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

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形式的串的方法。

5.4.5 5.4节习题

* 习题5.4.1：考虑下面的文法

S ? | aS | aSbS | ε

这个文法是歧义的，试给出串aab的两个： a) 分析树。 b) 最左推导。 c) 最右推导。

! 习题5.4.2：证明习题5.4.1中的文法恰恰能够生成所有具有如下性质的a、b串：该串的任何前缀中a的个数至少要和b的个数一样多。

*! 习题5.4.3：找到一个习题5.4.1中的语言的无歧义的文法。

!! 习题5.4.4：在习题5.4.1的文法中，有些a、b串仅有一棵分析树。试给出一个有效的测试方法来判断一个给定的串是否有该性质。如果该测试“考虑所有分析树在从中跳出产物为该串的”的话，那么就不算是有效的。

! 习题5.4.5：这个问题和习题5.1.2中的文法有关，在这里重新写一遍：

S?A1BA?0A|?B?0B|1B|? a) 证明该文法是无歧义的。

b) 找到一个生成同样语言的文法，并且要求是歧义文法，并且展示它的歧义性。

*! 习题5.4.6：习题5.1.5中你的文法是无歧义的吗？如果不是的话，把它改写为无歧义文法。

习题5.4.7：下面的文法生成的是以x和y为操作数、二元运算符+、-和*为运算符的前缀表达式：

E ? +EE | *EE | -EE | x | y

a) 找到串+*-xyxy的最左、最右推导和一棵分析树1。 ! b) 证明该文法是无歧义的。

1

原文误为推导树——译者注

5.5 第 5 章摘要

? 上下文无关文法：通过使用产生式——一种递归定义的规则，CFG是定义语言的

一种方法。CFG由一个变元集、一个终结符号集、一个开始符号和产生式集合构成。每个产生式由一个头变元和一个体构成，而产生式的体是由零个或多个变元和/或终结符号组成的串构成的。 ? 推导和语言：由开始符号开始，通过重复的用产生式的体来替换产生式的头，最

后可以得到终结符号串，这个过程叫做推导。一个CFG的语言就是能够这样推导出来的终结符号串的集合，它也叫做上下文无关语言。 ? 最左和最右推导：如果总是替换串中最左（最右）的变元，那么这种推导就叫做

最左（最右）推导。CFG的语言中的每一个串都至少有一个最左推导和一个最右推导。 ? 句型：推导过程中的任何一步都有一个由变元和/或终结符号组成的串，这个串叫

做句型。如果一个推导是最左（最右）的，那么这种串就是左（右）句型。 ? 分析树：分析树是一棵能够展示推导过程的本质的树。内部节点都用变元来标

号，而叶节点都用终结符号或ε来标号。对于每一个内部节点，一定存在一个以该节点的标号为头，以它的子节点的标号从左到右连接起来的串为体的产生式。 ? 分析树和推导的等价性：一个终结符号串属于一个文法的语言当且仅当它是至少

一棵分析树的产物。因而，最左、最右推导和分析树是否存在都是判断一个串是否属于一个CFG的语言的等价条件。 ? 歧义文法：对于一些CFG，有可能找到一个有多于一棵的分析树的串，或者等价

的找到多于一个的最左或最右推导。这样的文法就是歧义的。 ? 去除歧义性：对于很多有用的文法，比如那些用来描述典型的编程语言中的程序

结构的文法，都有可能找到一个无歧义的文法来生成和它同样的语言。不幸的是，一个语言的无歧义文法往往比最简单的歧义文法要复杂的多。另外也有一些上下文无关语言（一般来说大多是专门设计出来的）是固有歧义的，也就意味着任何该语言的文法都是歧义的。 ? 文档类型定义：正在形成的XML标准是用来在Web文档中共享信息的，它使用

了一种符号表示法，叫做DTD。DTD是用来通过文档中嵌套的语义标记符来描述这种文档的结构的。DTD本质上就是一种上下文无关文法，它的语言就是一类相关的文档。

5.6 第 5 章参考文献

上下文无关文法是由乔姆斯基[4]提出来的，本来是计划用它来描述自然语言。不久以后人们就使用了类似的想法来描述描述计算机语言——巴科斯[2]的Fortran和瑙尔[7]的Algol。因此，CFG有时也指“巴科斯-瑙尔型文法”。

文法的歧义性问题是几乎同时由康托尔[3]和弗洛伊德[5]指出的。固有歧义性是由格罗斯[6]首先指出的。

对于CFG在编译器种的应用，请参考[1]。在定义XML标准的文档中有DTD的定义[8]。

（（（以下照原文复制）））