The Decaf Book
  • Introduction
  • 语言规范
  • Java 框架分阶段指导
    • 本章导引
    • PA1-A:语法分析器的自动构造
      • 阶段任务
      • 词法分析
      • 抽象语法树
      • 文法分析
    • PA1-B:基于 LL(1) 的语法分析器半自动构造
      • 阶段任务
      • LL(1) 文法分析
      • 错误恢复
    • PA2:语义分析
      • 阶段任务
      • 类型、符号和作用域
      • 访问者模式
      • 符号表构建
      • 类型检查
    • PA3:中间代码生成
      • 阶段任务
      • TAC 程序
      • 面向对象机制
      • 控制流的翻译
    • PA4:中间代码优化
      • 实验内容
      • 基本块
      • 数据流分析概述
      • 数据流优化概述
      • 公共表达式提取
      • 复写传播
      • 常量传播
      • 死代码消除
  • Scala 框架分阶段指导
    • 本章导引
    • PA1:语法分析器的自动构造
      • 阶段任务
      • 词法分析
      • 抽象语法树
      • 文法分析
      • 访问者模式
    • PA2:语义分析
      • 阶段任务
      • 类型、符号和作用域
      • 符号表构建
      • 类型检查
    • PA3:中间代码生成
      • 阶段任务
      • TAC 程序
      • 面向对象机制
      • 控制流的翻译
    • PA3-JVM:JVM 字节码生成
      • 阶段任务
      • JVM 字节码简介
      • 翻译过程
    • PA4:中间代码优化
      • 实验内容
      • 基本块
      • 数据流分析概述
      • 数据流优化概述
      • 公共表达式提取
      • 复写传播
      • 常量传播
      • 死代码消除
  • Rust 框架分阶段指导
    • 本章导引
    • PA1-A:语法分析器的自动构造
      • 实验内容
      • lalr1使用指导
        • 编写lexer
        • impl块的可选属性
        • 产生式和语法动作
        • 解决冲突
        • 一个完整的例子
      • 抽象语法树
      • 框架中部分实现的解释
      • 文件结构
    • PA1-B:基于 LL(1) 的语法分析器半自动构造
      • 实验内容
      • lalr1使用指导
      • 错误恢复
      • 文件结构
    • PA2:语义分析
      • 实验内容
      • 语义分析
      • 符号表
      • visitor模式
    • PA3:中间代码生成
      • 实验内容
      • 中间代码
      • 中间代码中的类型信息
      • 运行时存储布局
      • 面向对象机制
      • tacvm简述
    • PA4:中间代码优化
      • 基本块
      • 数据流分析概述
      • 数据流优化概述
      • 公共表达式提取
      • 复写传播
      • 常量传播
      • 死代码消除
    • PA5:寄存器分配
      • 实验内容
      • 图着色基本原理
      • 着色算法
      • 预着色节点
      • 干涉图节点合并
      • 调用约定
Powered by GitBook
On this page

Was this helpful?

  1. Rust 框架分阶段指导
  2. PA1-A:语法分析器的自动构造
  3. lalr1使用指导

解决冲突

Previous产生式和语法动作Next一个完整的例子

Last updated 5 years ago

Was this helpful?

我尝试找了很多文档,也用yacc/bison做了很多实验,但仍然没有能够完全总结出一个完整的解决和汇报冲突的策略。既然这样,那我就不尝试实现它的规范了,lalr1以我的规范为准,如果和yacc/bison的表现不一致,那就不一致吧。(当然,如果它的表现和我声明的规范矛盾了,那肯定还是一个bug)

首先定义产生式的优先级(不定义产生式的结合性,因为没有意义且不会用到)。没有#[prec(Term)]时,产生式的优先级与右端最后一个终结符的优先级相同,如果右端没有终结符或者右端最后一个终结符没有定义优先级,那么这条产生式就没有优先级;有#[prec(Term)]时,产生式的优先级与与终结符Term相同,同样如果Term没有优先级,那么这条产生式就没有优先级。

先假设只有两种冲突选择:

  • 若为规约-规约冲突

    • 如果两个规约选择都有优先级,且优先级不相等,则选择优先级高的产生式规约

    • 否则,选择先出现的产生式规约,且汇报一个冲突警告

  • 若为移进-规约冲突

    • 若待移进的终结符和待规约的产生式都有优先级(注意此时移进的终结符一定也有结合性)

      • 若待移进的终结符优先级高,则移进

      • 若待规约的产生式优先级高,则移进

      • 若二者优先级相等

        • 若移进的终结符为左结合,则规约

        • 若移进的终结符为右结合,则移进

        • 若移进的终结符为不结合(有结合性,结合性是不结合),则既不移进也不规约,这两种选择都不合法

    • 否则,移进,并且汇报一个冲突警告

以上就是解决冲突的全部内容了吗?这的确是文档里能找到的全部内容了,但我认为事情还没说完:在一个状态转移上,可行的选择可能大于两个。这一定是有大于两个规约选择,或者有一个移进选择和大于一个规约选择。

这之所以会成为一个问题,是因为没办法通过直接推广上面的两两比较来选择出一个"最好"的选择。在集合{ 移进,规约1,规约2,...,规约n }上如果定义x≤y⇔x \le y \Leftrightarrowx≤y⇔ xxx和yyy冲突的时候选yyy,那么这个关系并不是一个合法的偏序关系,例子如下:

  规约x:无优先级,出现在第2位
  规约y:优先级1,出现在第1位
  规约z:优先级2,出现在第3位

即使先不考虑所有的需要"汇报一个冲突警告"的情形,也就是说产生式的优先级和终结符的优先级和结合性都存在且产生式的优先级不会相等,这时这个关系的确是一个偏序关系。然而如果需要处理结合性为不结合的终结符,仍然不能做出非常令人信服的选择(因为这个偏序集仍然不是全序的),例如:

  规约x: 优先级1
  规约y: 优先级2
  移进z: 优先级2,结合性为不结合

至少有两种理解是合理的:一是规约y和移进z"抵消"了,所以选择规约x;二是规约x因为优先级不如规约y而不能选择,规约y和规约z因为终结符不结合也不能选择,所以没有选择。

我没有查到yacc/bison是怎么处理这些情况的,试图通过实验来归纳的时候也遇到了很多无法理解的问题,没有得出有用的结论。简单起见,规定如果有大于两个冲突选择,lalr1将拒绝生成代码。它会把冲突情况做出一定程度的汇报,然后中止编译。

那么满足x≤yx \le yx≤y和y≤zy \le zy≤z,但是不满足x≤zx \le zx≤z。