《计算理论第3章 上下文无关文法与下推自动机.》由会员分享，可在线阅读，更多相关《计算理论第3章 上下文无关文法与下推自动机.（117页珍藏版）》请在金锄头文库上搜索。
1、第三章上下文无关文法与下推自动机ContextFreeGrammar(CFG)andPushDownAutomaton(PDA)上下文无关文法（CFG）在程序设计语言和编译原理中有着重要的应用，因为上下文无关文法可以用来阐述绝大多数的程序设计语言的句法结构。此外上下文无关语言也可以作为描述语言翻译方案的基础。本章重点讨论:CFG的简化CFG的两种范式下推自动机（PDA）的概念PDA与CFG之间的等价转换上下文无关语言运算的封闭性以及CFL的有关判定问题。3.1上下文无关文法的派生树(推导树)一个上下文无关文法中的一个句型的派生过程可以用一棵树来描述。【例3-1.1】给定文法G=(SAabPS)
2、，其中P：SaAS|aASbA|ba|SS。句型aabbaa的派生过程就可以用一棵树来描述，如图3-1.1所示。将此树的叶结点符号从左到右读取下来构成的符号串就是aabbaa。SaASSbAabaa图3-.11aabbaa的派生树1派生树的定义设文法G=(S)是上下文无关文法如果一棵有序树满足下面四个条件，则它是棵派生树：(1)它的每个结点标记的符号是()中的符号；(2)根结点标记开始变元S；(3)内结点标记的符号是变元，即是中的符号。(4)如果一个内结点标记为A，且X1X2Xk是A的从左到右的所有子结点则AX1X2Xk是P中一个产生式。(5)如果一个结点标记符号是，则它是其父结点的唯一儿子结
3、点。其中第(5)条是为了防止下面情况发生：如产生式Aa(a是个终极符)被误认为是Aa或Aa，而在派生树中被画成如图3-2形式。2派生树的结果设T是棵派生树，将此树的叶结点符号从左到右依次读取下来构成的符号串就是此派生树的结果。例如，图3-1.1派生树的结果就是aabbaa。3派生树与句型的派生关系设G=(S)是CFG，如果G中有派生S，则在G中必有一棵以为结果的派生树。反之，如果G中有一棵以为结果的派生树，则G中也必有派生S。可以说派生与派生树是一一对应的。AAaa图3-1.24最左派生与最右派生所谓最左派生，就是在一个派生的每一步都是对句型中最左边的变元进行替换。例如，例3-1中aabbaa
4、的派生：SaASaSbASaabASaabbaSaabbaa，此派生是最左派生。所谓最右派生，就是在一个派生的每一步都是对句型中最右边的变元进行替换。SaASaAaaSbAaaSbbaaaabbaa此派生是最右派生。5上下文无关文法的二义性设G是个CFG，如果它的某个句子有两棵不同构的派生树，则称G是二义性的上下文无关文法。【例3-1.2】给定CFGG=(SabPS)，其中P：SaSbS|bSaS|。句子abab的两棵不同构的派生树，如图3-1.3所示。图3-1.3abab的两棵不同构的派生树SaSSbSaSbSaSSbSaSb这说明此CFGG是有二义性的。3.2上下文无关文法的简化一个上下文
5、无关文法有时可以去掉一些符号，或者去掉一些产生式以后，仍然和原来的文法等价，这就是所谓文法的简化。这里简化文法主要是指：去掉无用符号、去掉产生式和去掉单一产生式。1去掉无用符号定义：给定CFGG=(S)，如果在G中存在派生SXw，其中w，X，则称符号X是有用的，否则X是无用的。简单地说，无用符号就是G中对任何wL(G)的派生中都不会出现的符号。【例3-2.1】给定文法G=(SABCabPS)，其中P：SAB|aABC|aCb。G中有派生：可见再往下就无法推导了，因而由S只能推出a，不能推出其他符号串。所以此文法中，A、B、C、b都是无用的符号，只有S和a是有用符号。如何去掉无用符号？分两步走，
6、使用两个引理，就可以做到这一点。下面介绍这两个引理。引理3-2.1给定CFGG=(S)，且L(G)，可以找到一个与G等价的CFGG=(S)，使得每个A，都有w，且在G中有Aw。证明：1）求的算法：beginOLD:=NEW:=A|AwP且wWhileOLDNEWdobeginOLD:=NEWNEW:=OLDA|AP且(OLD)end:=NEWend下面证明此算法的有效性。显然对任何变元ANEW不论A是在第步还是在第步加入到NEW中的都有派生Aw其中w。只证明G中任何派生Aw，w必有ANEW。(对派生的步数归纳证明)a)若此派生是一步完成的，即有Aw，则说明P中有产生式Aw，于是A在算法的第步被
7、添加到NEW中。b)假设G中派生Aw是少于k步完成的则ANEW。c)当G中有k步派生AX1X2Xnk-1w，不妨设w=w1w2wn，其中Xiwi，(i=12n)，而且由于这些派生的步数少于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中任
8、何派生Sw，在G中也有Sw。所以L(G)L(G)。b）证明L(G)L(G)，(反证法)任取wL(G)，假设wL(G)则说明在G中w的派生Sw中必用到PP中的产生式，即用到了中的变元，而这些变元又能推出终极符串，这与上面证明的此算法有效矛盾。所以必有wL(G)从而L(G)L(G)。最后得L(G)=L(G)。【例3-2.2】给定CFGG=(SABCabPS)，其中P：SA|BAaB|bS|bBAB|BaCAS|b求一个与之等价的文法G，使得G中的每个变元都可以推出终极符串。解：对G应用引理3-2.1，执行上述算法，得到的结果如表3-2.1所示。循环次数i初值123OLDNEW当算法执行第三次循环时
9、，判定OLD=NEW算法终止。最后得GCFGG=(SACabPS)其中P：SAAbS|bCAS|b实际上，只去掉了不能推出终极符串的变元B。ACSACACACSACS引理3-2.2给定CFGG=(S)，可以找到一个与G等价的CFGG，G=(S)，使得每个X()，都有()，且在G中有派生SX。证明：1执行下面迭代算法求和。1）置初值：:=S，:=2）如果A，在P中又有产生式A1|2|m，则可以将12m中的所有变元加到中，将12m中的所有终极符加到中中。重复2)。3）若没有新的符号可加入到、中，算法停止。最后得到、。2构造P：是由P中只含有()中的符号的产生式构成的。3证明L(G)=L(G)a）显
10、然有L(G)L(G)，因为，TT，P，所以G中任何派生Sw，在G中也有Sw。所以L(G)L(G)。b）证明L(G)L(G)，任取wL(G)，不妨设w在G中的派生为SXw，其中()，由上述算法可知，在此派生中出现的所有符号，都不会因为对G使用此引理而被去掉，所以这些符号必在中，此派生中所用到的产生式也在P中，所以这个派生在G中也可以实现，因而必有wL(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-
11、2.2处理得G(S)，由两个引理得L(G)=L(G)。下面证明G中不含无用符号。假设G中有无用符号Y。根据引理3-2.2得，在G中必存在派生SY，其中()，因为G的符号也都是G中的符号，所以此派生在G中也可以实现，又根据引理3-2.1得，和中的变元以及Y都可以推出终极符串，于是G中有派生：SYw，w，又因为派生Yw中的符号不会因为对G用引理3-2.2而被去掉，所以在G中也会实现派生Yw，于是G中也有派生SYw，这与符号Y是无用符号矛盾。所以G中不含无用符号。值得注意的是，去掉G中无用符号时，一定要先用引理3-2.1，后用引理3-2.2。应用引理的次序不可颠倒，否则可能遗漏一些无用符号。请看下面
12、例子。【例3-2.3】给定CFGG=(SABabPS)，其中P：SAB|aAa求一个与之等价的文法G”，使得G”中不含无用符号。解：先对G应用引理3-2.1方法处理，执行此算法得到的结果如表3-2.2所示。循环次数i初值123OLDSANEWSASA当算法执行第二次循环时，判定OLDNEW，算法终止。最后得G：CFGG=(SAabPS)，其中P：SaAa。再对G用引理3-2.2处理，执行算法的结果如表3-2.3所示：循环次数i初值123SSTa最后得文法G(SaPS)，其中P=Sa。但是，如果先对G用引理3-2.2，后用引理3-2.1就得到如下结果：对G用引理3-2.2执行算法的结果，如表3-
13、2.4所示：循环次数i初值123SSABTa得文法G=(SABaPS)，P：SAB|aAa。再对G用引理3-2.1执行算法的结果如表3-2.5所示：循环次数i初值123OLDSANEWSASA最后得文法G=(SAaPS)，P：SaAa。显然，这样做，无用符号A没有被去掉。可见去掉文法中无用符号时，使用这两个引理的先后次序是很重要的2去掉产生式定义：所谓产生式，就是形如A的产生式，其中A为变元。给定CFGG，如果L(G)，则G中所有产生式都可以去掉。如果L(G)，则除了开始变元S的产生式(即S)外，其余产生式都可以去掉。为了去掉产生式，先定义一个概念可为零的变元。定义：设A是个变元，如果A，则称
14、A是可为零的。去掉CFGG中的产生式的思路是：首先，找出G中所有可为零的变元。然后，对P中每个形如AX1X2Xn的产生式进行如下处理：要添加一些这样的产生式：这些产生式是通过去掉X1X2Xn中某些可为零的变元而得到的。但是，如果所有Xi(i=12n)都是可为零的，则不可全去掉，因为那样会产生新的产生式A。【例3-2.6】有产生式：SaSAbB设A与B都是可为零的，则由这个产生式变成如下四个产生式：SaSAbBSaSbB(去掉A)SaSAb(去掉B)SaSb(A和B全去掉)。注意，要将所有可能的情况均考虑到，才能保证新的文法与原文法等价。定理3-2.2给定CFGG=(S)，可以找到一个不含无用符号，又无产生式的CFGG，使得L(G)L(G)
