上下文无关文法与语言

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]。

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