12.3 利用符号的优先级来解决冲突

大部分情况下， LR(1) 解析过程的 shift/reduce 冲突可以通过引入符号的优先级来解决。具体方法为：

（1） 定义某些符号的优先级以及结合方式；

（2） 当构造 LR(1) 的过程中出现了 shift/reduce 冲突时，即某个状态 I 中同时还有 [ A -> u.aw , c ] 和 [ B -> v. , a ] ，若已定义符号 a 的优先级，且符号串 v 中至少有一个已定义优先级的符号，则可通过以下原则确定 M[I, a] 的动作：

（2.1） 找到 v 中最右边的、已定义优先级的符号（也就是 v 中离 a 最近的一个已定义优先级的符号），假设为 b ；

（2.2） 若 a 的优先级 低于 b 的优先级，则： M[I, a] = reduce B -> v ；

（2.3） 若 a 的优先级 高于 b 的优先级，则： M[I, a] = shift NEXT(I, a) ；

（2.4） 若 a 的优先级 等于 b 的优先级，则根据 a 和 b 的结合方式：

（2.4.1） 若 a 和 b 都为左结合，则 M[I, a] = shift NEXT(I, a) ；

（2.4.2） 若 a 和 b 都为右结合，则 M[I, a] = reduce B -> v 。

来看一个简单的例子，语法为：

  1. 0) S -> E
  2. 1) E -> E + E
  3. 2) E -> E * E
  4. 3) E -> id
  5.  
  6. first(S) = first(E) = id

所有的状态及转移关系见下：

  1.  I0:                              I1:                            I2:
  2.      Configurations:                  Configurations:                Configurations:
  3.          S -> . E     , $                 S -> E .     , $               E -> id .    , +/*/$
  4.          E -> . E + E , +/*/$             E -> E . + E , +/*/$       Actions:
  5.          E -> . E * E , +/*/$             E -> E . * E , +/*/$           +  : reduce E -> id
  6.          E -> . id    , +/*/$         Actions:                           *  : reduce E -> id
  7.      Actions:                             +  : shift  I3                 $  : reduce E -> id
  8.          E  : goto   I1                   *  : shift  I4
  9.          id : shift  I2                   $  : reduce S -> E
  10.  
  11.  
  12.  I3:                              I4:
  13.      Configurations:                  Configurations:
  14.          E -> E + . E , +/*/$             E -> E * . E , +/*/$
  15.          E -> . E + E , +/*/$             E -> . E + E , +/*/$
  16.          E -> . E * E , +/*/$             E -> . E * E , +/*/$
  17.          E -> . id    , +/*/$             E -> . id    , +/*/$
  18.      Actions:                         Actions:
  19.          E  : goto   I5                   E  : goto   I6
  20.          id : shift  I2                   id : shift  I2
  21.  
  22.  
  23.  I5:                                           I6:
  24.      Configurations:                               Configurations:
  25.          E -> E + E . , +/*/$                          E -> E * E . , +/*/$
  26.          E -> E . + E , +/*/$                          E -> E . + E , +/*/$
  27.          E -> E . * E , +/*/$                          E -> E . * E , +/*/$
  28.      Actions:                                      Actions:
  29.          +  : shift  I3 / reduce E -> E + E            +  : shift  I3 / reduce E -> E * E
  30.          *  : shift  I4 / reduce E -> E + E            *  : shift  I4 / reduce E -> E * E
  31.          $  : reduce E -> E + E                        $  : reduce E -> E * E

注意状态 I5 和 I6 中都出现了两个 shift/reduce 冲突。以 I5 为例，它同时有以下两条形态：

  1. 1) E -> E + E . , *
  2. 2) E -> E . * E , x

上面第一条形态的 lookahead 和第二条形态中黑点后面的终结符都是 ，因此当它遇到一个 时，可以执行 shift I4 ，也可以执行 reduce E -> E + E 。

现在按前面介绍的方法来确定该执行的动作。首先定义符号 * 和 + 的优先级分别为 0 和 1 （数字越小优先级越高），且定义两个符号都是左结合的。

再来看上面第一条形态，其产生式右边的符号串为 E + E ，这个符号串里最右边的、且定义了优先级的符号就是 + ，其优先级为 1 。而此形态的 lookahead （也就是 * ）的优先级为 0 ，高于 + 。因此，选择的动作为 shift 。

再按上面的方法消除其他 shift/reduce 冲突，确定 I5 和 I6 的动作如下（其中方括号内的是被放弃的动作）：

  1.  I5:                                                 I6:
  2.      Configurations:                                     Configurations:
  3.          E -> E + E . , +/*/$                                E -> E * E . , +/*/$
  4.          E -> E . + E , +/*/$                                E -> E . + E , +/*/$
  5.          E -> E . * E , +/*/$                                E -> E . * E , +/*/$
  6.      Actions:                                            Actions:
  7.          +  : reduce E -> E + E [shift  I3]                 +  : reduce E -> E * E [shift I3]
  8.          *  : shift  I4         [reduce E -> E + E]         *  : reduce E -> E * E [shift I4]
  9.          $  : reduce E -> E + E                             $  : reduce E -> E * E

LL(1) 分析法的解析过程中，在挑选产生式的时候只利用下一个读入符号（lookahead）的信息，而 LR(1) 分析法不仅仅是利用下一个读入符号的信息，事实上，它几乎利用了前面读入过的所有的符号的信息。 LR(1) 分析法的解析力量和适用范围远大于 LL(1) 分析法，在引入符号优先级解决常见的 shift/reduce 冲突情况后，它可以解析目前几乎所有的程序语言。

到了这里，可以圆满的回答上一章最后的两个问题了：

如何找出可行的折叠？ 答案：利用状态和形态，当转移到一个含可折叠形态 [ A -> u. , a ] 的状态、且下一个读入符号是 a 时，就可以执行一次可行的折叠了。

有多个可行的折叠怎么办？ 答案： 若采用 LR(1) 分析法，则很少会出现这种情况，且可以比较容易的将语法改写成 LR(1) 语法。