发布时间 : 星期一 文章上下文无关文法与语言更新完毕开始阅读83402af2ba0d4a7302763ab1
第（v）行和第（vi）行利用产生式1推断出以下结论：由于任何标识符都是表达式，因此我们在第（i）行和第（iv）行中推断出的标识符a和b00也都是变元E所代表的语言中的串。第（vii）行利用产生式2推出这些表达式1的和也是表达式；第（viii）行利用产生式4推出用括号括着的同样的该串也是表达式2；第（ix）行利用产生式3来把 a与我们在第（viii）行中所发现的表达式相乘。□
从头到体地使用产生式来进行推导需要定义一个新的关系符号?。设G = (V, T, P, S)是一个CFG，?A?是一个包含终结符号和变元的串，其中A是一个变元，也就是说，α和β是都是(V∪T)*中的串，而A属于V。如果A?γ是G的一个产生式，那么我们称?A?????。如果G是上下文已知的，那么就可以把它省略掉，而仅仅记做
G?A?????。注意：在推导的每一步中都可以替换串中任何位置的任何一个变元，只要
用该变元的任何一个产生式的体替换该变元即可。
进一步可以把?符号推广到能够表示零步、一步或者多步推导，就像有穷自动机的转
?移函数?被推广到?一样。在推导中，用一个*来表示“零步或多步”，如下：
?基础：对任何由终结符号和变元组成的串α都有???，也就是说，任何串都能推导出它
G自己。
归纳：如果???并且???，则???。也就是说，如果α经过零步或多步推导可以得
GGG???到β，而β经过零步或多步推导可以得到γ，那么α就可以推导出γ。另一种解释，
???意味着存在一个串的序列γ1，γ2，…，γn，n≥1，满足
G?1. α ＝γ1， 2. β ＝γn，
3. 对于i = 1, 2, …, n – 1，有γi?γ
?i +1 。
如果文法G是已知的，我们可以用?来代替? 。
G?例5.5：推断a?(a?b00)属于变元E所代表的语言的过程可以用一个从串E开始的对该串的推导来给出，下面就是一个这样的推导：
E?E?E?I?E?a?E? a?(E)?a?(E?E)?a?(I?E)?a?(a?E)?a?(a?I)?a?(a?I0)?a?(a?I00)?a?(a?b00)在第一步中，用产生式3（图5.2）的体来替换E。在第二步中，产生式1体中的I被用来替换第一个E，依次类推。值得注意的是，在替换时我们系统地采用了总是替换串中最左边变元的策略。然而在每一步中，其实我们可以选择要被替换的变元，也可以使用任何一个该变元的产生式的体来替换它。例如，在第二步中，可以用(E)来替换第二个E（凭借产生式4），如果这样做的话，就可以得到E?E?E?(E)。也可以选择一个甚至永远 12
原文误为“标识符”——译者注 原文误为“标识符”——译者注
不能得到这个终结符串的替换：一个简单的例子是如果在第一步时使用产生式2，那么将会得到E?E＋E，而无论对这两个E再做任何替换都无法把E+E变成a?(a?b00)了。
我们可以通过使用关系符号?来简化推导过程：首先由基础可知E?E，然后反复使用归纳部分可以得到E?E?E，E?I?E等等，直到最终的E?a?(a?b00)。
递归推理和推导这两种观点是等价的。换句话说，能够推理出一个终结符号串w属于某个变元A的语言当且仅当A?w。然而，想要证明这件事还需要一些其它的工作，我们将放到后面的第5.2节再来完成。□
?????? CFG推导中的符号表示 在讨论CFG时，对不同符号的表示方法有许多约定俗成的惯例，比如： 1. 字母表中开头的几个小写字母如a, b等表示终结符号，数字和其它字符比如＋或括号总表示终结符号。 2. 字母表中开头的几个大写字母如A, B等表示变元。 3. 字母表中结尾的几个小写字母如w或z表示终结符号串。这种约定提示我们：在自动机中的输入符号和终结符号串是类似的。 4. 字母表中结尾的几个大写字母如X或Y可以表示终结符号或者变元。 5. 小写的希腊字母如α和β表示由终结符号和（或）变元构成的串。 其中没有只由变元构成的串，原因是这种串的意义不大。然而，一个名叫α或其它希腊字母的串可以只包含变元。
5.1.4 最左和最右推导
当推导一个串时，我们可通过如下的方法来限制可选推导的数目：在每一步推导中只将最左边的变元替换成该变元的某个产生式体，这种方式的推导叫做最左推导（Leftmost Derivation），用关系符号?和?分别来表示一步和多步的最左推导。如果文法G在推导
lm?lm中不是很清楚，那么也可以把它放到这两个符号中箭头的下边。
类似的，也可以每次只替换串中最右边的变元，这样的推导叫做最右（Rightmost）（推导），使用符号?和?分别来表示一步和多步的最右推导。同上，如果不是很清楚
rm?rm的话，相应文法的名字也可以写在箭头下边。
例5.6：例5.5中的推导实际上是一个最左推导，因此，我们也可以这样写：
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我们也可以把上面的最左推导精简为E?a?(a?b00)，或者分多步来表达推导的过
lm?程，比如其中的某一步为E?E?a?(E)。
lm?如果采用最右推导，虽然对串中的每个变元实际上做了同样的替换，但替换的次序不同。具体写出来就是：
E?E?E?E?(E)?E?(E?E)?rmrmrmrmE?(E?I)?E?(E?I0)?E?(E?I00)?E?(E?b00)?
rmrmrmrmE?(I?b00)?E?(a?b00)?I?(a?b00)?a?(a?b00)rmrmrm这个推导的精简表示是E?a?(a?b00)。
rm?任何推导都有等价的最左和最右推导。也就是说，如果w是一个终结符号串，A是一个变元，那么A?w当且仅当A?w，也当且仅当A?w，具体的证明将在第5.2节中给
lmrm???出。
5.1.5 文法的语言
如果G ＝ (V, T, P, S)是一个CFG，那么G的语言（language）（记做L(G)）是指能从开始符号推导出的所有终结符号的集合。也就是：
L(G)?{w in T|S?w}
G?如果一个语言L是某个上下文无关文法的语言，那么L就叫做上下文无关语言，或者CFL。例如，我们断定图5.1中的文法定义了字母表为{0, 1}上的回文的语言，因此，这些回文的集合就是一个上下文无关语言。具体的证明如下：
定理5.7：L(Gpal)是字母表为{0, 1}上的回文的集合，其中Gpal是例5.1中的文法。 证明：我们将要证明一个{0, 1}*中的串w在L(Gpal)中当且仅当它是一个回文，即w = wR 。 （充分性）假定w是一个回文，我们使用数学归纳法通过对|w|进行归纳来证明w在L(Gpal)中。
基础：长度0和1为归纳基础。如果|w|是0和1，那么w一定是ε，0或1，由于有产生式P?ε，P? 0和P? 1，因此在上面任何一种情况下都有P?w。
?归纳：假定|w|≥2。因为w = wR，所以w的开头和结尾一定是同一个字符，即w=0x0或w=1x1，并且x也一定是一个回文，即x = xR。注意：为了说明w的两端确实有两个字符，需要用到|w|≥2的假定。
如果w=0x0，则根据归纳假设有P?x，继而可以得到从P到w的推导
?P?0P0?0x0?w。如果w=1x1情况类似，只是第一步推导所需的产生式是P?1P1。在这两种情况下都可以得出w在L(Gpal)中，证毕。
（必要性）现在假定w在L(Gpal)中，即P?w，要证明的是w是一个回文。证明的过程是对从P到w的推导过程的步数进行归纳。
基础：如果该推导是一步完成的，那么它一定使用了三个在体中不包含P的产生式之一，即该推导为P?ε，P?0或P?1。因为ε，0和1都是回文，因而基础得证。
归纳：现在，假定该推导共包含n + 1步，其中n≥1，并且对于任何n步完成的推导上述结论都成立——也就是说，如果P?x可在n步完成，那么x一定是回文。
考虑一个w的(n + 1)-步推导，它一定是如下形式：
???P?0P0?0x0?w
或者P?1P1?1x1?w，原因是n + 1步其实最少是两步，而且能够增加推导步数的产生式只有P?0P0和P?1P1。注意在这两种情况中的P?x都能在n步完成。 根据归纳假设可知x是回文，即x = xR，但是如果这样的话就有0x0和1x1也都是回文，比如(0x0)R = 0x R 0 = 0x0。由此可知w也是回文，证毕。□
???