编译原理与实践：二义文法的应用

就一个文法而言，对于其任何“移进-归约”分析器，尽管栈的内容和下一个输入符号都已清楚，但仍无法确定分析动作是“移进”还是“归约”，或者无法从几种可能的归约中确定其一，则称该文法是非LR的。LR文法肯定无二义，任何二义文法绝不是LR文法，也不是算符优先文法或LL（k）文法，更不存在相应的确定的语法分析器。但是，对某些二义文法可做适当修改，给出优先性和结合性，从而构造出比相应非二义文法更优越的LR分析器。

例如，算术表达式的二义文法的拓广形式、LR（0）项目集规范族以及识别活前缀的DFA如图5-10所示。

图5-10　二义表达式文法的DFA

从图5-10可以看出，状态I1、I7和I8中存在移进-归约冲突。

在I1中，归约项目E→E·实为接受项目。由于FOLLOW（E）={#}，也就是说，只有遇到句子的结束符号‘#’才能接受，因而与移进项目的移进符号‘+’、‘*’都不会冲突，所以可用SLR（1）方法来解决，即当前输入符为‘#’时接受，遇‘+’或‘*’时移进。

在I7和I8中，由于归约项目[E→E+E·]和[E→E*E·]的左部都为非终结符E，而FOLLOW（E）={#，+，*}，且移进项目均有‘+’和‘*’，即存在

FOLLOW(E)∩{+,*}≠φ

因而，I7和I8中的冲突不能用SLR（1）方法来解决。实际上，可以证明该二义文法用LR（k）方法仍不能解决此冲突。(www.xing528.com)

此时，可以定义优先关系和结合性来解决这类冲突。比如，规定‘*’优先级高于‘+’，且都服从左结合，那么在I7中，由于‘*’＞‘+’，故遇‘*’移进；又因‘+’服从左结合，所以遇‘+’则用E→E+E去归约。在I8中，由于‘*’＞’+’，且服从左结合，因此，不论遇到‘+’、‘*’或‘#’号都应归约。文法的LR分析表如表5-16所示。

表5-16　二义表达式文法的LR分析表

利用表5-16对输入串i+i*i进行分析，其过程如表5-17所示。

表5-17　用表5-16所示的LR分析表对输入串i+i*i进行分析的过程

显然，对二义文法规定了优先关系和结合性后的LR分析速度高于相应的非二义文法的LR分析速度。在对输入串i+i*i的分析中，用表5-16比用表5-2（同时也是表5-13）少了3步。对于其他的二义文法，用类似的方法也可能构造出无冲突的LR分析表。