发布时间 : 星期日 文章上下文无关文法与语言更新完毕开始阅读
幸运的是，在实际应用中这种情况并不很严重。对于一般的编程语言中的结构所对应的文法来说，可用一种熟知的方法来消除其中的歧义性。图5.2中的表达式文法就很典型，所以我们将会把研究如何去除它的歧义性的过程作为一个重要的例子。
首先，我们注意到有两个导致图5.2中的文法的歧义性的原因： 1.
没有考虑运算符的优先级。虽然图5.17(a)中正确的结合了*（先于结合+），然而图5.17(b)却错误的结合了+（先于结合*）并且给出了一棵错误的分析树。在一个无歧义性的文法中将只允许图5.17(a)中的结构。
一系列同样的运算符既可从左到右也可从右到左地结合。例如，如果图5.17中的*全部换成+，那么对于串E+E+E将会得到两棵不同的分析树。因为加法和乘法都是满足结合律的，因此不管从左到右还是从右到左的结合都无所谓，但是为了去除歧义性，必须选择其中一种结合方式。习惯的做法是坚持从左到右的结合，所以只有图5.17(b)中是两个加号的正确结合方式。
2.
YACC中歧义性的消除 如果刚才使用的表达式的文法是歧义的，那么我们可能会疑虑图5.11中的YACC样本程序是如何实现的。没错，它所描述的文法确实是歧义的，但是YACC强大功能中的一部分正是用来去除绝大部分导致歧义性的因素。对于表达式文法，只要坚持下面两条就足以去除歧义性了： a) *比+的优先级高，也就是说*总是在它两边的+结合之前结合。这条规则告诉我们在例5.25中要使用推导（1）而不是推导（2）。 b) *和+都是左结合的，也就是说一些用*连接的表达式总是被从左向右地结合起来，对用+结合的表达式也同样。 YACC允许我们规定运算符的优先级，只要把它们按照从优先级最低到最高的顺序排列起来就行了。从技术上说，一个运算符的优先级将在如下产生式中应用：该运算符是这个产生式体的最右端的终结符号。我们也可以定义运算符是左结合还是右结合的，只要分别用关键字%left和%right就行了。例如，为了规定+和*都是左结合的，并且*比+的优先级高，我们只需要在图5.11中文法的开头部分写上如下的句子： %left ‘+’ %left ‘*’ 采用优先级的解决方法实际上是引入更多不同的变元，每个变元代表拥有同样级别的“粘结强度”的那些表达式。更明确的说就是：
1.
因子是不能被相邻的运算符（包括*和+）打断的表达式，因此在我们的表达式
文法中的因子只有：
(a) 标识符——不可能通过增加运算符的方法来把一个标识符打断。
(b) 任何被括号括起来的表达式——无论括号里面括的是什么。括号的用处正是
用来防止括号里面的东西成为括号外面的运算符的操作数。
2. 项是不能被相邻的加号打断的表达式。在我们的例中，只有+和*是运算符，因
此项就是一个和几个因子的乘积。例如，项a*b是可以被打断的，只要采用左结合的规则并且把a1*放到它的左边，这样它就变成了a1*a*b，也就是
(a1*a)*b，因而a*b就被打断了。然而，仅仅在它的左边放置一个加号项比如
a1+或在它的右边放置+a1是无法打断a*b的，正确的结合是：a1+a*b为a1+(a*b)，a*b+a1为(a*b)+a1。 3.
今后表达式是指任何可能的表达式，其中包括可以被相邻的加号或乘号打断的表达式。因此，我们例中的表达式就是一个或多个项的和。
图5.19：一个无歧义性的表达式文法
例5.27：图5.19展示了一个无歧义性的表达式文法，它和图5.2中的文法所产生的是同样的语言。考虑F，T和E，它们的语言分别是上文中定义的因子，项和表达式。例如，对于串a+a*a，该文法只允许有一棵分析树，就像图5.20中的那样。
图5.20：a+a*a的唯一的语法分析树
关于这个文法是无歧义性的事实还不算很明显，下面是一些关键的发现，它们能够解释为什么在这个语言中的串不可能拥有两棵不同的分析树。
? 从T推导出的串都是项，它们一定是一个或多个用*连接的因子。我们定义的因
子，在图5.19中就是F的产生式所定义的，它或者是标识符或者是一个用括号括起来的表达式。 ? T的两个产生式的形式能够决定一序列的因子的分析树只能是把f1*f2*?*fn (n>1)
打断为项f1*f2*?*fn-1和因子fn。原因是从F无法推导出项fn-1*fn这样的表达式，除非把它们用括号括起来。因而，当使用产生式T?T*F时F除了最后一个因子之外不可能推导出别的东西。也就是说项的分析树只能是类似于图5.21中那样的。 ? 同样的，一个表达式就是用+连接起来的一系列的项。当我们使用产生式E?E+T
来推导t1+t2+?+tn时，T只能推导出tn，体中的E只能推导出t1+t2+?+tn-1。原因同样是：如果不使用括号的话，T是不可能推导出两个或多个项的和的。
图5.21：一个项的所有可能的分析树的样子
5.4.3 最左推导作为表达歧义性的一种方式
即使当文法是无歧义的时候，推导也有可能不唯一。但下面的结论总是成立的：在无歧义的文法中，最左推导是唯一的，最右推导也是唯一的。我们只考虑最左推导，最右推导只给出结论。
例5.28：作为一个例子，注意图5.18中的两棵产物为E+E*E的分析树。如果从它们出发，我们将会分别得到两棵树(a)和(b)的最左推导如下：
E?E?E?I?E?a?E?a?E*E?a?I*E?a?a*E?a)
lmlmlmlmlmlmlma?a*I?a?a*alm
E?E?E?E?E*E?I?E*E?a?E*E?a?I*E?a?a*E?b)
lmlmlmlmlmlmlma?a*I?a?a*alm
注意这两个最左推导并不相同。这个例子并不能证明下面的定理，但它说明了树的不同导致了最左推导的不同。
定理5.29：对于任何文法G=(V,T,P,S)和T*中的串w，w有两棵不同的分析树当且仅当从S到w有两个不同的最左推导。
证明：（必要性）如果检查定理5.14中从分析树构造最左推导的过程，我们会发现只要两棵分析树中有一个（第一个）节点，在该节点处使用了不同的产生式，那么在构造最左推导时就会使用不同的产生式，因而得到了不同的最左推导。
（充分性）虽然前面并没有给出一个直接从最左推导构造分析树的方法，但是它的思想并不难。首先从根节点开始构造分析树，并把根节点的标号设为S。然后每次检查推导中的一步。在每一步中会有一个变元被替换，因此这个变元就对应于正在被构造的分析树中最左边的没有子节点但是标号为变元的节点。由最左推导中这一步所使用的产生式，可以决定这个节点的子节点分别是什么。如果有两个不同的推导，那么在这两个推导第一次发生不同的地方，所被构造的节点将会得到不同的子节点的列表，这也保证了所构造的分析树是不同的。
5.4.4 固有的歧义性
我们说一个上下文无关的语言L是固有歧义的，如果它的所有的文法都是歧义的。只要L有一个文法是无歧义的，那么L就是无歧义的。例如，我们说图5.2中的文法所生成的表达式的语言实际上是无歧义的。即使这个文法是歧义的，存在另外一个无歧义的文法和它生成同样的语言——图5.19中的文法。
我们将不去证明固有歧义语言，而是给出一个语言的例子，能够证明它是固有歧义的，我们将会直观的解释为什么任何关于它的文法都是歧义的。这个将要讨论的语言是：
L?{anbncmdm|n?1,m?1}?{anbmcmdn|n?1,m?1}
也就是说，L包含所有满足下列条件的a+ b+ c+ d+形式的串：
1. a和b的个数一样且c和d的个数一样，或者 2. a和d的个数一样且b和c的个数一样。
L是上下文无关语言。图5.22中的显然是L的一个文法。它使用分离的集合来产生L中的两种类型的串。
这个文法是歧义的。比如，串aabbccdd有两个最左推导： 1. S?AB?aAbB?aabbB?aabbcBd?aabbccdd
lmlmlmlmlm2. S?C?aCd?aaDdd?aabDcdd?aabbccdd
lmlmlmlmlm图5.23中的是这个两棵分析树。
图5.22：一个固有歧义语言的文法
图5.23：aabbccdd的两棵分析树
证明L的所有文法都一定是歧义的过程是很复杂的。然而，它的本质如下：我们需要说明几乎是有限个数的其中a,b,c,d的个数相同的串都一定用下面两种不同的方法生成：一种方法是a和b的个数一样，c和d的个数一样。另一种是a和d的个数一样，b和c的个数一样。
例如，生成a和b的个数相同的串的唯一方法是使用类似于图5.22中A的变元。可能有些变化，但这些变化并不改变根本的东西。例如：
? 可以避免一些短串，比方说例如把基本的产生式A?ab换为A?aaabbb。 ? 可以用一些其它的变元来分享A的工作，例如，通过使用变元A1和A2，其中A1
产生奇数个a而A2产生偶数个，类似于：A1?aA2b | ab; A2?aA1b | ab。 ? 也可以让A产生的a和b的个数不完全相等，而是差着某个数。例如，可以从一
个产生式S?AbB开始然后用A?aAb | a来生成比b多一个的a。 然而，我们不能避免某些生成在某种程度上和b的个数相匹配的个数的a。
同样的，我们可以说明一定存在一个类似于B的变元用来生成匹配个数的c和d。同样，该文法中也一定有类似于C（生成匹配个数的a和d）和D（生成匹配个数的b和c）的变元。 把这个观点形式化后就能够证明不管我们对基本的文法作怎样的修改，它都能像图5.22中的文法那样有两种生成至少几个anbncndn形式的串的方法。