上下文无关文法与语言

第 5 章 上下文无关文法及语言

现在我们把注意力从正则语言转移到另外一大类语言上来，它们叫做“上下文无关语言”。这个语言类有着自然、递归的表示方法，这种表示方法叫做“上下文无关文法”。 从1960年以来，上下文无关文法一直在编译技术中扮演着重要的角色。它们能够把分析器（一类用来在编译过程中发掘源程序结构的程序）的实现从一种费时的、不通用方式的设计工作转变成为一种能够很快完成的工作。近年来，上下文无关文法也被用来描述文档格式：XML（eXtensible Markup Language 可扩展标记语言）中使用的DTD（Document-Type Definition 文档类型定义）就是用来描述Web上的信息交换格式的。

在本章中，我们将首先介绍上下文无关文法的表示方法，然后将介绍怎样用文法来定义语言。我们将会讨论到“语法分析树”──对一个文法处在它所表示的语言的字符串中结构的图形描述。语法分析树是对一个编程语言的语法分析器的产物，也是通常用来获得程序结构的途径。

上下文无关语言还有另外一种等价的自动机表示叫做“下推自动机”。我们将在第6章介绍下推自动机。虽然它不如有穷自动机重要，但仍然要介绍它，原因是作为一种语言的定义机制来说，它跟上下文无关文法具有等价性，后面在第7章研究如何判定上下文无关语言以及研究上下文无关语言的封闭性时，这种等价性是非常有用的。

5.1 上下文无关文法

这一章的内容将从非形式化地介绍上下文无关文法的表示法开始。形式化的定义会在读者了解到这些文法的一些重要的能力之后给出。届时我们将会说明怎样形式地定义一个文法，并将介绍一种叫作“推导”的过程：它能够决定在一个文法的语言中到底有哪些串。

5.1.1 一个非形式化的例子

下面来考虑一个“回文（palindrome）”的语言。“回文”是指正向和反向读起来都一样的串，比如otto或者madamimadam（“Madam, I’m Adam,”引自Eve在Eden的花园里听到的第一句话）。换句话说，串w是一个回文当且仅当w = wR 。考虑简单些的情况——只需要描述字母表{0, 1}上的回文，这个语言包括像0110，11011这样的串，也包括空串ε，但不包括像011或0101这样的串。

很容易验证这个0,1上的回文语言Lpal不是正则语言，要做到这点只需要使用泵引理即可：假设Lpal是一个正则语言，令n是与其相关的常数，考虑回文串w = 0n10n ，如果Lpal是正则的，那么我们就能够把w写为w = xyz ，其中y由第一组0中的若干个（但至少一个）构成。接下来，如果Lpal是正则的话那么xz也应该在Lpal里。然而由于xz的两端的0的个数不同，进而可知它不可能是回文串，由此得出的矛盾可以推翻前面关于Lpal是正则语言的假设。

对于什么样的0,1串在Lpal里，有一个自然的、递归的定义，它从一个最基本的显然属于Lpal中的串开始，接着利用一个最直观的思想：如果一个串在Lpal里，那么它开头和结尾

的字母一定相同，进一步得出：当把它开头和结尾的字母都去掉以后，剩下的串一定也是回文。具体写出来就是： 基础：ε，0和1都是回文。

归纳：如果w是回文，那么0w0和1w1也都是回文。另外，除了由上面的基础和归纳定义出来的串之外就再没有回文了。

上下文无关文法就是一个形式化的表示法，它可用来表达这种递归形式定义的语言。一个文法是由一个以上用来代表字符串类（也就是语言）的变元构成的，在这个例子里，我们只需要使用一个变元P，它用来代表回文串的集合（也就是组成语言Lpal的字符串类）。另外还有一些用来说明每个类中的串是怎样构造的规则，构造既可以使用字母表上的符号，也可以使用类中已经有的串，还可以两者都用。

图5.1：回文的上下文无关文法

例5.1：图5.1给出了用上下文无关文法定义回文的规则。这些规则的含义将在第5.1.2节中阐明。

前三条规则定义了基础，它们表示回文的字符串类中包括串ε，0和1。这三条规则的右端（箭头指向的那边）都没有变元，这也是说它们定义了基础的原因。

后两条规则是定义的归纳部分。比如，规则4是说如果串w在P这个类中的话，那么串0w0也在P这个类中。类似的，规则5告诉我们1w1也在P中。□

5.1.2 上下文无关文法的定义

语言的文法性描述包括四个重要部分： 1.

一个符号的有穷集合，它定义了语言的字符串中可能出现的符号。在上面回文的例中该集合为{0, 1}，这些符号叫做终结符号。

一个变元的有穷集合，变元有时也叫做非终结符或语法范畴。每个变元代表一个语言，也就是说，一个字符串的集合。在上面的例中只有一个变元P并且它就是用来代表以{0, 1}为字母表的回文串类（回文串的语言）的。

有一个变元叫做开始符号，它代表语言开始被定义的地方。其它变元用来代表其它辅助的字符串类，这些变元是用来帮助开始符号定义该语言的。在上面的例中，唯一的变元P同时也是开始符号。

一个产生式（或者也叫规则）的有穷集合，它用来表示语言的递归定义，每个产生式包括：

(a) 一个变元，它被该产生式定义或者部分定义，这个变元通常叫做产生式的

头。

2.

3.

4.

(b) 一个表示产生式的符号?。

(c) 一个包含零个或多个终结符号或变元的串，它叫做产生式的体，它用来表示

一种构成产生式头变元所代表语言的方法。具体的构造过程是：保持终结符号不动，把任何已知属于该语言的串里出现的产生式的头用产生式的体替换。 图5.1是一个产生式的例子。

上面给出的四个部分构成了一个上下文无关文法（Context-Free Grammar），简称文法，或者CFG。一个CFG G可以用组成它的四部分表示，记做G = (V, T, P, S)，其中V是变元（Variable）的集合，T是终结符号（Terminal）的集合，P是产生式（Production）的集合，S代表开始符号（Start Symbol）。 例5.2：回文的文法Gpal可以表示为

Gpal = ({P}, {0, 1}, A, P)

其中A表示图5.1中五个产生式的集合。

例5.3：这次来考虑一个复杂一些的CFG，它可简化地表示典型的编程语言中的表达式。首先，运算符限制为只有+和*， 分别用来表示加法和乘法。其次，表达式中允许有标识符，但不是一般编程语言中的那种（字母开头，后面有零个或多个字母或数字），而是字母仅限为a和b、数字仅限为0和1。也就是说每个标识符必须由a或b打头，后面可以跟着任何{a, b, 0, 1}*中的串。

这个文法中需要两个变元。一个记做E，代表表达式（Expression），同时它也是开始符号，用来表示我们所要定义的语言。另一个变元记做I，代表标识符（Identifier），它所代表的语言其实是正则的，也就是下面的正则表达式所表示的语言：

(a + b)(a + b + 0 + 1)*

然而，在文法中不应该出现正则表达式。不过我们可以用一系列的产生式来表示和这个正则表达式所表示的实质上一样的东西。

图5.2：简单表达式的上下文无关文法

这个描述表达式的文法可以形式化的记为G = ({E, I}, T, P, E)，其中T是终结符号的集合{+, *, (, ), a, b, 0, 1}，P是图5.2中产生式的集合，下面是这些产生式的解释

规则（1）定义了表达式类的基础部分，说的是一个表达式可以是一个标识符。规则（2）到（4）给出了表达式类定义的归纳部分：规则（2）说一个表达式可以由两个表达式中间用加号连接组成；规则（3）和（2）类似，不过把加号换成了乘号；规则（4）则说任何由一对括号括起来的一个表达式本身也是表达式。

规则（5）到（10）定义了标识符I。其中规则（5）和（6）给出了基础部分——a和b都是标识符。其它的四条规则给出了归纳定义——任何标识符后面再加上a, b, 0, 1中的任何一个所得到的结果依然是标识符。□

产生式的减缩表示法 把产生式看作属于它的头变元是很方便的，因此我们将经常会使用像“A的产生式”或者“A-产生式”这样的记法来表示以A为头变元的产生式。我们有时也这样来书写一个文法的产生式：每个变元只在产生式头中出现一次，而在该产生式的体里列出所有该变元的产生式的体，并且在它们之间用竖杠分隔。也就是说，产生式组A?α1， A?α2，…，A?αn可以用一个下面的表示法来代替：A?α1 | α2 | ? | αn 。举例来说，图5.1中的回文文法可以写作：P?ε| 0 | 1 | 0P0 | 1P1 。

5.1.3 使用文法来推导

产生式可以用来推断一个给定的字符串确实处在一个给定的变元所代表的语言中，这样的推断有两条途径：比较常规的一种方法是从产生式的体到产生式的头来使用规则。也就是说，对于产生式的体中出现的变元，我们可以取出一个已知属于这个变元所代表的语言中的串，然后把这样得到的串按照在体中的先后顺序连接起来，中间也同时按顺序加上体中的终结符号。这样得到的串就一定在该产生式的头所代表的语言中。这种方式的推理叫做递归推理。

另外一种方法是从产生式的头到体来使用规则，由此定义一个文法的语言。具体的做法是：使用以开始符号为头的一个产生式来扩展开始符号，接着通过替换体中变元的方式来扩展所得到的字符串，具体替换的方式是用一个以该变元为头的产生式的体来替换该变元。继续这个过程，直到得到的字符串中只有终结符号。这个文法的语言就是所有能用这种方式得到的字符串的集合。这种使用文法的方式叫做推导。

下面举一例来说明第一种方法——递归推理。然而，通常用推导的方法来考虑文法更加自然，因此紧接着我们就会给出描述这种推导的表示法。

例5.4：考虑一些使用图5.2中的文法进行推理的例子，图5.3是这些推理的汇总。例如，第（i）行说我们可以通过使用产生式5来推断串a属于I所代表的语言。第（ii）行到第（iv）行说我们可以推断b00是一个标识符（通过使用产生式6一次得到b，再使用产生式9两次就能得到后面的两个0）。

推理得出的字符串 属于的语言 使用的产生式 使用的字符串 图5.3：使用图5.2中的文法进行串的推理

第（v）行和第（vi）行利用产生式1推断出以下结论：由于任何标识符都是表达式，因此我们在第（i）行和第（iv）行中推断出的标识符a和b00也都是变元E所代表的语言中的串。第（vii）行利用产生式2推出这些表达式1的和也是表达式；第（viii）行利用产生式4推出用括号括着的同样的该串也是表达式2；第（ix）行利用产生式3来把 a与我们在第（viii）行中所发现的表达式相乘。□

从头到体地使用产生式来进行推导需要定义一个新的关系符号?。设G = (V, T, P, S)是一个CFG，?A?是一个包含终结符号和变元的串，其中A是一个变元，也就是说，α和β是都是(V∪T)*中的串，而A属于V。如果A?γ是G的一个产生式，那么我们称?A?????。如果G是上下文已知的，那么就可以把它省略掉，而仅仅记做

G?A?????。注意：在推导的每一步中都可以替换串中任何位置的任何一个变元，只要

用该变元的任何一个产生式的体替换该变元即可。

进一步可以把?符号推广到能够表示零步、一步或者多步推导，就像有穷自动机的转

?移函数?被推广到?一样。在推导中，用一个*来表示“零步或多步”，如下：

?基础：对任何由终结符号和变元组成的串α都有???，也就是说，任何串都能推导出它

G自己。

归纳：如果???并且???，则???。也就是说，如果α经过零步或多步推导可以得

GGG???到β，而β经过零步或多步推导可以得到γ，那么α就可以推导出γ。另一种解释，

???意味着存在一个串的序列γ1，γ2，…，γn，n≥1，满足

G?1. α ＝γ1， 2. β ＝γn，

3. 对于i = 1, 2, …, n – 1，有γi?γ

?i +1 。

如果文法G是已知的，我们可以用?来代替? 。

G?例5.5：推断a?(a?b00)属于变元E所代表的语言的过程可以用一个从串E开始的对该串的推导来给出，下面就是一个这样的推导：

E?E?E?I?E?a?E? a?(E)?a?(E?E)?a?(I?E)?a?(a?E)?a?(a?I)?a?(a?I0)?a?(a?I00)?a?(a?b00)在第一步中，用产生式3（图5.2）的体来替换E。在第二步中，产生式1体中的I被用来替换第一个E，依次类推。值得注意的是，在替换时我们系统地采用了总是替换串中最左边变元的策略。然而在每一步中，其实我们可以选择要被替换的变元，也可以使用任何一个该变元的产生式的体来替换它。例如，在第二步中，可以用(E)来替换第二个E（凭借产生式4），如果这样做的话，就可以得到E?E?E?(E)。也可以选择一个甚至永远 12

原文误为“标识符”——译者注 原文误为“标识符”——译者注

习题5.1.6：递归定义关系符号?，其中递归基础为“???”，递归定义为“如果有

????和???，则有???”。还有很多定义?的方法与定义“?是一步或多步的?”的效果是一样的。证明下列陈述都是正确的：

a) ???当且仅当有一个包含一个或多个串的序列：

??????1,?2,?,?n

满足???1，???n，并且对于i?1,2,?,n?1都有?i??i?1。

b) 如果有???和???，那么就有???。提示：使用归纳法，对推导???中的步数进行归纳。 ! 习题5.1.7：考虑定义了下面产生式的CFG G：

S ? aS | Sb | a | b

a) 通过对串的长度进行归纳，证明任何L(G)中的串都没有ba这个子串。 b) 非形式化地来描述L(G)，用(a)来证明你的结论。 !! 习题5.1.8：考虑定义了下面的产生式的CFG G：

S ? aSbS | bSaS | ε

证明L(G)是所有有相同个数的a和b的串的集合。

????5.2 语法分析树

推导有一种非常有用的树型表示——“语法分析树”，这种树能够清楚地告诉我们终结符号串中的符号是怎样组成子串的，这些子串属于文法中某个变元的语言。更重要的是在编译器设计中语法分析树是一种可以用来表示源程序的重要的数据结构。在编译器中，把源程序表示成树结构能够有助于用自然、递归的函数来完成把源程序翻译成目标代码的工作。

在本节中，将首先介绍语法分析树，并会阐述它与推导以及递归推理之间的紧密联系。然后将会研究文法和语言的歧义性的本质，这也是语法分析树的一种重要应用。有些文法允许一个终结符号串拥有多于一棵的语法分析树，这种情况使得这种文法不适合被用来表达程序设计语言，因为它使得编译器无法判断一些源程序的结构，因而无法给该程序确定合适的目标代码。

回顾关于树的术语 我们假设你已经了解了树的概念，并且熟悉常用的关于树的术语。然而，我们还是一起回顾一下它们以加深你的印象： ? 树是一些有特定父子关系的节点的集合。每个节点至多有一个父节点，该父节点画在该节点上面，还有零个或多个子节点画在该节点下面，并且父子节点之间用线段连接。图5.4，5.5和5.6都是树的例子。 ? 有且仅有一个根节点，它没有父节点。该节点出现在树的最顶端。没有子节点的节点叫做叶节点，不是叶节点的节点叫做内部节点或内节点。 ? 一个节点的子节点的子节点的?叫做该节点的后代，一个节点的父节点的父节点的?叫做该节点的祖先。一般来说，一个节点同时也是自己的祖先和后代。 ? 一个节点的子节点按照从左到右的顺序排列和画出。如果一个节点N在另一个节点M的左边，那么所有N的后代都被排在所有M的后代的左边。

5.2.1 构造语法分析树

对于文法G = (V, T, P, S)来说，G的语法分析树是满足下列条件的树： 1. 每个内部节点的标号是V中的一个变元。

2. 每个叶节点的标号可以是一个变元、一个终结符号或者ε。并且，如果叶节点的

标号是ε，那么它一定是它父节点唯一的子节点。 3. 如果某个内部节点的标号是A，并且它的子节点的标号从左到右分别为：

X1, X2, …, Xn

那么A? X1X2?Xn一定是P中的一个产生式。注意：如果其中某个X为ε，那么X一定是A唯一的子节点，并且A?ε是P的一个产生式。

例5.9：图5.4给出了一棵语法分析树，它所使用的文法是图5.2中的表达式文法。它的根节点的标号是变元E。因为根节点的三个子节点的标号从左到右分别为E, +和E，因此在根结点处使用的产生式是E?E+E。在根节点最左边的子节点处，因为该节点只有一个标号为I的子节点，所以它使用的产生式是E?I。□

例5.10：图5.5给出的是图5.1中回文文法的一棵分析树。根节点处使用的产生式是

P?0P0，根节点的中间子节点处使用的产生式是P?1P1。注意最下面的节点使用的产生式是P?ε，并且该节点只有一个标号为ε的子节点，这也是能在分析树中使用标号为ε的节点的唯一情况。□

图5.4：表示从E推导出I+E的语法分析树

图5.5：表示从P推导出0110的语法分析树

5.2.2 语法分析树的产生

考虑任意一棵分析树，把这棵分析树所有叶子的标号按照从左到右的顺序连接起来，就可以得到一个字符串，这个字符串称作该树的产物，其实它总是根结点处的变元所能推导出来的串，这一点后面不久会给出证明。特别重要的是有一些满足以下条件的分析树：

1. 它的产物是终结符号串，即所有叶节点的标号都是终结符号或者ε。 2. 根结点的标号是开始符号。

这些分析树的产物都是相应文法的语言中的串。不久我们会证明一个文法所产生的语言恰好是所有这样的以开始符号为根、产物是终结符号串的分析树的产物。

例5.11：图5.6正是一个这样的例子：根节点的标号是开始符号，它的产物是一个终结符号串。它所基于的文法是图5.2中介绍的表达式的文法。这棵树的产物是在例5.5中推导出来的串a*(a+b00)。实际上我们将会看到，这棵分析树恰好就是那个推导的另一种表示。

图5.6：表明串a*(a+b00)在表达式文法的语言中的分析树

5.2.3 推理、推导和语法分析树

迄今为止我们介绍了几种描述一个文法怎样工作的概念，实质上它们都描述了串的同样的性质。也就是说，给定一个文法G = (V, T, P, S)，应该能够证明下面几点是等价的：

1. 通过递归推理过程能够确定终结符号串w在变元A的语言中。 2. A?w。 3. A?w。

lm???4. A?w。

rm5. 存在根结点为A，产物为w的分析树。

事实上，除了递归推理的使用被定义为仅限于终结符号串以外，所有其它的条件（存在推导、最左或最右推导、分析树）对于w为包含变元的串的等价性也都是成立的。 这些等价性需要证明，我们打算用图5.7中的顺序来证明它们。换句话说，该图中的每条弧表示我们要完成的一个证明：如果它尾部的条件成立，那么它头部的条件就一定成立。比如，定理5.12说如果w能通过递归推理得出在A的语言中，那么一定存在一棵分析树，它的根为A，产物为w。

语法分析树

最左推导

推导

最右推导

递归推理

图5.7：证明关于文法的一些等价性

注意其中有两条弧比较明显，因此就不作形式化的证明了：如果w有一个从A开始的最左推导，那么它肯定有一个从A开始的推导，因为最左推导本身同时也是推导；类似的，如果w有一个最右推导，那么它显然也有一个推导。下面会依次证明这些等价性中剩下比较难的部分。

5.2.4 从推理到树

定理5.12：设G = (V, T, P, S)是一个CFG。如果通过递归推理过程得出终结符号串w在变元A的语言中的话，那么一定存在一棵分析树，它的根为A，产物为w。 证明：对推理的步数进行归纳。

基础：若该推理只有一步，则该推理过程只需使用基础，因此一定存在产生式A?w。图5.8中的树满足成为文法G的分析树的条件，其中w的每个位置有一个叶子。显然，它的根是A，产物是w。考虑特例w =ε，那么该树只有一个标号为ε的叶子，此时同样满足根是A，产物是w的条件。

归纳：假定能够得出w在A的语言里这个结论的推理过程需要n+1步，并且对于任意语言B和其中某个串x，当推理过程小于等于n步时定理都成立。考虑得出w在A的语言里这个结论的推理的最后一步，这一步一定使用了A的某个产生式，不妨设为A?X1X2?Xn，其中Xi或者是一个终结符号，或者是一个变元。

图5.8：定理5.12的证明中基础的情况下所构造的树

我们把w打断为w1w2?wn，其中：

1. 如果Xi是一个终结符号，那么wi=Xi，即在产生式中wi只由这个终结符号组成。 2. 如果Xi是一个变元，那么wi是一个先前推理出在Xi的语言中的串。也就是说，

得出w属于A的语言的n+1步推理中，关于wi的推理至多占用了其中的n步。之所以它不能占用全部的n+1步，是因为最起码在最后一步使用的产生式是

A?X1X2?Xn，而它肯定不是关于wi的推理中的一步。因此，我们可以对wi和Xi应用归纳假设，从而得出结论：存在一个根为Xi、产物为wi的分析树。

图5.9：定理5.12的证明中归纳部分所使用的树

接下来我们构造一棵树，它的根为A并且产物为w，就像图5.9中所画的那样。根节点的标号为A，它的子节点分别为X1, X2, …, Xn。因为A? X1X2?Xn是G的一个产生式，所以这种选择是有效的。

每个节点Xi实际上是一个产物为wi的树的根节点。在情况（1）中Xi是终结符号，这棵子树就变成了一棵只有单个标号为Xi的节点的平凡树。也就是说，这棵子树仅由该根节点这一个节点构成。因为wi=Xi，所以在情况（1）中该子树的产物为wi的条件也是满足的。

在情况（2）中，Xi是一个变元。继续使用归纳假设可以得出一棵根为Xi、产物为wi

的树，且这棵树被接到节点Xi上（见图5.9）。

至此，这棵树已经构造好了，它的根节点为A，把根节点所有子树的产物从左到右连接起来就得到整棵树的产物，正好是w1w2?wn，也就是w。□

5.2.5 从树到推导

现在我们将会展示怎样从一棵分析树构造一个最左推导。最右推导的构造思想与此相同，因此我们就不再证明从分析树构造最右推导的部分了。为了帮助理解推导的构造过程，我们首先来看看从一个变元到一个串的某个推导怎样能够被嵌入到另一推导当中。有一个例子可说明这件事情。

例5.13：再一次考虑图5.2中表达式的文法。很容易验证存在这样的一个推导：

E?I?Ib?ab

推而广之，对任意的串α和β，下面的推导也都成立：

?E???I???Ib???ab?

理由是这种用产生式的体来替换头的方法既可用在单独的变元上，也可用在任意的上下文α和β中。1

例如，如果有这样一个推导，它的开头两步是E?E?E?E?(E)，那么就可以把“E+(”看作α，把“)”看作β，然后对中间的E应用上面关于ab的推导，因而可以得到：

E?(E)?E?(I)?E?(Ib)?E?(ab)

□

现在就可以着手证明能够把分析树转换成最左推导的定理了。证明是通过对树的高度进行归纳完成的，其中树的高度是指从根节点顺着父子关系到叶节点的最长的路程。例如，图5.6中树的高度是7，最长的根到叶子的路径是到标号为b的叶子的路径。注意，习惯上路径长度计算的是该路径上的边数，而不是顶点数，因此一个单个节点的路径的长度为0。

定理5.14：设G = (V, T, P, S)是一个CFG。假设有一棵分析树，它的根的标号为变元A、产物为w，其中w属于T*。那么一定存在一个文法G中的最左推导A?w。

lm?证明：对树的高度进行归纳。

基础：归纳基础是高度为1的树，1是产物为终结符号串的树高的最小值。在这种情况下，这棵树一定和图5.8中的树类似，根节点的标号为A，而且它的子节点从左到右连起来为w。由于这棵树是一棵分析树，因此A?w一定是一个产生式。因此，A?w是从A

lm到w的一个单步完成的最左推导。

归纳：如果树的高度是n，其中n>1，它一定和图5.9中的树类似。换句话说，根节点的标号为A，它的子节点的标号从左到右分别为X1，X2，…，Xk，其中这些X可以是变元和终结符号。

1. 如果Xi是终结符号，定义wi为只包含Xi的串。

2. 如果Xi是变元，那么它一定是某个产物为终结符号串wi的子树的根节点。注意在

这种情况下，这棵子树的高度一定小于n，因此可以对它使用归纳假设。即，存在

一个最左推导Xi?wi。

lm?注意，w=w1w2?wn。

下面我们构造一个w的最左推导。首先由A?X1X2?Xk开始，接着对于

lmi=1,2,…,k，依次证明

A?w1w2?wiXi?1Xi?2?Xk

lm? 1

事实上，术语“上下文无关”正是由于这种无需考虑上下文就能进行的串对变元的替换才得来的。另外还有一类更强的文法，它们是“上下文相关”的，这种文法中的替换只有当一定的串出现在被替换的串的左边和（或）右边时才能进行。当前，上下文相关文法在实际应用中并不占主导地位。

这部分的证明实际上是另外再使用一个归纳法，不过这次是对i进行归纳。归纳基础是：i=0时已知的A?X1X2?Xk。归纳部分是：假定

lmA?w1w2?wi－1XiXi?1?Xk

lm?a) 如果Xi是终结符号那就什么都不做。然而，下一步中把Xi看作终结符号串wi。从而可以得到

A?w1w2?wiXi?1Xi?2?Xk

lm?b) 如果Xi是变元，那么继续从Xi到wi的推导，不过这次使用已经构造好的推导的上下文。换句话说，如果该推导为

Xi??1??2??wi

lmlmlm我们就继续下面的推导

w1w2?wi?1XiXi?1?Xk?lmw1w2?wi?1?1Xi?1?Xk?lmw1w2?wi?1?2Xi?1?Xk?

lm?w1w2?wi?1wiXi?1?Xk这个结果就是需要的推导A?w1w2?wiXi?1Xi?2?Xk。

lm?当i = k时，这个结果就是从A到w的最左推导。□

例5.15：我们来构造图5.6中的分析树的最左推导。我们只展示最后一步：在已经把根节点的所有子树所对应的推导都构造好了的前提下，剩下要做的工作只是给出整个树所对应的推导。也就是说，假设通过递归地使用定理5.14中的技术，已经得到了以根节点的第一个子节点为根的子树对应的最左推导E?I?a，同时得到了以根节点的第三个子节点为

lmlm根的子树对应的最左推导

E?(E)?(E?E)?(I?E)?(a?E)?lmlmlmlmlm(a?I)?(a?I0)?(a?I00)?(a?b00)lmlmlm

为了构造整棵树的最左推导，首先在根处使用A?E*E，然后把其中第一个E用它

lm的推导所代替，并且在每步中都用*E作为下文。这样得到的最左推导为

E?E*E?I*E?a*E

lmlmlm在根处使用的产生式中的*不用推导，所以上面的最左推导也是根节点的前两个子节点所对应的最左推导。为了完成整个最左推导，接着使用推导E?(a?b00)，并且在每步中

lm?都把a*加在前面，后面再加上一个空串。这个推导实际上在例5.6中已经出现过了，就是：

E?E?E?I?E?a?E?lmlmlmlma?(E)?a?(E?E)?a?(I?E)?a?(a?E)?lmlmlmlm

a?(a?I)?a?(a?I0)?a?(a?I00)?a?(a?b00)lmlmlm□

类似的，有一个定理可以保证把分析树转化为最右推导。从树构造最右推导的过程和最左推导的构造过程几乎完全相同。只是，在第一步A?X1X2?Xk开始后，先使用最

rm右推导扩展Xk，然后Xk-1等等，最后才是X1。我们就不给出进一步的证明了。

定理5.16：设G = (V, T, P, S)是一个CFG。假设有一棵分析树，它根的标号为变元A、产物为w，其中w属于T*。那么一定存在一个文法G中的最右推导A?w。□

rm?5.2.6 从推导到递归推理

现在距离完成图5.7中的整个环路只差这一点了：如果对某个CFG有一个推导

A?w，那么一定可以通过递归推理过程得出w在A的语言中的结论。在给出相应的定理

和它的证明之前，首先看看推导的一些重要性质。

假设存在一个推导A?X1X2?Xk?w，那么一定可以把w打断成w=w1 w2 ?wk

使得Xi?wi。注意如果Xi是终结符号，那么wi=Xi，并且该推导只有零步。这个发现的证明并不难，只要对推导的步数进行归纳就行了。即如果X1X2?Xk??，那么对于任意的i < j，α中所有由Xi扩展来的位置一定在所有由Xj扩展来的位置的左边。

如果Xi是一个变元，那么就可以通过如下方法获得推导Xi?wi：首先从推导

?????A?w开始，然后去掉以下的：

a) 所有在句型中由Xi推导出的部分的左边和右边的位置， b) 所有和从Xi推导出wi无关的步骤， 为了看清这个过程，有一个例子：

例5.17：对于图5.2中的表达式文法，考虑如下推导：

?E?E?E?E?E?E?I?E?E?I?I?E?

I?I?I?a?I?I?a?b?I?a?b?a考虑其中第三个1句型E*E+E和该句型中间的那个E。

从E*E+E开始，按照上面推导中的步骤，但是要去掉所有由中间的E左边的E*和右边的+E所推导出来的位置。那么上面推导中的这些步骤就变成了E,E,I,I,I,b,b。也就是说，下一步中并没有改变中间的E，在接下来的一步中把它变成了I，然后的两步中保持为I不变，接着把它变成b并且在最后一步中保持不变。

如果只考虑从中间那个E的推导中变化的部分，那么序列E,E,I,I,I,b,b就变成了推导E?I?b。这个推导准确地刻画了中间的E在整个推导过程中的变化情况。

定理5.18：设G=(V, T, P, S)是一个CFG。假设有一个推导A?w，其中w属于T*。那么

G?应用于G的递归推理过程决定了w在变元A的语言中。 证明：对推导A?w的长度进行归纳。

基础：如果该推导只有一步，那么A?w一定是一个产生式。由于w只包含终结符号，因此由递归推理过程的基础部分就可以得出w在A的语言中。

归纳：假设该推导包含n+1步，并且假定对于所有少于或等于n步的推导来说结论都成立。把推导写为A?X1X2?Xk?w。然后，根据先于该定理的讨论，我们可以把w打断为w=w1w2?wn ，其中：

a) 如果Xi是终结符号，则wi = Xi 。

b) 如果Xi是变元，那么有Xi?wi。因为推导A?w的第一步肯定不是推导

????Xi?wi中的一部分，因此我们知道这个推导只有少于等于n步。因此，对它使用归纳假

设可以推理出wi在Xi的语言中。

现在已经有了产生式A?X1X2?Xk，其中wi或者等于Xi或者可知在Xi的语言中。在下一轮的递归推理过程中，就可以知道w1w2?wk在A的语言中。因为w1w2?wk=w，因此可以推理出w在A的语言中。□

?5.2.7 5.2节习题

习题5.2.1：对于习题5.1.2中的文法和每个串，给出相应的分析树。

! 习题5.2.2：假设G是一个CFG，并且它的任何一个产生式的右边都不是ε。如果w在L(G)中，w的长度是n，有一个m步完成的w的推导，证明有一个包含n+m个节点的关于w的分析树。

1

在讨论从大的推导过程中找出一些子推导过程时，假定我们所关心的是一些推导的第二个句型中的变元。然而，这种思想对于一个推导中的任何一步中的变元都是成立的。

! 习题5.2.3：假设在习题5.2.2中除了G中可能有右端为ε的产生式外其它所有的条件都满足，证明此时w的分析树有可能包含n+2m-1个节点，但不可能更多了。

! 习题5.2.4：在第5.2.6节中提到了如果X1X2?Xk??，那么对于任意的i

?5.3 上下文无关语言的应用

上下文无关文法最初是由乔姆斯基（N.Chomsky）所构想出用来描述自然语言的，这个愿望还没有被实现。然而，由于计算机科学中递归定义的概念被频繁地使用，所以把CFG作为用来描述这些概念实例的方法也很有必要。下面将粗略地给出众多应用中的两个，一个较老的应用和一个比较新的应用。

1. 用文法来描述编程语言。比这更重要的在于，存在着机械化的方式把用CFG描述

了的语言变为分析器，分析器是编译器的一部分，它用来发现源程序中的结构并且把该结构表示成为分析树。这是最早使用CFG的应用之一，事实上它也是最早把计算机科学中的理论付诸于实践的方法之一。 2. 人们普遍认为XML（eXtensible Markup Language 可扩展标记语言）能够促进电子

商务的发展， XML能够帮助参与电子商务的双方在定单、产品描述以及许多其它方面的文档中采用规范、通用的格式。XML中最为精华的部分就是DTD

（Document-Type Definition 文档类型定义），而它实质上就是一个上下文无关文法，只不过该文法描述了哪些是文档中允许出现的标记符（Tag）以及这些标记符在文档中能够怎样地嵌套起来。标记符是一些用尖括号括起来的常见的关键字，你可能在HTML中见过它们，例如：和所括住的文本是需要强调的。不过，XML的标记符不是用来控制文本的格式的，而是和文本的含义有关。例如，如果你想要表示一些字符是电话号码，你就可以用和来括住它们。

5.3.1 语法分析器

编程语言在许多方面通常都有能用正则表达式描述的结构。例如，例3.9中讨论的标识符就能够用正则表达式来刻画。然而，典型的编程语言中也都有一些无法仅用正则表达式就能表达的非常重要的方面。下面就是两个例子。

例5.19：典型的编程语言中都使用括号，并且一般都是嵌套地、匹配地使用。所谓匹配就是说：找到一个左括号和一个在它后面且紧跟着它的右扩号，同时去掉这两个括号，并且重复这个过程，那么最终应该能够去掉所有的括号。如果在这个过程中找不到一对匹配的括号了，那么这个串中的括号就是不匹配的。括号匹配的串如：(()), ()(), (()())和ε，不匹配的如：)(和(()。

有一个文法Gbal = ({B}, {(, )}, P, B)刚好能够生成所有的括号匹配的串，其中P包含如下的产生式：

B ? BB | (B) | ε

其中第一个产生式B?BB是说：把两个括号匹配的串连接起来得到的串仍然是括号匹配的。这样的断言是有道理的，因为我们可以分别对这两个串进行匹配。第二个产生式B?(B)是说：把一个括号匹配的串用一对括号括起来所得到的串仍然是括号匹配的。同样这样的断言也是有道理的，因为如果中间的串是匹配的，那么把它里面所有的括号都去掉后就只剩下最外边的一对括号了，而此时它们仍然是匹配的。第三个产生式B?ε是基础，它是说空串是括号匹配的。

上面这段非形式化的论证应该能够使人相信Gbal产生的确实是所有的括号匹配的串。反过来的方向需要证明——也就是每个括号匹配的串都能够由该文法产生。不过，这个证明并不难，只需要对括号匹配的串的长度进行归纳就行了，因此我们把该证明的细节留给读者作为练习。

前边曾经提到过所有括号匹配的串组成的语言不是正则语言，现在应该来证明这件事情了。如果L(Gbal)是正则的，那么根据正则语言的泵引理，一定存在一个和该语言相关的常数n。考虑括号匹配的串w=(n)n，也就是n个左括号后面跟着n个右括号。如果根据泵引理把w打断为w=xyz，那么y只包含左括号，因此串xz中右括号就比左括号多了，因而xz不是括号匹配的，这跟括号匹配的串的语言是正则语言的假设相矛盾。 □

当然，除了括号之外，编程语言中还包含许多其它的东西，但是括号确实是算术或条件表达式中一个基本的组成部分。虽然图5.2中的文法中只有两个运算符：加号和乘号，但它仍然是算术表达式的非常典型的结构。并且它包含了详细的标识符的结构，该结构使用第3.3.2节中提到的编译器的词法分析部分来进行处理可能是比较适合的。然而，图5.2中描述的这个语言也不是正则的。例如，在这个语言中，(na)n是合法的表达式。可以通过泵引理来证明：如果这个语言式正则的，那么去掉一些左括号同时保持a和所有的右括号不动，这样得到的串应该仍然是表达式，然而实际上不是。

典型的编程语言中有很多方面跟括号匹配很相似。一般来说它们本身也是括号，不过可以在各种类型的表达式中。例如一个代码块的开始和结束，就像Pascal语言中的begin和end，或者C语言中的花括号{…}。也就是说如果把C程序中的花括号替换为圆括号，即把{换为(，把}换为) ，这样所得到的串一定是括号匹配的。

有时会出现另外一种相关的情况，只不过在这时“括号”匹配时不考虑未被匹配的左括号。比如C语言中处理if和else的时候，一个if子句可以不和else子句匹配而单独存在，也可以和一个else子句匹配。一个生成所有这样可能的if和else的序列的文法是：（其中if和else分别用i和e来代替）

S ? ε| SS | iS | iSe

例如，ieie, iie和iei都是可能的if和else的序列，而且都是用上面的文法生成的。也有一些不能用该文法生成的非法串，比如ei和ieeii。

对于一个由i和e组成的串是否能有该文法生成，有一个简单的测试方法——只需要从左边开始依次检查每个e即可，具体方法如下（该方法正确性的证明留给读者作为练习）：在这个e的左边找到第一个i，如果找不到的话，那么这个串就无法通过该测试，因而得出它不在该语言中的结论。如果找到了这个i，那么就把它和正在被检查的e一起去掉，然后继续重复这个过程：如果没有e了，那么这个串就通过了这个测试，因而得出它在该语言中的结论。如果还有e，那么就继续对最左边的e进行上面的检查过程。 例5.20：考虑串iee，第一个e和是它左边的i匹配，把它们去掉后该串变成了e。由于还有e，因此我们得继续进行检查，但这次没有i在它左边了，因此检查测试失败了，所以iee不在该语言中。注意这个结论是正确的，因为在C程序中else的个数不可能比if多。

再来一个例子，考虑iieie。第一个e是跟它左边的i匹配的，把它们去掉后还剩下iie。这个e继续和它左边的i匹配，再把它们去掉后还剩下i，这时没有e了，因此测试成功通过。这个结论也是有道理的，因为iieie所对应的C程序的结构就像图5.10中的结构。事实上，这个匹配算法同时也能告诉我们（及编译器）每个if所匹配的的else（如果有的话）到底是哪个，而这一点是很重要的，因为编译器需要创建程序员所设计的控制流逻辑。□

if （条件）{

…

if （条件）语句； else 语句； …

if （条件）语句； else 语句； … }

图5.10：一个if-else结构，其中的两个else分别和它们前面的if匹配，第一个if没有else和它匹配。

5.3.2 语法分析器生成器YACC

语法分析器是从源程序中创建语法分析树的函数，它的生成过程已经被所有的UNIX系统中都有的YACC命令所规范化了。YACC的输入是一个CFG，并且该CFG的具体表示方法和我们这里所用到的只在具体细节上有所不同。每个产生式都和一个动作相关联，而这个动作是一个C代码的片段。当语法分析树的一个节点（和它的子节点）被创建时，它们相应产生式所对应的这段C代码就被执行。一般的，动作是用来构造这个节点的代码，尽管在一些YACC应用中语法分析树实际上并没有真正的被构造出来，这时该动作就做一些别的事情，比如生成一段目标代码。

例5.21：图5.11是一个YACC中的CFG的例子。这个文法和图5.2中的是一样的。我们把动作部分省略掉了，展现出来的仅仅是它们（需要的）花括弧和它们在YACC输入中的位置。

图5.11：一个YACC中的文法的例子

注意下面是YACC和我们文法表示法的一些对应部分：

? 冒号被用来作为产生式的符号，我们的是?

? 所有具有同样的头的产生式都被编为一组，并且它们的体互相之间用竖线分隔开

来。我们也使用这种表示法，但不是必须的。 ? 同一个头所对应的体的列表靠一个分号来结束。我们没有使用这样的结束符号。 ? 终结符都用单引号引起来。很多字符都能被一对单引号引起来。虽然我们没有展

现出来，YACC允许它的用户自己定义终结符号。在源程序中出现的这些终结符号能被词法分析器检测和分离出来，并且通过它的返回值传递给语法分析器。 ? 没有被引起来的字母和数字组成的串是变元名。我们已经通过这个方法来赋予上

面两个变元更加有意义的名字——Exp和Id——虽然它们也能用E和I 来表示。

5.3.3 标记语言

下面我们将会考虑一系列的“语言”，它们叫做标记语言。这些语言中的“串”是使用了一些该语言中的标记符（tags）的文档。标记符告诉我们一些该文档中不同串的语义。

有一个你可能最熟悉的标记语言：HTML（超文本标记语言，HyperText Markup Language）。这个语言有两个主要的功能：在文档之间建立链接和定义一个文档的格式（“样子”）。我们只给出一个关于HTML结构的简单看法，但是下面的例子能够展示它的结构，也能够展示一个CFG是怎样描述合法的HTML文档的，还能够展示CFG是怎样在文档的处理过程（即文档在显示器和打印机上的显示）中起到引导作用的。

我讨厌的东西： 1. 发霉的面包。

2. 在快车道上开的很慢的人。

（a） 显示的文本

我讨厌的东西：

发霉的面包。

在快车道上开的很慢的人。

（b） HTML源码

图5.12：一个HTML文档和它的印刷版本

例5.22：图5.12（a）展示了一段文字，它包括了一个项目列表，图5.12（b）展示了它在HTML中的表达。注意从图5.12（b）可以看出HTML是由普通的问题掺杂着一些标记符组成的。对某个标记符x的匹配1是采用和的形式完成的。例如，互相匹配的标记 1

有时标记符的引入不仅仅有名字x的信息，还会有更多其它的信息。然而，在这些例子中我们不考虑这种情况。

和是用来表示它们之间的文字是需要强调表示的，也就是要把它们改为斜体字或者其它合适的字体。

和

这对互相匹配的标记符是用来表示一个有序列表的，也就是说一些项目或条款的列举。

另外还有两个不匹配使用的标记符的例子：

和，它们分别表示段落和项目列表。HTML允许（事实上鼓励）这些标记符也用

和匹配起来（分别通过在段落处和列表的结尾处使用它们），但是这种匹配不是必须的。因此我们就不匹配这些标记符了，这样的话下边将要考虑的HTML的文法就会更复杂一些了。□

有许多类的串和HTML文档相关。这里不把它们全都列出来了，而是仅仅给出那些对理解例5.22中的文本有关键作用的一些，并且对于其中的每一类都给出了一个具有描述性的名字的变元。

1. Text是任何有字面意义的字符串，也就是说它里面没有标记符。一个Text元素的

例子是图5.12（a）中的“Moldy bread.” 2. Char是任何只包含单个的、在HTML文本中合法字符的串。注意空格也算作字

符。 3. Doc代表文档，它是“Element”的序列，下面会给出Element的定义，并且这个

定义和Doc的定义是互归纳的。 4. Element或者是一个Text串，或者是一对互相匹配的标记符以及它们中间的文档，

或者是一个不匹配的标记符后面跟着一个文档。 5. ListItem是标记符后面跟着一个文档，并且该文档是一个项目列表。 6. List是包含零个或多个项目或条款的序列。

图5.13：HTML文法的一部分

图5.13是一个CFG，它描述了我们所介绍的HTML语言中的各种结构。在第1行中它说明了一个字符可以是“a”或者“A”或者很多其它可能的HTML字符集中的字符。第2行中它用两个产生式说明Text可以是空串或者任何由合法字符后面跟着一些文本构成的串。换句话说，Text就是零个或多个字符。注意虽然‘<’和‘>’可以分别用序列<；和>；来表示，但它们并不是合法字符。总之，绝对不可能在Text中找到标记符。 第3行是说一个文档是包含零个或多个“element”的序列。接着从第4行知道一个element或者是text，或者是强调了的文档，或者是段落开始符号后面跟着一个文档，或者是一个列表。另外对于HTML中其它的标记符也有相应的不同的Element的产生式。接着，第5行说一个ListItem是由标记符和它后面跟着的任何的文档组成的。第6行说一个List是零个或多个ListItem的序列。

HTML的有些方面的说明并不需要上下文无关文法的能力，在这些方面用正则表达式就足够了。比如，图5.13的第1行和第2行可以用正则表达式(a + A + ?)*来表示和Text表示的同样的语言。然而，HTML的有些方面确实需要CFG的能力。例如，每一对包含开

始和结束符号的标记符（比如和），就像括号匹配一样，是我们已知的非正则的。

5.3.4 XML和文档类型定义

能用文法来描述HTML倒不算什么，事实上所有的编程语言都可以用和它们相应的CFG来描述，因此如果不能描述HTML的话反倒令人惊讶了。然而，当我们考虑另外一类重要的标记语言XML（eXtensible Markup Language 可扩展标记语言）时，将会发现在使用这个语言的过程中，CFG扮演着至关重要的角色。

XML的目的不是描述文档的格式——那是HTML的工作，而是试着描述文本的“语义”。比如，像“枫树大街12号”这样的文本看上去像一个地址，但是它是吗？在XML中，代表一个地址的短语往往用标记符围起来，例如：

枫树大街12号

然而，对于是否意味着一幢建筑这件事情并不是很清楚。例如，如果这个文档是关于内存分配的，那么标记符可能会表示一个内存地址。为了把这些不同类型的标记符区别开来，人们希望开发一个标准，该标准采用DTD（Document-Type Definition 文档类型定义）的形式。

一个DTD本质上就是一个上下文无关文法，不过有着它自己的用来描述变元和产生式的表示法。下面的例子将会展示一个简单的DTD，并且会介绍用来描述DTD的语言的一部分。DTD语言本身有一个上下文无关的文法，但它并不是我们感兴趣和要描述的。然而，用来描述DTD的语言本质上是用一个CFG表示的，我们想知道在这个语言中CFG是怎样表达出来的。

一个DTD的定义是这样的

其中element是依次定义的，一个element定义是这样的

element的描述实质上是正则表达式。这些正则表达式的组成部分有：

1. 其它element的名字，表示一个类型的element可以出现在另一个类型的element里面，就像在HTML中一个文本列表里可以有强调的文本一样。 2. 特殊的术语 \\#PCDATA，代表任何不包含XML标记符的文本。这个术语和例5.22中变元Text的角色相同。 允许的操作符有：

1. | 代表合并，就像第3.3.1节中所介绍的UNIX的正则表达式的表示法中的那样。

element定义的列表

2. 逗号代表连接

3. 闭包运算有三种，就是第3.3.1节中所介绍的。它们有：*，最常用的运算符表示“零次或多次出现”；+，表示“一次或多次出现”；?，表示“零次或一次出现”。

并且用括号把运算符和它们的参数组合起来，否则如果没有括号的话，就采用通常的正则表达式的优先级。

例5.23：考虑下面的情况：假设计算机销售商们凑到一起想要建立一套DTD的标准，这套标准是用来在Web上发布他们正在销售的各种PC的介绍。每种PC的介绍将会给出一个型号，以及这个型号的特性的细节描述。例如RAM的大小，DISK的数目和大小等等。图5.14展示了一个假想的、非常简单的刻画个人计算机的DTD。

]>

图5.14：一个刻画个人计算机的DTD

这个DTD的名字是PcSpecs。第一个element（就像CFG的开始符号）是PCS（关于PC规格的列表）。它的定义部分是PC*，是说一个PCS包含零个或多个条目，每个条目都是PC。

接下来的是element PC的定义，它由五部分连接而成。其中前四部分是其它的

element，分别对应着型号、价格、处理器类型和PC的RAM。由于逗号表示连接，因此这几部分必须刚好出现一次，并且还得按照顺序出现。最后一个组成部分是DISK+，表示一个PC中可以有一个或多个DISK。

很多组成部分都是简单的文本：型号，价格和RAM都是这样的。但是处理器是有结构的，从它的定义可以看出来它由生产厂家、型号和速度这三部分按顺序构成，这三部分都是简单的文本。

DISK的结构最为复杂。首先，一个DISK可以是一个硬盘、CD或者DVD，这从

element DISK的定义可以看出来，DISK定义为这三者的“或”。其次，硬盘也由三个部分按顺序构成，它们分别是生产厂家，型号和大小；而CD和DVD仅仅由它们的速度来代表。

图5.15是一个使用图5.14中的DTD的XML文档的例子。注意到在这个文档中，每个element都用两个标记符来表示，其中一个以它为名字，另一个在结束处和它对应。其中表示结束的标记符不过是在该element的名字前面加了一个斜杠而已，这和HTML中是一样的。从而，在图5.15中可以看到最外层的标记符是…。这个标记符里面是一系列的条目，每一个都是该生产商所销售的PC，这里仅展示出来其中的一个条目。

<型号>4560 <价格>$2295 <处理器>

<生产厂家>Intel <型号>Pentium <速度>800MHz

256 <硬盘>

<生产厂家>Maxtor <型号>Diamond <大小>30.5Gb

<速度>32x

…

图5.15：一个遵照图5.14中DTD结构的文档的一部分

通过例中的条目，我们可以很容易的看到机器的型号是4560，价格是$2295，处理器是800MHz Intel Pentium 处理器。它有256Mb的RAM，一个30.5Gb的Maxtor

Diamond硬盘和一个32x的CD-ROM驱动器。其实最重要的并不是我们能看到这些东西，而是程序能够读取这个文档，并且能够根据图5.14中的DTD的文法来正确的解释图5.15中所有的数字和名字。□

你可能已经注意到了，图5.14中这样的DTD中定义element的规则看上去和上下文无关文法的产生式并不是很像。这些规则中的一大部分已经是正确的形式了，例如

和下面这个产生式很类似

处理器 ? 生产厂家 型号 速度

然而，下面这条规则

其中定义DISK的部分并不像一个产生式的体。既然这样，推广的方法很简单：只要把这条规则解释成为三个产生式，它们拥有同样的头，而它们的体用竖杠连接起来，这里竖杠的作用和规则中的相同。因此，这条规则和下面的三个产生式等价

DISK ? 硬盘 | CD | DVD

最难转换的一种情况是

其中“体”里有一个闭包运算。解决的方法是把DISK+用一个新的变元Disks来代替，并且通过一对产生式来表示变元Disk的一个或多个实例。等价的产生式是

PC ? 型号 价格 处理器 RAM Disks Disks ? Disk | Disk Disks

有一个通用的方法能够把产生式体中包含正则表达式的CFG转换成普通的CFG。这里先非形式化的给出它的思想：你也许希望不仅仅把产生式体中包含正则表达式的CFG变成正规的CFG，并且能够证明经过这样的扩展变换之后并没有产生超出这个CFL之外的新的语言。下面将会归纳地给出把体中包含正则表达式的产生式变成一系列和它等价的普通的产生式。这个归纳是对产生式体中的正则表达式的大小来进行的。

基础：如果产生式的体是几个element的连接，那么这个产生式已经是合法的CFG的产生式的形式了，因此什么都不用做了。

归纳：否则，将根据最后使用的运算符来采取下面五种情况下的方案之一。

1. 该产生式是A?E1, E2的形式，其中E1和E2都是DTD语言中允许的表达式，这是

一个连接的情况。引进两个新的变元B和C，并且它们不能在该文法的其它地方出现。把A?E1, E2替换为下面的一组产生式：

A ? BC B ? E1 C ? E2

其中第一个产生式A?BC是合法的CFG的产生式，后面两个有可能并不是合法的（当然也可能是合法的）。然而它们的体要短于原来的产生式的体，因此只要继续应用归纳的过程来把它们转换为CFG的形式就行了。

2. 该产生式是A?E1 | E2的形式。对于并运算，把这个产生式用下面的一对产生式来

代替：

A ? E1 A ? E2

同样，这些产生式也可能是或者不是合法的CFG产生式，但是它们的体一定比原来的产生式的体要短。因此只要递归的应用转换规则就可以把它们编为符合CFG形式的新的产生式了。

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节中将会展示一个上下文无关语言，对它而言只存在歧义的文法，根本不存在无歧义文法。对这样的语言来说，去除它的歧义性是不可能的。

幸运的是，在实际应用中这种情况并不很严重。对于一般的编程语言中的结构所对应的文法来说，可用一种熟知的方法来消除其中的歧义性。图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+(a*b)，a*b+a1为(a*b)+a1。 3.

今后表达式是指任何可能的表达式，其中包括可以被相邻的加号或乘号打断的表达式。因此，我们例中的表达式就是一个或多个项的和。

图5.19：一个无歧义性的表达式文法

例5.27：图5.19展示了一个无歧义性的表达式文法，它和图5.2中的文法所产生的是同样的语言。考虑F，T和E，它们的语言分别是上文中定义的因子，项和表达式。例如，对于串a+a*a，该文法只允许有一棵分析树，就像图5.20中的那样。

图5.20：a+a*a的唯一的语法分析树

关于这个文法是无歧义性的事实还不算很明显，下面是一些关键的发现，它们能够解释为什么在这个语言中的串不可能拥有两棵不同的分析树。

? 从T推导出的串都是项，它们一定是一个或多个用*连接的因子。我们定义的因

子，在图5.19中就是F的产生式所定义的，它或者是标识符或者是一个用括号括起来的表达式。 ? T的两个产生式的形式能够决定一序列的因子的分析树只能是把f1*f2*?*fn (n>1)

打断为项f1*f2*?*fn-1和因子fn。原因是从F无法推导出项fn-1*fn这样的表达式，除非把它们用括号括起来。因而，当使用产生式T?T*F时F除了最后一个因子之外不可能推导出别的东西。也就是说项的分析树只能是类似于图5.21中那样的。 ? 同样的，一个表达式就是用+连接起来的一系列的项。当我们使用产生式E?E+T

来推导t1+t2+?+tn时，T只能推导出tn，体中的E只能推导出t1+t2+?+tn-1。原因同样是：如果不使用括号的话，T是不可能推导出两个或多个项的和的。

图5.21：一个项的所有可能的分析树的样子

5.4.3 最左推导作为表达歧义性的一种方式

即使当文法是无歧义的时候，推导也有可能不唯一。但下面的结论总是成立的：在无歧义的文法中，最左推导是唯一的，最右推导也是唯一的。我们只考虑最左推导，最右推导只给出结论。

例5.28：作为一个例子，注意图5.18中的两棵产物为E+E*E的分析树。如果从它们出发，我们将会分别得到两棵树(a)和(b)的最左推导如下：

E?E?E?I?E?a?E?a?E*E?a?I*E?a?a*E?a)

lmlmlmlmlmlmlma?a*I?a?a*alm

E?E?E?E?E*E?I?E*E?a?E*E?a?I*E?a?a*E?b)

lmlmlmlmlmlmlma?a*I?a?a*alm

注意这两个最左推导并不相同。这个例子并不能证明下面的定理，但它说明了树的不同导致了最左推导的不同。

定理5.29：对于任何文法G=(V,T,P,S)和T*中的串w，w有两棵不同的分析树当且仅当从S到w有两个不同的最左推导。

证明：（必要性）如果检查定理5.14中从分析树构造最左推导的过程，我们会发现只要两棵分析树中有一个（第一个）节点，在该节点处使用了不同的产生式，那么在构造最左推导时就会使用不同的产生式，因而得到了不同的最左推导。

（充分性）虽然前面并没有给出一个直接从最左推导构造分析树的方法，但是它的思想并不难。首先从根节点开始构造分析树，并把根节点的标号设为S。然后每次检查推导中的一步。在每一步中会有一个变元被替换，因此这个变元就对应于正在被构造的分析树中最左边的没有子节点但是标号为变元的节点。由最左推导中这一步所使用的产生式，可以决定这个节点的子节点分别是什么。如果有两个不同的推导，那么在这两个推导第一次发生不同的地方，所被构造的节点将会得到不同的子节点的列表，这也保证了所构造的分析树是不同的。

5.4.4 固有的歧义性

我们说一个上下文无关的语言L是固有歧义的，如果它的所有的文法都是歧义的。只要L有一个文法是无歧义的，那么L就是无歧义的。例如，我们说图5.2中的文法所生成的表达式的语言实际上是无歧义的。即使这个文法是歧义的，存在另外一个无歧义的文法和它生成同样的语言——图5.19中的文法。

我们将不去证明固有歧义语言，而是给出一个语言的例子，能够证明它是固有歧义的，我们将会直观的解释为什么任何关于它的文法都是歧义的。这个将要讨论的语言是：

L?{anbncmdm|n?1,m?1}?{anbmcmdn|n?1,m?1}

也就是说，L包含所有满足下列条件的a+ b+ c+ d+形式的串：

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

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

本文来源：https://www.bwwdw.com/article/gj5p.html