第 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

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