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

习题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的证明中基础的情况下所构造 …… 此处隐藏：2678字，全部文档内容请下载后查看。喜欢就下载吧 ……