上下文无关文法与语言

内容发布更新时间 : 2024/12/25 9:06:29星期一 下面是文章的全部内容请认真阅读。

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

(((以下照原文复制)))

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi