内容发布更新时间 : 2024/5/4 11:46:52星期一 下面是文章的全部内容请认真阅读。
3. 该产生式是A?(E1)*的形式。这时要引入一个新的变元B（同样，B不能在别处出
现）然后把这个产生式变为：
A ? BA A ? ε B ? E1
4. 该产生式是A?(E1)+的形式。这时要引入一个新的变元B（同样，B不能在别处出
现）然后把这个产生式变为：
A ? BA A ? B B ? E1
5. 该产生式是A?(E1)?的形式。把这个产生式变为：
A ? ε A ? E1
例5.24：下面来考虑 怎样把这条DTD的规则
转换为合法的CFG产生式。首先，这条规则的体可以看作两个表达式的连接，第一个是型号，价格，处理器，RAM，第二个是DISK+。因此引入两个变元A和B来分别代表这两个子表达式，就可以得到下面的产生式：
PC ? AB
A ? 型号 价格 处理器 RAM B ? DISK+
其中仅有最后的一个产生式不是合法的形式。这时再引入一个新的变元C和两个新的产生式来代替它：
B ? CB | C C ? DISK
在这个特例下，由于A所能得出的表达式仅仅是几个变元的连接，而DISK仅仅是一个单个的变元，因此实际上没必要有A和C这两个变元，而只要用下面的产生式来代替它们就够了：
PC ? 型号 价格 处理器 RAM B B ? DISK B | DISK
□
5.3.5 5.3节习题
习题5.3.1：证明如果一个串是括号匹配的，就像例5.19中所说的那样，那么它一定能用B?BB|(B)|ε来生成。提示：对串的长度进行归纳。
* 习题5.3.2：考虑同时包含圆括号和方括号且这两种括号都匹配的所有串的集合。对于这种串的来历有一个例子。考虑C语言中的表达式，圆括号表示函数的参数，方括号表示数组的下标。如果把C语言中的表达式里除了括号以外的字符都去掉，那么剩下的串就是这种类型的括号匹配的串了。例如：
f (a[i]*(b[i][j], c[g(x)]), d[i])
就变成了一个括号匹配的串([]([][][()])[])。试着设计一个文法来定义所有的圆括号和方括号都匹配的串。
! 习题5.3.3：在第5.3.1节中，考虑下面的文法：
S ? ε| SS | iS | iSe
并且当时说过可以通过重复的使用下面的方法来测试它的语言L的成员性：（这个测试过程从w开始，并且在这个重复的过程中串w会发生变化）
1. 如果这个串是从e开始的，那么测试失败，w不在L中。 2. 如果串里没有e了（还可以有i），那么测试通过，w在L中。
3. 否则，删掉第一个e和它左边的i，然后继续对剩下的串进行这三个步骤的测试过
程。 试证明这个测试过程能够正确的识别出L中的串。
习题5.3.4：把下面的东西加入到图5.13中的HTML的文法中去： * a) 项目列表必须用标记符来表示结束。
b) element可以试无序列表，就像有序列表一样。无序列表是通过用标记符
括住来表示的。 ! c) element可以是一个表格。表格是用
里面可以有一行或多行，每一行都用
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节中将会展示一个上下文无关语言，对它而言只存在歧义的文法，根本不存在无歧义文法。对这样的语言来说，去除它的歧义性是不可能的。