发布时间 : 星期日 文章上下文无关文法与语言更新完毕开始阅读
图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
事实上，术语“上下文无关”正是由于这种无需考虑上下文就能进行的串对变元的替换才得来的。另外还有一类更强的文法，它们是“上下文相关”的，这种文法中的替换只有当一定的串出现在被替换的串的左边和（或）右边时才能进行。当前，上下文相关文法在实际应用中并不占主导地位。