上下文无关文法与语言(7)

1 ]>

图5.16：课程的DTD

习题5.3.5：把图5.16中的DTD转换为上下文无关文法。

5.4 文法和语言的歧义性

前面已经看到，CFG的应用往往立足于使用文法来提供文件的结构。例如，在第5.3节中的使用文法来定义程序和文档的结构。其中不言而喻的假定是文法能唯一地决定它的语言里每个串的结构。然而，下面将会看到并不是每一个文法都能提供这种唯一的结构的。

如果一个文法不能提供唯一的结构，那么有时可以通过重新设计这个文法，使得它能够给每一个它的语言中的串以唯一的结构。但不幸的是，有时却无法达到这个目的。也就是说，的确存在这样的一类CFL，它们具有“固有的歧义性”，定义这类语言的任何文法总是对该语言中的某些串提供多于一个的结构。

5.4.1 歧义文法

下面我们回到一直用着的例子上来：图5.2中的表达式文法。这个文法能够生成任何包含*和+运算符的序列，而且产生式E?E+E|E*E允许我们按照任何选定的顺序来生成这些表达式。

例5.25：例如，考虑句型E+E*E，从E到它有两种推导：

1. E?E?E?E?E*E 2. E?E*E?E?E*E

注意在推导（1）中，第二个E是用E*E来替换的，而在推导（2）中是用E+E来替换第一个E。图5.17给出了这两棵分析树，需要注意它们是不同的分析树。

图5.17：具有同样产物的两棵分析树

1

原文中没有该行——译者注

这两个推导的不同之处是有意义的。如果考虑表达式的结构的话，推导（1）说第二和第三个表达式先相乘，再和第一个表达式相加。而推导（2）则表示先把前两个表达式相加，再把它们的和跟第三个表达式相乘。举一个更具体的例子，第一个推导认为1+2*3应该结合成1+(2*3)=7，而第二个推导则认为它应该结合成(1+2)*3=9。很明显，是第一个而不是第二个推导跟我们在数学中对表达式的运算法则相一致。

对于描述表达式的结构来说，由于图5.2中的文法对很多表达式都能给出两种以上不同的结构（比如通过在推导过程中用E+E*E来替换一个标识符所得到的串），所以该文法对于提供表达式唯一的结构来说不是最好的选择。在实际应用中，它往往给出错误的表达式中的结合方式。为了在编译器中使用这个表达式文法，我们需要对它进行一些修改，使它能够提供唯一正确的表达式中的结合方式。□

另一方面，如果一个文法仅仅是对于一个串存在不同的推导（而不是不同的分析树）并不意味这个文法中存在缺陷。下面就是一个例子。

例5.26：使用同样的表达式文法，可以发现对串a+b有许多不同的推导。其中的两个例子是：

1. E?E?E?I?E?a?E?a?I?a?b 2. E?E?E?E?I?I?I?I?b?a?b

然而，这些推导所提供的结构并没有本质的区别，它们都是说a和b是标识符，而且都要把它们的值相加。事实上，如果使用定理5.18和5.12中的构造过程的话，这些推导所产生的分析树都是一样的。□

上面的两个例子告诉我们并不是多种推导导致了歧义性，而是存在多棵不同的分析树所导致的。因此，我们说一个CFG G=(V, T, P, S)是歧义的，如果T*中至少存在一个串w，使得有多于一棵的不同分析树满足如下条件：它们的根都是S，产物都是w。如果一个文法使得任意的串都最多只对应一棵分析树，那么该文法就是无歧义的。

例如，例5.25几乎就已经给出了一个图5.2中文法歧义性的证明。我们只需要证明图5.17中的分析树能够经过补充后产生终结符号串的产物。图5.18就是这个补充过程的一个例子。

图5.18：产物为a+a*a的树，实证了我们的表达式文法的歧义性。

5.4.2 去除文法的歧义性

在理想的情况下，我们应该能够提供给你一个算法，它能够从CFG中去除歧义性，这一点在很大程度上就像第4.4节中我们提供的那个用来去除有穷自动机里多余状态的算法一样。然而，令人惊讶的事实是，就像我们将要在第9.5.2节中所看到的那样，实际上即使想要首先判断一个CFG是不是歧义的，都不存在一个算法能够实现。而且，第5.4.4节中将会展示一个上下文无关语言，对它而言只存在歧义的文法，根本不存在无歧义文法。对这样的语言来说，去除它的歧义性是不可能的。

幸运的是，在实际应用中这种情况并不很严重。对于一般的编程语言中的结构所对应的文法来说，可用一种熟知的方法来消除其中的歧义性。图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+( …… 此处隐藏：3649字，全部文档内容请下载后查看。喜欢就下载吧 ……