理由是这种用产生式的体来替换头的方法既可用在单独的变元上，也可用在任意的上下文α和β中。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) | ε