计算理论基础章3

第三章上下文无关文法与下推自动机ContextFreeGrammar(CFG)andPushDownAutomaton(PDA)上下文无关文法（CFG）在程序设计语言和编译原理中有着重要的应用，因为上下文无关文法可以用来阐述绝大多数的程序设计语言的句法结构。此外上下文无关语言也可以作为描述语言翻译方案的基础。本章重点讨论:CFG的简化CFG的两种范式下推自动机（PDA）的概念PDA与CFG之间的等价转换上下文无关语言运算的封闭性以及CFL的有关判定问题。3.1上下文无关文法的派生树(推导树)一个上下文无关文法中的一个句型的派生过程可以用—棵树来描述。【例3-1.1】给定文法G=({S,A},{a,b},P,S)，其中P：SaAS|a,ASbA|ba|SS。句型aabbaa的派生过程就可以用一棵树来描述，如图3-1.1所示。将此树的叶结点符号从左到右读取下来构成的符号串就是aabbaa。S๐a๐A๐๐SS๐b๐๐Aa๐b๐๐a๐a图3-.11aabbaa的派生树1．派生树的定义设文法G=(ＶＮ,ＶＴ,Ｐ,S)是上下文无关文法,如果一棵有序树满足下面四个条件，则它是棵派生树：(1)它的每个结点标记的符号是(ＶＮ∪ＶＴ∪{ε})中的符号；(2)根结点标记开始变元S；(3)内结点标记的符号是变元，即是ＶＮ中的符号。(4)如果一个内结点标记为A，且X1,X2,…,Xk是A的从左到右的所有子结点,则AX1X2…Xk是P中一个产生式。(5)如果一个结点标记符号是ε，则它是其父结点的唯一儿子结点。其中第(5)条是为了防止下面情况发生：如产生式Aa(a是个终极符)被误认为是Aaε或Aεa，而在派生树中被画成如图3-2形式。2．派生树的结果设T是棵派生树，将此树的叶结点符号从左到右依次读取下来构成的符号串就是此派生树的结果。例如，图3-1.1派生树的结果就是aabbaa。3．派生树与句型的派生关系设G=(ＶＮ,ＶＴ,Ｐ,S)是CFG，如果G中有派生S*α，则在G中必有一棵以α为结果的派生树。反之，如果G中有一棵以α为结果的派生树，则G中也必有派生S*α。可以说派生与派生树是一一对应的。A๐๐ε๐Aa๐ε๐๐a图3-1.24．最左派生与最右派生所谓最左派生，就是在一个派生的每一步都是对句型中最左边的变元进行替换。例如，例3-1中aabbaa的派生：SaASaSbASaabASaabbaSaabbaa，此派生是最左派生。所谓最右派生，就是在一个派生的每一步都是对句型中最右边的变元进行替换。SaASaAaaSbAaaSbbaaaabbaa,此派生是最右派生。5．上下文无关文法的二义性设G是个CFG，如果它的某个句子有两棵不同构的派生树，则称G是二义性的上下文无关文法。【例3-1.2】给定CFGG=({S},{a,b},P,S)，其中P：SaSbS|bSaS|ε。句子abab的两棵不同构的派生树，如图3-1.3所示。图3-1.3abab的两棵不同构的派生树S๐a๐S๐๐Sb๐S๐๐aε๐๐ε๐ε๐S๐bS๐a๐S๐๐Sb๐๐Sa๐ε๐๐εε๐S๐๐b这说明此CFGG是有二义性的。3.2上下文无关文法的简化一个上下文无关文法有时可以去掉一些符号，或者去掉一些产生式以后，仍然和原来的文法等价，这就是所谓文法的简化。这里简化文法主要是指：去掉无用符号、去掉ε产生式和去掉单一产生式。1．去掉无用符号定义：给定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，如果在G中存在派生S*αXβ*w，其中w∈ＶＴ*，X∈ＶＮ∪ＶＴ，则称符号X是有用的，否则X是无用的。简单地说，无用符号就是G中对任何w∈L(G)的派生中都不会出现的符号。【例3-2.1】给定文法G=({S,A,B,C},{a,b},P,S)，其中P：SAB|a,ABC|a,Cb。G中有派生：可见再往下就无法推导了，因而由S只能推出a，不能推出其他符号串。所以此文法中，A、B、C、b都是无用的符号，只有S和a是有用符号。如何去掉无用符号？分两步走，使用两个引理，就可以做到这一点。下面介绍这两个引理。aBBbBBCBABS引理3-2.1给定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，且L(G)≠Φ，可以找到一个与G等价的CFGG’=(ＶＮ’,ＶＴ,Ｐ’,S)，使得每个A∈ＶＮ’，都有w∈ＶＴ*，且在G’中有A*w。证明：1）求ＶＮ’的算法：begin⑴OLDＶＮ:=Φ⑵NEWＶＮ:={A|Aw∈P且w∈ＶＴ*}⑶WhileOLDＶＮ≠NEWＶＮdobegin⑷OLDＶＮ:=NEWＶＮ⑸NEWＶＮ:=OLDＶＮ∪{A|Aα∈P,且α∈(ＶＴ∪OLDＶＮ)*}end⑹ＶＮ’:=NEWＶＮ,end下面证明此算法的有效性。显然对任何变元A∈NEWＶＮ,不论A是在第⑵步还是在第⑸步加入到NEWＶＮ中的,都有派生A*w,其中w∈ＶＴ*。只证明G中任何派生A*w，w∈ＶＴ*,必有A∈NEWＶＮ。(对派生的步数归纳证明)a）若此派生是一步完成的，即有Aw，则说明P中有产生式Aw，于是A在算法的第⑵步被添加到NEWＶＮ中。b）假设G中派生A*w是少于k步完成的,则A∈NEWＶＮ。c）当G中有k步派生AX1X2…Xnk-1w，不妨设w=w1w2…wn，其中Xi*wi，(i=1,2,…,n)，而且由于这些派生的步数少于k步，如果Xi是变元，则根据假设b）得Xi最终会加入到NEWＶＮ中。在执行算法的第⑷步时OLDＶＮ:=NEWＶＮ,当最后一个Xi加入OLDＶＮ时，在执行算法的第⑸步时，就将A加入到NEWＶＮ中。这说明此算法是有效的，即凡是可以推出终极符串的变元都会添加到NEWＶＮ中。于是，最后得到变元集合ＶＮ’。2）构造文法G’：G’＝(ＶＮ’,ＶＴ,Ｐ’,S)，其中P’：由P中只含有(ＶＮ’∪ＶＴ)的符号的产生式构成的。3）下面证明L(G)=L(G’)a）显然有L(G’)L(G)，因为ＶＮ’ＶＮ，P’Ｐ，所以G’中任何派生S*w，在G中也有S*w。所以L(G’)L(G)。b）证明L(G)L(G’)，(反证法)任取w∈L(G)，假设wL(G’),则说明在G中w的派生S*w中必用到P－P’中的产生式，即用到了ＶＮ－ＶＮ’中的变元，而这些变元又能推出终极符串，这与上面证明的此算法有效矛盾。所以必有w∈L(G’),从而L(G)L(G’)。最后得L(G)=L(G’)。【例3-2.2】给定CFGG=({S,A,B,C},{a,b},P,S)，其中P：SA|B,AaB|bS|b,BAB|Ba,CAS|b求一个与之等价的文法G’，使得G’中的每个变元都可以推出终极符串。解：对G应用引理3-2.1，执行上述算法，得到的结果如表3-2.1所示。循环次数i初值123OLDＶＮNEWＶＮ当算法执行第三次循环时，判定OLDＶＮ=NEWＶＮ,算法终止。最后得G’CFGG’=({S,A,C},{a,b},P’,S),其中P’：SA,AbS|b,CAS|b实际上，只去掉了不能推出终极符串的变元B。{A,C,S}{A,C}Φ{A,C}{A,C,S}{A,C,S}引理3-2.2给定CFGG=(ＶＮ,ＶＴ,Ｐ,S)，可以找到一个与G等价的CFGG’，G’=(ＶＮ’,ＶＴ’,Ｐ’,S)，使得每个X∈(ＶＮ’∪ＶＴ’)，都有α,β∈(ＶＮ’∪ＶＴ’)*，且在G’中有派生S*αXβ。证明：1．执行下面迭代算法求ＶＮ’和ＶＴ’。1）置初值：ＶＮ’:={S}，ＶＴ’:=Φ;2）如果A∈ＶＮ’，在P中又有产生式Aα1|α2|…|αm，则可以将α1,α2,…,αm中的所有变元加到ＶＮ’中，将α1,α2,…,αm中的所有终极符加到中ＶＴ’中。重复2)。3）若没有新的符号可加入到ＶＮ’、ＶＴ’中，算法停止。最后得到ＶＮ’、ＶＴ’。2．构造P’：是由P中只含有(ＶＮ’∪ＶＴ’)中的符号的产生式构成的。3．证明L(G)=L(G’)a）显然有L(G’)L(G)，因为ＶＮ’ＶＮ，ＶT’ＶT，P’Ｐ，所以G’中任何派生S*w，在G中也有S*w。所以L(G’)L(G)。b）证明L(G)L(G’)，任取w∈L(G)，不妨设w在G中的派生为S*αXβ*w，其中α,β∈(ＶＮ∪ＶＴ)*，由上述算法可知，在此派生中出现的所有符号，都不会因为对G使用此引理而被去掉，所以这些符号必在ＶＮ’∪ＶＴ’中，此派生中所用到的产生式也在P’中，所以这个派生在G’中也可以实现，因而必有w∈L(G’)。故L(G)L(G’)。最后得L(G)=L(G’)。定理3-2.1设L是一个非空的上下文无关语言，则L可由一个不含无用符号的上下文无关文法产生。证明：设G=(ＶＮ,ＶＴ,Ｐ,S)是个CFG，且L(G)=L≠Φ。先对G用引理3-2.1处理后，得G’＝(ＶＮ’,ＶＴ,Ｐ’,S)，再将G’用引理3-2.2处理得G’’＝(ＶＮ’’,ＶＴ’’,Ｐ’’,S)，由两个引理得L(G’’)=L(G)。下面证明G’’中不含无用符号。假设G’’中有无用符号Y。根据引理3-2.2得，在G’’中必存在派生S*αYβ，其中α,β∈(ＶＮ’’∪ＶＴ’’)*，因为G’’的符号也都是G’中的符号，所以此派生在G’中也可以实现，又根据引理3-2.1得，α和β中的变元以及Y都可以推出终极符串，于是G’中有派生：S*αYβ*w，w∈ＶＴ*，又因为派生αYβ*w中的符号不会因为对G’用引理3-2.2而被去掉，所以在G’’中也会实现派生αYβ*w，于是G’’中也有派生S*αYβ*w，这与符号Y是无用符号矛盾。所以G’’中不含无用符号。值得注意的是，去掉G中无用符号时，一定要先用引理3-2.1，后用引理3-2.2。应用引理的次序不可颠倒，否则可能遗漏一些无用符号。请看下面例子。【例3-2.3】给定CFGG=({S,A,B},{a,b},P,S)，其中P：SAB|a,Aa求一个与之等价的文法G”，使得G”中不含无用符号。解：先对G应用引理3-2.1方法处理，执行此算法得到的结果如表3-2.2所示。循环次数i初值123OLDＶＮΦ{S,A}NEWＶＮ{S,A}{S,A}当算法执行第二次循环时，判定OLDＶＮ＝NEWＶＮ，算法终止。最后得G’：CFGG’=({S,A},{a,b},P,S)，其中P’：Sa,Aa。再对G’用引理3-2.2处理，执行算法的结果如表3-2.3所示：循环次数i初值123ＶＮ’’{S}{S}ＶT’’Φ{a}最后得文法G’’＝({S},{a},P’’,S)，其中P’’={Sa}。但是，如果先对G用引理3-2.2，后用引理3-2.1就得到如下结果：对G用引理3-2.2执行算法的结果，如表3-2.4所示：循环次数i初值123ＶＮ’{S}{S,A,B}ＶT’Φ{a}得文法G’=({S,A,B},{a},P’,S)，P’：SAB|a,Aa。再对G’用引理3-2.1执行算法的结果如表3-2.5所示：循环次数i初值123OLDＶＮ’’Φ{S,A}NEWＶＮ’’{S,A}{S,A}最后得文法G’’=({S,A},{a},P’’,S)，P’’：Sa,Aa。显然，这样做，无用符号A没有被去掉。可见去掉文法中无用符号时，使用这两个引理的先后次序是很重要的。2．去掉ε产生式定义：所谓ε产生式，就是形如Aε的产生式，其中A为变元。给定CFGG，如果εL(G)，则G中所有ε产生式都可以去掉。如果ε∈L(G)，则除了开始变元S的ε产生式(即Sε)外，其余ε产生式都可以去掉。为了去掉ε产生式，先定义一个概念可为零的变元。定义：设A是个变元，如果A*ε，则称A是可为零的。去掉CFGG中的ε产生式的思路是：首先，找出G中所有可为零的变元。然后，对P中每个形如AX1X2…Xn的产生式进行如下处理：要添加一些这样的产生式：这些产生式是通过去掉X1X2…Xn中某些可为零的变元而得到的。但是，如果所有Xi(i=1,2,…n)都是可为零的，则不可全去掉，因为那样会产生新的ε产生式Aε。【例3-2.6】有产生式：SaSAbB,设