上下文无关文法.doc

语言与计算理论导引 上下文无关文法第三部分 上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。分析不是一定需要下推自动机来完成。CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。1陶晓鹏 Copyright 2003语言与计算理论导引 上下文无关文法6 上下文无关文法6.1 上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。例子6.1 正如我们在例子2.16中所见，字母表a, b上的回文语言pal可以用下面的递归方法描述：1. L, a, bpal2. 对每个Spal，aSa和bSb也属于pal3. pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1. S的值可以是L, a, b2. 每个S可以写成aSa或bSb的形式如果我们用表示“可以取值为”，则可以写出下面的式子：SaSaabSbaabLba=abba上面的产生过程可以总结成下面的两组产生式（或称规则）：Sa | b | LSaSa | bSb符号“|”表示“或”的含义。上式的含义是aSa或bSb，而不是a或b，即连接运算的优先级高于“|”。我们使用的这套术语中，小写字母a和b表示终结符，大写字母S表示非终结符，或称变量。总共有5条规则，或产生式（production）。符号S是非终结符，也是起始终结符，即我们生成字符串的起始符号是S，然后不断利用规则替换符号串中的非终结符，直到最终得到一个不含非终结符的符号串，就生成了规则所定义的语言的一个字符串。例子2中的产生式具有除起始符S外的多个非终结符，我们设想S表示了语言中任意的字符串，其他非终结符表示了其他辅助性的字符串类型，他们可用来方便地生成S表示的字符串。例子6.2 我们要构造一个生成所有在字母表a, b上的非回文字符串的文法，那样的字符串可以描述如下：从字符串的两端开始比较，也许能够发现一些相同的字符对，但最终能够发现一对不同的字符。对于前一种情况，我们可以借用回文语言的产生式：SaSa | bSb如果加入产生式Sa | b | L则这种左右匹配的形式将体现在整个字符串上，为了中断这种左右匹配的情况，即体现上面提到的第二种情况，我们引入新的非终结符，比如D，表示那些左右两个端点上的字符不同的字符串。且所有符合D的字符串也符合S，因此有SD。非终结符的定义比较简单，它唯一的条件是左右两个端点的字符不相同，中间的字符串可以是任意的，我们用非终结符A表示任意的字符串，则有DaAb | bAa。A表示任意的字符串，因此A的产生式更简单了，不用添加新的非终结符来简化问题，它的产生式是，AL | aA | bA。我们把上面三个非终结符的产生式写在一起，就得到了描述所规定语言的产生式集：SaSa | bSb | DDaAb | bAaAL | aA | bA因此一个完整的非回文字符串“abbaaba”的产生过程是，SaSaabSbaabDbaabbAabaabbaAabaabbaLabaabbaaba定义6.1 上下文无关文法（context-free grammar, CFG）是一个4元组G=(V, , S, P)，其中，V和是不相交的有限集，SV，P是一组有限的产生式规则，形如Aa，其中AV，且a(V)*。V的元素称为非终结符（或变量），的元素称为终结符，S是一个特殊的非终结符，称为起始符，P的元素称为语法规则，或产生式。设G=(V, , S, P)是一个CFG，我们将符号保留给P的产生式专用，符号G用于表示字符串的产生过程的每一步，如aGb表示字符串b能够通过替换a中的某些变量（根据P定义的产生式来替换）得到，即如果有a=a1Aa2且AgP，则b=a1ga2。这里能够看到，我们命名为上下文无关（context-free）的含义，即我们在利用产生式规则，用一组符号替换某个非终结符时，与非终结符的上下文无关（此处，A的替换与a1和a2无关），替换是无限制的。在没有多个文法出现，很清楚用到文法G是什么的情况下，推导符号G可以简写成。多步的推导可以写成*G，即如果存在一组符号串，a=a0、a1、ak=b，每个后者都是前者的直接推导，则称为a可以多步推导出b，记为a*Gb，简写成a*b。定义6.2 G=(V, , S, P)是一个CFG，则G产生的语言是所有可由G产生的字符串组成的集合，即L(G)=x* | S*Gx。一个语言L是上下文无关语言（context-free language, CFL），当且仅当存在一个CFG G，使得L=L(G)。此处可以把文法设想成类似自动机的抽象模型，则一个语言L是CFL当且仅当存在一个CFG G接受它（或识别它），类似前面正则语言与有限自动机的关系，接受（或识别）的含义是两方面的，一方面凡是L中的字符串都能由G产生，另一方面，凡是不属于L的字符串都不能由G产生。前面的例子，能够比较容易地说明这两方面的限制，下面的例子则不是很明显。例子6.3 考虑语言L=x0, 1* | n0(x)=n1(x)，其中ni(x)表示数字i在x中的出现次数（即含有相同数目0和1的语言）。写出生成L的CFG。分析：既然CFG的本质是一个递归定义，那么类似例子6.1，我们可以先发现归纳基础，然后找到归纳推理。显然LL，另外如果存在一个字符串xL，那么得到更长的属于L的字符串的两个方法是，0x1和1x0，即分别在两端添加相同数量的0和1。（当然，还有很多生成方法，比如x01，x10，或在x中插入相同数量的0和1），这样得到三个产生式：SL | 0S1 | 1S0显然，还遗漏了一些字符串，如0110。我们注意到L中任意两个元素的连接仍然属于L，因此可以增加一个产生式，SSS。与前面的三个产生式合并，我们得到一个CFG G如下，SL | 0S1 | 1S0 | SS显然G产生的字符串都满足0和1数目相等这个条件，即L(G)L，现在只要证明LL(G)。令d(x)=n0(x)-n1(x)。则字符串xL，当且仅当d(x)=0。因此只需证明每个满足d(x)=0的x，都有xL(G)。我们用数学归纳法来证明LL(G)。归纳对象是字符串的长度|x|。1. 归纳基础，|x|=0且d(x)=0，则xL(G)，这是显然的，因为此时x=L，而L可以由产生式SL得到。2. 归纳推理，设k=0，每个满足|y|=k，d(y)=0的字符串y都属于L(G)。要证明每个长度等于k+1且d(x)=0的字符串x也属于L(G)。分情况讨论如下：a) 如果x以0开始，以1结尾，则可以写成x=0y1，且d(y)=0，根据归纳假设yL(G)，即存在一组推导，S*Gy。因此对于x，存在推导，S0S1*0y1x。b) 如果x以1开始，以0结尾，类似a)的处理，能够得到从S到x的推导。c) 如果x以0开始，且以0结尾。则x的长度至少为2，设x=0y0。现在考察x的所有前缀z的d(z)，其中d(0)=1，d(0y)=d(0y0)-d(0)=-1，而d(z)随着z的长度增1，至多增加1或减少1，而当前缀从0变化到0y时，d(z)从1变化到-1，因此存在某个长于0短于0y的前缀z，使得d(z)=0，则x=zw，显然d(w)=0，由于z、w的长度都0的x都能由G0产生，对x的长度应用数学归纳法。1. 归纳基础，显然|x|=1且d(x)0时，即x=0，x可由S0推导，属于L(G0)。2. 归纳推理，设k=0，对每个|x|0的x都属于L(G0)，要证明每个|x|0的x也属于L(G0)。分情况讨论，此处仅讨论x=0y0的情况（即以0开始和结尾的情况），a) x仅由0组成，易证。b) x至少含有一个1。则x=w1z，现在证明d(w)0且d(z)0。设x含有n个1，n=1，对每个1=i=n，令wi是x的前缀，紧接wi的下一个字符就是第i个1，则x=wi1zi。分两种情况1）不存在wi，使得d(wi)0，则d(wn)0，令w=wn，z=zn，显然d(z)0，得证；2）存在一个wi，使得d(wi)=0，设i=m是第一个d(wi)0，且d(wm-1)=10，令w=wm-1，z=zm-1，易证d(zm-1)0，因此得证。其他两种情况，x以1开始，以1结尾证明略。类似方法能够得到生成L1的产生式，我们用A表示生成L0的产生式，B表示生成L1的产生式，那么生成语言L的全部文法是：SA | BA0 | 0A | 1AA | AA1 | A1AB1 | 1B | 0BB | BB0 | B0B注意其中的第一个规则，它恰如其分地表示了合集的含义。6.2 更多地例子，包括一些熟悉的语言例子6.5 我们前面已经提到了在计算机科学和其他领域应用很广泛的书写代数表达式的语言。一般地，我们允许任意的标识符和数字常数出现在表达式中，为了简化问题，我们规定只有一个标识符（字母a）、4种两项运算符（+、-、*、/）和左括号、右括号。我们用变量A表示这个简单的表达式语言。它可以嵌入到复杂的表达式语言中。一个容易发现的递归现象是，如果存在两个表达式，那么可以利用运算符和括号，连接它们构成新的表达式。显然，除了单个标识符a，其他表达式都是通过这个递归过程构造的，因此我们得到下面的文法：SS+S | S-S | S*S | S/S | (S) | a表达式a+(a*a)/a-a的推导过程如下，SS-SS+S-Sa+S-Sa+S/S-Sa+(S)/S-Sa+(S*S)/S-Sa+(a*S)/S-S.a+(a*a)/a-a还存在其他一些推导过程，如SS/SS+S/Sa+S/Sa+(S)/Sa+(S*S)/Sa+(a*S)/Sa+(a*a)/Sa+(a*a)/S-Sa+(a*a)/a-Sa+(a*a)/a-a显然，第一种推导比第二种更自然，它符合了通常的运算符的优先级和计算次序。比如，上述表达式通常的计算次序如下：1. 计算a*a，记为A2. 计算A/a，记为B3. 计算a+B，记为C4. 计算C-a尽管第二种推导不符合通常的表达式结构，或表达式语义，但整个推导是符合文法规定的，是一个合法的推导。一个可能的结论是本例给出的CFG不是最合理的，它没有体现出运算符和括号的优先级，另外好的CFG对每个字符串仅仅提供一种推导过程（如果忽略次序不同的一些简单替换），在6.4节我们将回到这个问题，它称为CFG的歧义。例子6.6 上面的例子类似例子3.5和3.6，仅仅描述了程序设计语言（比如C和Pascal）的某个部分，本例将显示，CFG可用来描述程序设计语言的整个语法结构。C语言有两大类语法结构，和。包括条件声明（）和循环声明（）等等，因此有，. | | | .if () for (; ; ) .可以类似构造多个声明连接而成的复合声明，以及等等。例子6.7 高级程序设计语言的一个大的优点是写出的程序与英文陈述很接近，既然我们可以用CFG去描述高级程序设计语言，那么可不可以用来描述英语呢？对于一些简单的英语语法，容易找到它的CFG，比如最基本、最典型的英语陈述句的结构是， ，因此可以构造出如下的产生式， 可以进一步构造生成右部三个非终结符的产生式。写出一套合理的、具有广泛性、符合常用语法习惯的英语规则并不困难，且规则的数目也可以不是很多。困难的地方是防止产生不合语法，或合乎语法，然而不合语义，没有人会使用的英语句子。下面的产生式就是一个例子， John | Janereminded | himself | herself上面文法能够产生很多不“正确”的英语句子，如“John reminded herself”，“Jane reminded himself”。可以通过增加文法的复杂性（更多的非终结符和更多的产生式）来消除这种不正确的推导，比如修改产生式为， 而对于例如“Jane reminded Jane”还需要其他消除方法，因为句子“Jane reminded John”是一个好的英语句子。要想区别这两个句子，需要上下文信息，因此本章讨论的CFG无法很深入、精细地刻画自然语言的一些细微特征。6.3 CFL的合并、连接和Kleene*运算例子6.4我们构造了一个CFG，它生成的语言是另外两种语言的合集，而且找到了另外两种语言对应的CFG。例子6.4揭示的方法和处理连接和Kleene*运算的相应方法构成了下面定理的基础。定理6.1 L1和L2是两个CFL，则语言L1L2、L1L2和L1*也是CFL。证明：我们用构造法证明。假设生成L1和L2的文法分别是G1=(V1, , S1, P1)和G2=(V2, , S2, P2)，以此为基础，分别构造生成上面三种新语言的CFG。首先假设V1V2=f（否则可以通过改名来到达目的），设生成L1L2的文法Gu=(Vu, , Su, Pu)，其中，Su是不属于V1和V2的新增非终结符，Vu=V1V2Su，Pu=P1P2SuS1 | S2。现在证明L(Gu)=L1L2。一方面，任取xL1=L(G1)，则S1*x，又由于存在产生式SuS1，因此Su*x。类似地，任取xL1，也有S*x。因此L1L2L(Gu)。另一方面，任取xL(Gu)，则存在S*x，则存在S1*x或S2*x，因此L(Gu)L1L2。得证。类似处理连接运算，文法Gc=(Vc, , Sc, Pc)，其中Sc是不属于V1和V2的新增非终结符。定义Vc=V1V2Sc，Pc=P1P2ScS1S2。任给xL1L2，则x=x1x2，x1L1，x2L2。因此有SS1S2*x1S2*x1x2=x，即L1L2L(Gc)。任给xL(Gc)，即S*x，则有S1S2*x，由于V1和V2不相交，则存在x1x2=x，满足S1*x1，S2*x2，因此L(Gc)L1L2。文法G*=(V, , S, P)生成语言L1*，其中，S是不属于V的新增非终结符。语言L1*所含字符串x的形式是x=x1x2.xk，其中每个xiL1，如果能够S连续地产生k个S1，则S能够推导出x，因此得到下面的产生式，SS1S | L，而P=P1SS1S | L。显然，L1*L(G1*)。任给xL(G1*)，则存在S*x，而S推导的第一步一定是SS1k，因此xL(G1)kL(G1)*。得证。下面的例子说明了证明的第一步消除V1和V2中的同名是很重要的。比如有两个CFG如下：S1XA, Xc, AaS2XB, Xd, Bb此处非终结符X出现在两个文法中，如果不改名将带来混乱。如SS1XAdAda，而事实上S1无法推导出da。推论6.1 每个正则语言都是CFL。证明：根据正则语言的递归定义（定义3.1），每个正则语言是以三种简单的字符（f、L、a）为基础，多次施加三种运算（合并、连接、Kleeen*）得到。显然三种简单的字符组成的语言是CFL，又根据定理6.1，三种运算保持了CFL的性质，因此根据结构归纳法，命题得证。例子6.8 语言L是正则表达式，(011+1)*(01)*，表示的正则语言，写出它对应的CFG。分析：定理6.1的证明过程给出了发现一个CFL的CFG的方法。分别考虑(011+1)*和(01)*。而(011+1)*可进一步转化成考虑(011+1)，得到A011 | 1，然后加上Kleene*运算，得到，BAB | L类似地，对应正则表达式(01)*的产生式是，CDC | L, D01最后应用连接运算，得到语言L对应的CFG是SBCBAB | LA011 | 1CDC | LD01最后引入的符号S是非终结符，构造过程中引入的符号是辅助非终结符。例子6.9 语言L=0i1j0k | ji+k的CFG。分析：一个直观的观察是L的每个字符串都是三部分连接而成的：0i、1j、0k。因此似乎可以分别构造三部分语言的CFG，然后通过连接运算构造整个语言的CFG。这种方法是错误的，因为本例语言的三部分是相互关联的，而不是相互独立的，定理6.1揭示的方法仅仅用在相互独立的两个CFG之间的运算。可行的方法是，将本例中具有关系的参数i、j、k转换成相互无关的参数。由于ji+k，不妨令j=i+k+m，m0。则0i1j0k=0i1i1m1k0k。此处的三个参数i、m、k相互独立，因此语言L=L1L2L3，其中，L1=0i1i | i=0L2=1m | m0L3=1k0k | k=0先分别构造语言L1、L2、L3的CFG，然后利用连接运算构造L的CFG。L1和L3类似，L2易于构造。发现L1的递归性质，LL1，对每个xL1，都有0x1L1。因此得到L1的CFG，A0A1 | L。类似地，L3的CFG是C1C0 | L。L2的CFG是B1B | 1（注意，不是BL，因为L2的字符串长度至少为1）。因此连接三部分，得到最终的CFG G=(V, , S, P)，其中，V=S, A, B, C，=0, 1，P=SABC, A0A1 | L, B1B | 1, C1C0 | L。字符串01402=(01)(1)(1202)的推导过程如下，SABC0A1BC0L1BC011C0111C001111C0001111L0001111006.4 推导树和歧义对于一个自然语言，比如英语，理解它的句子从理解它的语法结构开始，即了解句子是怎样根据语言的句法规则产生的。给定一个CFG和一个它所生成的字符串x，知道了x的推导过程有助于正确理解x的含义。一个展示推导过程（或推导结构）的自然的方法是画出推导树或分析树。树的根部是文法的起始非终结符，它是推导的起点。树的内部节点对应文法的一个非终结符，比如A，A的子节点对应形如Aa的产生式的右部a的每个符号。对于形如AL的产生式，标记为A的内部节点的子节点只有一个，即L。以例子6.5文法为例，SS+S | S-S | S*S | S/S | (S) | a，存在一个字符串的推导，SS-SS*S-Sa*S-Sa*a-Sa*a-a，它对应的推导树如图6-1a所示。另一个字符串的推导，SS-SS-S/S.a-a/a的推导树如图6-1b。这两个代数表达式常常用表达式树（expression trees）表示，表达式树是一个二叉树，它的叶节点是标识符或常量，内部节点是运算符（参见图6-2）。表达式树显示了表达式的结构和推导过程，本节提出的推导树类似于这种表达式树。在一个CFL的字符串的完整推导树上，根节点对应文法的起始非终结符，叶节点（或称终端节点）对应终结符或L。有时我们也用推导树表示起于某个普通非终结符的推导结构，或部分推导过程，这种推导树的根节点不一定是起始非终结符，叶节点也不一定是终结符。推导的每一步都是用某个产生式的右部代替左部的非终结符，每个推导都由一组这样的替换按照一定顺序组成。替换的顺序很重要，因此推导SS+Sa+Sa+a和SS+SS+aa+a是不同的推导。这种差异是在细节上，当得到S+S时，前者选取了最左非终结符，后者选取了最右非终结符。两种推导对应的推导树是完全一样的，因此可以认为推导过程中的细微的次序差异是不重要的。推导树完全反映了推导中用到的产生式，但不关心推导中用到的临时节点，或某些产生式的应用次序，这些次序也与字符串的语法结构无关，因此对应相同推导树的推导都认为是相同的推导。另一个比较两个推导的方法是将推导的过程标准化，比如采用最左原则，即每次替换最左（或第一个）非终结符。如果两个遵循最左原则的推导是不同的，那么认为是“本质”不同的推导。实际上，最左原则和推导树原则是两个相当的判定标准。一方面，对应不同推导树的最左推导过程是显然不同的。另一方面，对应不同最左推导过程的推导树也是不同的。比如设下面的推导是第一次出现差异的情况，xAbxa1bxAbxa2b其中，x是终结符组成的字符串，A是非终结符，且a1a2，因此体现在推导树则一定不同。现在定义，一个字符串具有多个（超过1个）推导树当且仅当具有多个最左推导。注意我们也可以采用最右原则，关键是消除一些细节上的差异。我们发现许多CFG生成的字符串具有多个“本质”不同的生成办法。定义6.3 CFG G是歧义的（ambiguous）当且仅当存在一个xL(G)具有多个推导树（或最左推导过程）。显然，上面定义的歧义很接近我们日常应用的自然语言句子的歧义。比如一个记者用到的标题“Disabled Fly to See Carter”，如果它出现在美国第39任总统当政时期，对应的推导是：S .。但通常更多的解释是：S .。此处，正确理解一个新闻标题的关键是选择相应的语法推导。例子6.10 回到例子6.5给出的代数表达式的CFG，我们考察了字符串a+(a*a)/a-a具有的本质不同的推导过程。分析：本例的CFG形如，SS+S | S-S | S*S | S/S | (s) | a，看一个简单的例子“a+a+a”，存在两个不同的最左推导：SS+Sa+Sa+S+Sa+a+Sa+a+aSS+SS+S+Sa+S+Sa+a+Sa+a+a它们对应的推导树分别见图6-3a和图6-3b。如果结合具体的代数运算符含义，两者最终含义是相同的，前者等同于a+(a+a)，后者等同于(a+a)+a。可见括号具有消除歧义的作用。从例子6.10容易看到，凡是具有形如AAaA的产生式的CFG都是有歧义的。然而有很多种引入歧义的方式，有时很难发现并排除它们。例子6.11 程序设计语言歧义的一个标准的例子是“dangling else”，考虑下面的产生式：if () | if () else |现在考虑声明：if (expr1) if (expr2) f(); else g();根据上面的产生式，可以有两个推导树，一种将else看成与第一个if相关，另一种将else看成与第二个if相关。参见图6-4a和图6-4b。在C语言中，为了消除歧义，常常引入括号，如，if (expr1) if (expr2) f(); else g();if (expr1) if (expr2) f(); else g();或者修改文法，如 | if () else | if () | if () else 目前我们无法证明为什么新文法消除了歧义，但可以直观地解释。生成的都是if-else匹配的情况，生成的是if-else不匹配的情况。而且出现在else之前的都是，因此不匹配的情况出现在else之后，即else总是与最接近的if匹配。程序设计语言Modula-2使用了类似括号的方法消除歧义，IF THEN END |IF THEN ELSE END |在上面文法下，图6-4a和图6-4b对应的字符串分别是IF A1 THEN IF A2 THEN S1 END ELSE S2 ENDIF A1 THEN IF A2 THEN S1 ELSE S2 END END6.5 一个无歧义的代数表达式尽管有些CFL是“内在”歧义的，即只能由有歧义的CFG生成，但通常意义的歧义是针对文法而言，而不是语言。如果一个CFG是歧义的，常常可能存在（也是我们希望发现的）一个与其相当的非歧义的CFG，本节我们消除例子6.5给出的代数表达式的文法的歧义。为了简化问题，我们仅仅使用两个运算符“+”和“*”，得到产生式如下，SS+S | S*S | (S) | a如果消除了这两个运算符的歧义，能够类似地消除“-”和“/”的歧义。正如前面讲到，产生式SS+S能够带来歧义，我们需要消除这种类型的产生式，同时保持各种运算符的优先级，比如*的优先级高于+，且位于前面的+优先级高于后面的+。新文法G1的产生式如下，SS+T | TTT*F | FF(S) | a需要证明两个方面：1）G1与G相当；2）G1没有歧义。为了证明方便，G1中的起始符号改写成S1。定理6.2 文法G的产生式是SS+S | S*S | (S) | a，文法G1的产生式是S1S1+T | TTT*F | FF(S1) | a则L(G)=L(G1)。证明：首先证明L(G1)L(G)。对属于L(G1)的字符串x的长度使用数学归纳法。1. 归纳基础，x=a时，显然xL(G)2. 归纳推理，设k=1，每个属于L(G1)、长度=k的字符串y也属于L(G)，要证明如果xL(G1)且|x|=k+1，则xL(G)。显然G1推导x的第一步是下面三种情况之一，S1S1+TS1TT*FS1T(S1)如果是情况一，则x=y+z，S1*y，T*z，由于S1*T，因此也有S1*z，由于y和z的长度都=1，对每个yL(G)且|y|=k，yL(G1)也成立，要证明如果xL(G)且|x|=k+1，则xL(G1)。设x在G上的第一步推导是S(S)，对应x=(y)，则|y|=1，任何一个从S1、T、F推导出来的长度=1，如果AGnx，则AG1*x。对n使用数学归纳法。1. 归纳基础，n=1，即AG1x，则P中存在Ax，x是非空的，因此P1中也有Ax，则AG11x，AG1*x。2. 归纳推理，n=k时所有|x|=k的x满足上式。要证明对|x|=k+1的x也满足上式。设AG*x的第一步是AX1X2.Xn，对应x=x1x2.xn。其中Xi=xi或XiG=1，如果AG1nx，则AG*x。类似可证。显然，消除文法的空产生式，需要添加大量新的产生式（很类似，消除FA的空转移需要添加大量新的转移）。于是存在一个问题，添加的新产生式是否带来了新的不好的性质。部分的回答是算法6.1不会带来歧义，即如果原来文法G是非歧义的，则处理后的文法G1也是非歧义的。证明并不困难，参见练习6.38。单一产生式的消除类似空产生式的消除。比如要删除AB（更普遍地，A*B），就要对所有Ba，添加Aa。为了简化讨论，我们消除单一产生式的工作基础是无空产生式的文法。下面先定义A可推导集（A-derivable）。1. 如果存在产生式AB，则B是A可推导的；2. 如果存在产生式CB，且C是A可推导的，BA，则B是A可推导的；3. 仅包含1和2产生的非终结符。算法6.2 给定一个没有空产生式的CFG G=(V, , S, P)，构造一个没有单一产生式的文法G1=(V, , S, P1)。1. 初始化P1=P2. 对每个AV，发现A的可推导集3. 对A的可推导集的每个元素B，如果存在Ba，则添加产生式Aa到P14. 删除P1中的所有单一产生式定理6.5 设G是没有空产生式CFG，G1是算法6.2得到的文法，则G1没有单一产生式，且L(G1)=L(G)。证明：略，参见练习6.37。值得指出的是，如果文法G是无歧义的，则文法G1也是无歧义的。例子6.13 G是生成代数表达式的文法，它的产生式如下：SS+T | TTT*F | FF(S) | a则S的可推导集是T, F，T的可推导集是F。根据算法6.2的第3步，加入产生式ST*F | (S) | a和T(S) | a，然后删除单一产生式，最后的产生式集合如下，SS+T | T*F | (S) | aTT*F | (S) | aF(S) | a除了删除一些“不好”的产生式，如空产生式和单一产生式，对产生式的格式添加更多的限制也是有用的。已经提出了多种产生式的“规范形式”，本节介绍其中的一种，Chomsky范式。定义6.6 一个CFG的每个产生式符合下面两个形式中的一种，则称为Chomsky范式（Chomsky normal form, CNF）：ABC和Aa。其中，A、B、C是非终结符，a是终结符。将一个文法G转换成CNF需要三个步骤。第一步应用算法6.1和算法6.2得到没有空产生式和单一产生式的文法G1，L(G1)=L(G)-L；第二步构造新的文法G2，它的产生式只有下面两种形式：AB1B2.Bk和Aa，其中，A、Bi是非终结符，a是终结符，L(G2)=L(G1)。从G1构造G2很简单，给每个终结符a引入一个相应的非终结符Xa，添加产生式Xaa，原产生式中的a都替换成Xa（除了Aa这类产生式）。文法G2已经很接近Chomsky范式了，产生式的右部要么全是非终结符，要么是单个终结符。第三步，将G2中右部长度超过2的产生式用多个产生式替换。定理6.6 对于每个CFG G都存在一个符合Chomsky范式的CFG G，使得L(G)=L(G)-L。证明：略。例子6.14 CFG G的产生式如下：SAACDAaAb | LCaC | aDaDa | bDb | L构造G对应的符合Chomsky范式的文法G。分析：1. 删除空产生式，得到SAACD | ACD | AAC | CD | AC | CAaAb | abCaC | aDaDa | bDb | aa | bb2. 删除单一产生式，增加SaC | a，删除SC。3. 增加产生式的限制，不允许非终结符和终结符在产生式右部混杂出现，得到SAACD | ACD | AAC | CD | AC | XaC | aAXaAXb | XbXbCXaC | aDXaDXa | XbDXb | XaXb | XbXbXaaXbb4. 转换成CNF，得到SAT1T1A