上下文无关文法与语言(4)

理由是这种用产生式的体来替换头的方法既可用在单独的变元上，也可用在任意的上下文α和β中。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的语 …… 此处隐藏：3449字，全部文档内容请下载后查看。喜欢就下载吧 ……