文法证明的形式 定理5.7是一个典型的例子，它证明了某个文法确实定义了某个已经非形式化定义好的特定的语言。首先要给出一个归纳假设，用它来描述每个变元所推导出的串都要满足的性质。在这个例中只有一个变元P，因此只要声明它所代表的串就是回文串即可。 然后证明“充分性”这部分：即如果一个串w满足某一个变元A的串所应该有的非形式化陈述了的性质，那么就应该有A?w。在这个例中，因为P是开始符号，因此?P?w就意味着w在这个文法的语言中。通常我们用数学归纳法，通过对w的长度进行归纳来证明“充分性”这部分。如果有k个变元的话，那么可以证明归纳陈述应该包含k个部分，并且它们之间应该能被证明是互归纳的关系。 接着要证明“必要性”这部分，即如果A?w，那么w应该满足A所能推导出的串所应该有的非形式化陈述了的性质。同样，在这个的例中，只有开始符号P需要证明，并且认为w在Gpal的语言里和P?w是等价的。这部分的证明通常需要对推导的步数进行归纳。如果该文法有这种类型的产生式：该产生式所推导出的串中可能包含两个或更多的变元，那么就应该把一个n步的推导分成若干部分，每个变元一个部分。这些部分可能比n步少，因此就必须使用对所有小于等于n的情况都包含的归纳假设，就像1.4.2节中所说的那样。
???5.1.6 句型
由开始符号推导出来的串有着很特殊的作用，它们称作“句型”，即如果
G?(V,T,P,S)是一个CFG，那么任何在(V∪T)*中且满足S??的串α都是句型。如果
?S??则α是左句型，如果如果S??则α是右句型。注意语言L(G)是由所有属于T*的
lmrm??句型组成的，也就是由只含终结符号的句型组成的。
例5.8：考虑图5.2中表达式的文法。例如，E?(I?E)是一个句型，因为可以有这样一个推导：
E?E?E?E?(E)?E?(E?E)?E?(I?E)
然而这个推导既不是最左的也不是最右的，原因是在最后一步中被替换的是中间的E。
举一个左句型的例子：考虑a?E，存在最左推导：
E?E?E?I?E?a?E
lmlmlm类似的，下面的推导
E?E?E?E?(E)?E?(E?E)
rmrmrm可以说明E?(E?E)是一个右句型。□
5.1.7 5.1节习题
习题5.1.1：设计下列语言的上下文无关文法：
* a) 集合{0n1n | n≥1}，即所有一个或多个0后面跟着相同数目的1的串的集合。 *! b) 集合{aibjck | i≠j 或 j≠k}，即所有满足如下性质的串的集合：若干个a后面跟着若干
个b，后面再跟着若干个c，并且或者a和b的数目不同，或者b和c的数目不同，或者两者都不同。 ! c) 所有不是ww形式的由a和b构成的串的集合，即不是把某个串任何重复了一遍的
串。 !! d) 所有0的个数是1的个数两倍的串的集合。
习题5.1.2：下面的文法产生了正则表达式0*1(0+1)*的语言：
S?A1BA?0A|?B?0B|1B|?试给出下列串的最左推导和最右推导： * a) 00101。 b) 1001。 c) 00011。
! 习题5.1.3：证明任何正则语言都是上下文无关语言。提示：通过对正则表达式中的运算符的数目进行归纳的方法来构造CFG。
! 习题5.1.4：如果一个CFG的每个产生式的体都最多只有一个变元，并且该变元总在最右端，那么该CFG称做右线性的。也就是说，右线性文法的所有产生式都是A?wB或A?w的形式，其中A和B是变元，w是由零个或多个终结符号所组成的串。
a) 证明任何右线性文法所产生的语言都是正则语言。提示：构造一个ε-NFA来模拟最左推导，并用它的状态来表示当前左句型中的单个变元。 b) 证明任何正则语言都有右线性文法。提示：用一个DFA，并且用文法的变元来表示状态。 *! 习题5.1.5：设T?{0,1,(,),?,*,?,e}，可以把T看作字母表为{0, 1}的正则表达式所使用的符号的集合，唯一的不同是用e来表示符号ε，目的是为了避免有可能出现的潜在的混淆。你的任务是以T为终结符号集合来设计一个CFG，该CFG生成的语言恰好是字母表为{0, 1}的正则表达式。
习题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?ε，并且该节点只有一个标号为ε的子节点，这也是能在分析树中使用标号为ε的节点的唯一情况。□