解决冲突

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

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

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

• 若为规约-规约冲突

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

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

• 若为移进-规约冲突

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

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

    • 若待规约的产生式优先级高，则规约

    • 若二者优先级相等

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

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

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

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

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

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

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

那么满足$x \le y$和$y \le z$，但是不满足$x \le z$。

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

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

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

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