解决文法二义性的方法

前面已经说过，一棵语法树完全等价于一个最左（或最右）推导。然而，是不是说一个句子就一定只存在一个唯一的最左（或最右）推导，也就是说，一个句子是否一定只对应一棵语法树呢？答案是否定的。

例如，对于文法（2.1），关于句子（i*i+i）的最左推导就存在着一种与（2.4）截然不同的形式：

判断文法二义性

该推导所对应的语法分析树如图2-2所示。

显然，句子（i*i+i）的最左推导（2.4）和（2.6）不同，其分别对应的语法分析树图2-1和图2-2也不相同。二者不同之处在于：由第2代结点产生第3代结点的过程中，图2-1的语法树使用了规则E→E+E，而图2-2的语法树则使用了规则E→E*E。这种差别是本质的，意味着可以使用两种完全不同的方式得到同一个句子。(www.xing528.com)

图2-2　语法分析树

如果一个文法存在某个句子对应两棵不同的语法树，或者说，如果一个文法存在某个句子对应两个不同的最左（或最右）推导，则称该文法是二义的。

应当注意的是，文法的二义性和语言的二义性是两个不同的概念。文法二义并不代表语言一定是二义的，只有当产生一个语言的所有文法都二义，这个语言才是二义的。比如，可能有这样两个不同的文法G1和G2，其中一个是二义的而另一个是无二义的，但是却有L（G1）=L（G2），因此，这种语言不是二义的。

就二义性文法而言，句子的分析有可能不唯一，这点是编译程序不希望看到的。因此，对于一个程序设计语言来说。常常希望其文法无二义性，从而使得对其每个语句的分析是唯一的。