计算理论基础章精选文档.ppt

《计算理论基础章精选文档.ppt》由会员分享，可在线阅读，更多相关《计算理论基础章精选文档.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算理论基础章本讲稿第一页，共一百一十七页 上下文无关文法（上下文无关文法（CFG）在程序设计语言和编）在程序设计语言和编译原理中有着重要的应用，因为上下文无关文法译原理中有着重要的应用，因为上下文无关文法可以用来阐述绝大多数的程序设计语言的句法结可以用来阐述绝大多数的程序设计语言的句法结构。此外上下文无关语言也可以作为描述语言翻构。此外上下文无关语言也可以作为描述语言翻译方案的基础。译方案的基础。本章重点讨论本章重点讨论:CFG的简化的简化 CFG的两种范式的两种范式 下推自动机（下推自动机（PDA）的概念）的概念 PDA与与CFG之间的等价转换之间的等价转换 上下文无关语言运算的封闭性上下

2、文无关语言运算的封闭性 以及以及CFL的有关判定问题。的有关判定问题。本讲稿第二页，共一百一十七页3.1 上下文无关文法的派生树上下文无关文法的派生树(推导树推导树)一个上下文无关文法中的一个句型的派生过程可以用一个上下文无关文法中的一个句型的派生过程可以用棵树来描述。棵树来描述。【例例3-1.1】给定文法给定文法G=(S,A,a,b,P,S)，其中，其中 P：SaAS|a,ASbA|ba|SS。句型。句型aabbaa的派生过程就可以的派生过程就可以用一棵树来描述，如图用一棵树来描述，如图3-1.1所示。将此树的叶结点符号所示。将此树的叶结点符号从左到右读取下来构成的符从左到右读取下来构成的符

3、号串就是号串就是aabbaa。SaASSbAabaa图3-.11 aabbaa的派生树本讲稿第三页，共一百一十七页1 1派生树的定义派生树的定义设文法设文法 G=(,S)是上下文无关文法是上下文无关文法,如果一棵有序树满足下面四个条件，则它是棵派生树：如果一棵有序树满足下面四个条件，则它是棵派生树：(1)它的每个结点标记的符号是它的每个结点标记的符号是()中的符号；中的符号；(2)根结点标记开始变元根结点标记开始变元S；(3)内结点标记的符号是变元，即是内结点标记的符号是变元，即是中的符号。中的符号。(4)如果一个内结点标记为如果一个内结点标记为A，且，且X1,X2,Xk是是A的从左的从左到右

4、的所有子结点到右的所有子结点,则则AX1X2Xk是是P中一个产生式。中一个产生式。(5)如果一个结点标记符号是如果一个结点标记符号是，则它是其父结点的唯，则它是其父结点的唯一儿子结点。一儿子结点。本讲稿第四页，共一百一十七页其中第其中第(5)条是为了防止下面情况发生：条是为了防止下面情况发生：如产生式如产生式Aa(a是个终极符是个终极符)被误认为被误认为是是Aa或或Aa，而在派生树中被，而在派生树中被画成如图画成如图3-2形式。形式。2派生树的结果 设设T T是棵派生树，将此树的叶结点符号从左到右依次读是棵派生树，将此树的叶结点符号从左到右依次读取下来构成的符号串就是此派生树的结果。取下来构成

5、的符号串就是此派生树的结果。例如，图例如，图3-1.1派生树的结果就是派生树的结果就是aabbaa aabbaa。3派生树与句型的派生关系 设设G=(,S)是是CFG，如果，如果G中有派生中有派生S*，则在则在G中必有一棵以中必有一棵以为结果的派生树。反之，如果为结果的派生树。反之，如果G中中有一棵以有一棵以为结果的派生树，则为结果的派生树，则G中也必有派生中也必有派生S*。可以说派生与派生树是一一对应的。可以说派生与派生树是一一对应的。A AA Aa aa a图图 3-1.2本讲稿第五页，共一百一十七页4 4最左派生与最右派生最左派生与最右派生 所谓最左派生，就是在一个派生的每一步都是对句型

6、所谓最左派生，就是在一个派生的每一步都是对句型中最左边的变元进行替换。中最左边的变元进行替换。例如，例例如，例3-1中中aabbaaaabbaa的派生：的派生：S SaASaASaSbASaSbASaabASaabASaabbaSaabbaSaabbaa aabbaa，此派生是最左派生。此派生是最左派生。所谓最右派生，就是在一个派生的每一步都是对句型所谓最右派生，就是在一个派生的每一步都是对句型中最右边的变元进行替换。中最右边的变元进行替换。S SaASaASaAaaAaaSbAaaSbAaaSbbaaaSbbaaaabbaa,aabbaa,此派生是最右派生。此派生是最右派生。5 5上下文无关

7、文法的二义性上下文无关文法的二义性 设设G是个是个CFG，如果它的某个句子有两棵不同构的派生，如果它的某个句子有两棵不同构的派生树，则称树，则称G是二义性的上下文无关文法。是二义性的上下文无关文法。本讲稿第六页，共一百一十七页【例例3-1.2】给定给定CFG G=(S,a,b,P,S)，其中，其中P：SaSbS|bSaS|。句子句子abab的两棵不同构的派生树，如图的两棵不同构的派生树，如图3-1.3所示。所示。图图3-1.3 abab的两棵不同构的派生树的两棵不同构的派生树S Sa aS SS Sb bS S a aS Sb bS Sa aS SS Sb bS Sa a S S b b这说明

8、此这说明此CFG G是有二义性的。是有二义性的。本讲稿第七页，共一百一十七页3.2 上下文无关文法的简化上下文无关文法的简化 一个上下文无关文法有时可以去掉一些符号，或者去一个上下文无关文法有时可以去掉一些符号，或者去掉一些产生式以后，仍然和原来的文法等价，这就是所掉一些产生式以后，仍然和原来的文法等价，这就是所谓文法的简化。谓文法的简化。这里简化文法主要是指：去掉无用符号、去掉这里简化文法主要是指：去掉无用符号、去掉产生产生式和去掉单一产生式。式和去掉单一产生式。1 1去掉无用符号去掉无用符号 定义定义：给定：给定CFG G=(,S)，如果在，如果在G中存在派中存在派生生S*X*w，其中，其

9、中w*，X，则称，则称符号符号X是有用的，否则是有用的，否则X是无用的。是无用的。简单地说，无用符号就是简单地说，无用符号就是G中对任何中对任何wL(G)的派生中的派生中都不会出现的符号。都不会出现的符号。本讲稿第八页，共一百一十七页【例例3-2.1】给定文法给定文法G=(S,A,B,C,a,b,P,S)，其中，其中P：SAB|a,ABC|a,Cb。G中有派生：中有派生：可见再往下就无法推导了，因而由可见再往下就无法推导了，因而由S只能推出只能推出a，不能推，不能推出其他符号串。所以此文法中，出其他符号串。所以此文法中，A、B、C、b都是无用的都是无用的符号，只有符号，只有S和和a是有用符号。

10、是有用符号。如何去掉无用符号？分两步走，使用两个引理，就可如何去掉无用符号？分两步走，使用两个引理，就可以做到这一点。下面介绍这两个引理。以做到这一点。下面介绍这两个引理。本讲稿第九页，共一百一十七页引理引理3-2.1 给定给定CFG G=(,S)，且，且L(G)，可，可以找到一个与以找到一个与G等价的等价的CFG G=(,S)，使得，使得每个每个A，都有，都有w*，且在，且在G中有中有A*w。证明证明：1）求）求的算法的算法：begin OLD:=NEW:=A|AwP 且且w*While OLDNEW do begin OLD:=NEW NEW:=OLDA|AP,且且(OLD)*end :=

11、NEW,end本讲稿第十页，共一百一十七页下面证明此算法的有效性。下面证明此算法的有效性。显然对任何变元显然对任何变元ANEW,不论不论A是在第是在第步还是在第步还是在第步加入到步加入到NEW中的中的,都有派生都有派生A*w,其中其中w*。只证明只证明G中任何派生中任何派生A*w，w*,必有必有ANEW。(对派生的步数归纳证明对派生的步数归纳证明)a）若此派生是一步完成的，即有若此派生是一步完成的，即有Aw，则说明，则说明P中有产中有产生式生式Aw，于是，于是A在算法的第在算法的第步被添加到步被添加到NEW中。中。b）假设假设G中派生中派生A*w是少于是少于k步完成的步完成的,则则ANEW。c

12、）当当G中有中有k步派生步派生AX1X2 Xnk-1w，不妨设，不妨设w=w1w2 wn，其中，其中Xi*wi，(i=1,2,n)，而且由于这些，而且由于这些派生的步数少于派生的步数少于k步，如果步，如果Xi是变元，则根据假设是变元，则根据假设b）得）得Xi最终会加入到最终会加入到NEW中。在执行算法的第中。在执行算法的第步时步时OLD:=NEW,当最后一个当最后一个Xi加入加入OLD时，在执时，在执行算法的第行算法的第步时，就将步时，就将A加入到加入到NEWNEW中。中。本讲稿第十一页，共一百一十七页这说明此算法是有效的，即凡是可以推出终极符串的变这说明此算法是有效的，即凡是可以推出终极符串

13、的变元都会添加到元都会添加到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)，(反证法反证法)任取任取wL(G)，假设，假设w L(G),则说明在则说明在G中中w的派生的派生S*w中必用到中必用到PP中的中的产生式，即用到了产生式，即用到了中的变元

14、，而这些变元又能中的变元，而这些变元又能推出终极符串，这与上面证明的此算法有效矛盾。所以推出终极符串，这与上面证明的此算法有效矛盾。所以必有必有wL(G),从而从而L(G)L(G)。最后得最后得L(G)=L(G)。本讲稿第十二页，共一百一十七页【例例3-2.2】给定给定CFG G=(S,A,B,C,a,b,P,S)，其中，其中P：SA|B,AaB|bS|b,BAB|Ba,CAS|b求一个与之等价的文法求一个与之等价的文法G，使得，使得G中的每个变元都可以中的每个变元都可以推出终极符串。推出终极符串。解解：对：对G应用引理应用引理3-2.1，执行上述算法，得到的结果如，执行上述算法，得到的结果如

15、表表3-2.1所示。所示。循环次数i 初值 1 2 3OLDNEW当算法执行第三次循环时，判定当算法执行第三次循环时，判定OLD=NEW,算算法终止。最后得法终止。最后得GCFG G=(S,A,C,a,b,P,S),其中其中 P：SA,AbS|b,CAS|b实际上，只去掉了不能推出终极符串的变元实际上，只去掉了不能推出终极符串的变元B。A,C,SA,C A,CA,C,SA,C,S本讲稿第十三页，共一百一十七页引理引理3-2.2 给定给定CFG G=(,S)，可以找到一个与可以找到一个与G等价的等价的CFG G，G=(,S)，使得每个，使得每个X()，都有，都有,()*，且在，且在G中有派中有派

16、生生S*X。证明证明：1执行下面迭代算法求执行下面迭代算法求和和。1）置初值：置初值：:=S，:=;2）如果如果A，在，在P中又有产生式中又有产生式A1|2|m，则可以将则可以将1,2,m中的所有变元加到中的所有变元加到中，将中，将1,2,m中的所有终极符加到中中的所有终极符加到中中。重复中。重复2)。3）若没有新的符号可加入到若没有新的符号可加入到、中，算法停止。中，算法停止。最后得到最后得到、。本讲稿第十四页，共一百一十七页2构造构造P：是由：是由P中只含有中只含有()中的符号的产生中的符号的产生式构成的。式构成的。3证明证明L(G)=L(G)a）显然有显然有L(G)L(G)，因为，因为，

17、T T，P，所以，所以G中任何派生中任何派生S*w，在，在G中也有中也有S*w。所以。所以L(G)L(G)。b）证明证明L(G)L(G)，任取，任取wL(G)，不妨设，不妨设w在在G中的中的派生为派生为S*X*w，其中，其中,()*，由上，由上述算法可知，在此派生中出现的所有符号，都不会因为述算法可知，在此派生中出现的所有符号，都不会因为对对G使用此引理而被去掉，所以这些符号必在使用此引理而被去掉，所以这些符号必在中，此派生中所用到的产生式也在中，此派生中所用到的产生式也在P中，所以这个派生中，所以这个派生在在G中也可以实现，因而必有中也可以实现，因而必有wL(G)。故故L(G)L(G)。最后

18、得最后得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中必中

19、必存在派生存在派生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中不含无用符号。中不含

20、无用符号。本讲稿第十六页，共一百一十七页 值得注意的是，去掉值得注意的是，去掉G中无用符号时，中无用符号时，一定要先用引理一定要先用引理3-2.1，后用引理，后用引理3-2.2。应用引理的次序不可颠倒，否则应用引理的次序不可颠倒，否则可能遗漏一些无用符号。请看下面例子。可能遗漏一些无用符号。请看下面例子。【例例3-2.3】给定给定CFG G=(S,A,B,a,b,P,S)，其中，其中P：SAB|a,Aa求一个与之等价的文法求一个与之等价的文法G”，使得，使得G”中不含无用符号。中不含无用符号。解解：先对：先对G应用引理应用引理3-2.1方法处理，执行此算法得到的方法处理，执行此算法得到的结果如

21、表结果如表3-2.2所示。所示。循环次数i 初值 1 2 3OLD S,A NEW S,A S,A 本讲稿第十七页，共一百一十七页当算法执行第二次循环时，判定当算法执行第二次循环时，判定OLDNEW，算法终止。算法终止。最后得最后得G：CFG G=(S,A,a,b,P,S)，其中其中 P：Sa,Aa。再对再对G用引理用引理3-2.2处理，执行算法的结果如表处理，执行算法的结果如表3-2.3所示：所示：循环次数i 初值 1 2 3 S S T a 最后得文法最后得文法G(S,a,P,S)，其中，其中P=Sa。但是但是，如果先对，如果先对G用引理用引理3-2.2，后用引理，后用引理3-2.1就得到

22、就得到如下结果：如下结果：本讲稿第十八页，共一百一十七页对对G用引理用引理3-2.2执行算法的结果，如表执行算法的结果，如表3-2.4所示：所示：循环次数i 初值 1 2 3 S S,A,B T a 得文法得文法 G=(S,A,B,a,P,S)，P：SAB|a,Aa。再对再对G用引理用引理3-2.1执行算法的结果如表执行算法的结果如表3-2.5所示：所示：循环次数i 初值 1 2 3OLD S,A NEW S,A S,A 最后得文法最后得文法 G=(S,A,a,P,S)，P：Sa,Aa。显然，这样做，无用符号显然，这样做，无用符号A没有被去掉。可见去掉文法没有被去掉。可见去掉文法中无用符号时，

23、使用这两个引理的先后次序是很重要的。中无用符号时，使用这两个引理的先后次序是很重要的。本讲稿第十九页，共一百一十七页2 2去掉去掉产生式产生式定义定义：所谓：所谓产生式，就是形如产生式，就是形如A的产生式，其中的产生式，其中A为变元。为变元。给定给定CFG G，如果，如果 L(G)，则，则G中所有中所有产生式都可以产生式都可以去掉。如果去掉。如果L(G)，则除了开始变元，则除了开始变元S的的产生式产生式(即即S)外，其余外，其余产生式都可以去掉。产生式都可以去掉。为了去掉为了去掉产生式，先定义一个概念产生式，先定义一个概念可为零的变元可为零的变元。定义定义：设：设A是个变元，如果是个变元，如果

24、A*，则称，则称A是可为零的。是可为零的。去掉去掉CFG G中的中的产生式的思路是：产生式的思路是：首先，找出首先，找出G中所有可为零的变元。中所有可为零的变元。然后，对然后，对P中每个形如中每个形如AX1X2Xn的产生式进行如下处的产生式进行如下处理：要添加一些这样的产生式：这些产生式是通过去掉理：要添加一些这样的产生式：这些产生式是通过去掉X1X2Xn中某些可为零的变元而得到的。但是，如果所有中某些可为零的变元而得到的。但是，如果所有Xi(i=1,2,n)都是可为零的，则不可全去掉，因为那样会都是可为零的，则不可全去掉，因为那样会产生新的产生新的产生式产生式A。本讲稿第二十页，共一百一十七

25、页【例例3-2.6】有产生式：有产生式：SaSAbB,设设A与与B都是可为零的，都是可为零的，则由这个产生式变成如下四个产生式：则由这个产生式变成如下四个产生式：SaSAbB,SaSbB(去掉去掉A),SaSAb(去掉去掉B),SaSb(A和和B全去掉全去掉)。注意，要将所有可能的情况均考虑到，才。注意，要将所有可能的情况均考虑到，才能保证新的文法与原文法等价。能保证新的文法与原文法等价。定理定理3-2.2 给定给定CFG G=(,S)，可以找到一个不含无用，可以找到一个不含无用符号，又无符号，又无产生式的产生式的CFG G，使得，使得L(G)L(G)。证明：证明：假设假设G已经去掉了无用符号

26、，从已经去掉了无用符号，从G中去掉中去掉产生式产生式后得到文法后得到文法G，令，令G(,S)，其中，其中P构成如下：构成如下：本讲稿第二十一页，共一百一十七页1用下面迭代算法确定用下面迭代算法确定G中可为零的变元集合中可为零的变元集合0。begin OLD0:=NEW0:=A|AP While OLD0NEW0 do begin OLD0:=NEW0 NEW0:=OLD0A|AP,且且(OLD0)*end 0:=NEW0 end当当OLD0=NEW0时，算法终止，最后得到可为零的变时，算法终止，最后得到可为零的变元集合元集合0。此算法与引理此算法与引理3-2.1中算法相似，类似可证此算法的有效

27、性中算法相似，类似可证此算法的有效性本讲稿第二十二页，共一百一十七页2构造构造P：如果如果AX1X2XnP，则将所有形如，则将所有形如A12n的产的产生式都加到生式都加到P中，其中中，其中 如果如果Xi不是可为零的，则不是可为零的，则iXi。如果如果Xi是可为零的，则是可为零的，则iXi或者或者i。但是，。但是，如果所有如果所有Xi(i=1,2,n)都是可为零的，则不可所有都是可为零的，则不可所有i。3用归纳法证明：对任何用归纳法证明：对任何A,任何任何w，有，有如果如果AG*w，当且仅当，当且仅当 AG*w。1）先证明充分性。）先证明充分性。设设G中有派生中有派生AG*w，w。如如果果此此派

28、派生生是是一一步步完完成成的的，即即G中中有有派派生生AGw，则则AwP，因为，因为w，所以，所以AwP，所以，所以G中也有派生中也有派生AG*w。假假设设G中中派派生生AG*w是是少少于于k步步完完成成的的，则则G中中有有派派生生AG*w。本讲稿第二十三页，共一百一十七页 当当G中有派生中有派生AGX1X2XnG*ww1w2wn是由是由k步步完成的时，其中完成的时，其中Xi()且有且有XiG*wi(i=1,2,n)，其中有的其中有的wi可能为可能为。如果某个。如果某个wi，则对应的，则对应的Xi是可是可为零的变元。为零的变元。由由G中派生中派生AGX1X2Xn得得AX1X2XnP，根据，根据

29、P的的构成得，必有产生式构成得，必有产生式A12nP，其中，其中a）如果如果Xi G*wi，则，则iXi，于是有，于是有i G*wi，且此派生少于且此派生少于k步完成，由假设步完成，由假设得得G中有派生中有派生i G*wi。b）如果如果Xi G*wi，则，则Xi是可为零的变元，与是可为零的变元，与Xi对应对应i，于是有，于是有i G*wi。最后最后G中有派生：中有派生：A G 12n G*w1 2n G*w1w23n G*w1w2wnw,即即G中有派生中有派生A G*w,充分性成立。充分性成立。本讲稿第二十四页，共一百一十七页2）再证明必要性）再证明必要性。设。设G中有派生中有派生AG*w，显

30、然，显然w。.如果此派生是一步完成的，即如果此派生是一步完成的，即G中有中有Aw，则，则AwP，因为，因为w，于是，于是P中有产生式中有产生式Aw或者或者A，使得从，使得从中去掉某些可为零的变元后得到中去掉某些可为零的变元后得到w，总，总之之G中有派生中有派生AGw，或者，或者AGG*w。.假设假设G中有派生中有派生AG*w是少于是少于k步完成的，则步完成的，则G中有中有派生派生AG*w。.当当G中派生中派生AGX1X2 XnG*w1w2wnw是由是由k步步完成时，此派生的第一步派生是用完成时，此派生的第一步派生是用P中的产生式中的产生式AX1X2Xn。根据。根据P的构成知，的构成知，P中必存

31、在产生式中必存在产生式A，使得从，使得从中去掉某些可为零的变元后就得到中去掉某些可为零的变元后就得到X1X2Xn，于是，于是G中有派生：中有派生：AGG*X1X2Xn,本讲稿第二十五页，共一百一十七页而在而在G的第二步及以后的派生的第二步及以后的派生X1X2XnG*w1w2wnw中，令中，令Xi G*wi(i=1,2,.,n)，由于这些派生的步数少于，由于这些派生的步数少于k，由假设由假设得，得，Xi G*wi，于是，于是G中也有派生：中也有派生：A GG*X1X2Xn G*w1X2Xn G*w1w2X3Xn G*w1w2wnw。所以必要性成立。所以必要性成立。最后得此结论成立。即最后得此结论

32、成立。即如果如果AG*w，当且仅当，当且仅当 A G*w。当当A=S时，则有时，则有SG*w，当且仅当，当且仅当 SG*w。于是有于是有L(G)=L(G)。本讲稿第二十六页，共一百一十七页3 3去掉单一产生式去掉单一产生式定义定义：所谓单一产生式，就是形如：所谓单一产生式，就是形如AB的产生式，其中的产生式，其中A和和B都是变元。都是变元。定理定理3-2.3 每个不含有每个不含有的上下文无关语言的上下文无关语言L，都可以由，都可以由一个不含无用符号、无一个不含无用符号、无产生式、也无单一产生式的上产生式、也无单一产生式的上下文无关文法产生。下文无关文法产生。证明证明：令：令G(,S)是一个不含

33、有无用符号，无是一个不含有无用符号，无产生式的上下文无关文法，且产生式的上下文无关文法，且L(G)=L。构造一个。构造一个CFG G(,S)，其中，其中P的构成如下：的构成如下：包含包含P中所有非单一产生式。中所有非单一产生式。对任何对任何A,B，如果有，如果有AG*B，且，且B1|2|n是是P中中B的所有非单一产生式，则把的所有非单一产生式，则把所有所有A1|2|n加到加到P中。中。本讲稿第二十七页，共一百一十七页(例如例如G中有产生式：中有产生式：AB,BC,CD,B,C,D，于是有于是有A*B,A*C,A*D，B*C，B*D,C*D，则则G中有产生式：中有产生式：A|，B|，C|，D。)

34、下面下面证证明明L(G)=L(G)a）首先首先证证明明L(G)L(G)容易看出任何容易看出任何AP，则，则G中必有派生中必有派生AG*。因。因为，如果为，如果AP，G中当然有派生中当然有派生AG，如果，如果A P，则必有变元，则必有变元B，使得，使得G中有派生中有派生 AG*BG。所以对任何所以对任何wL(G),即即SG*w，此派生中用到的所有，此派生中用到的所有产生式产生式AP,则则G中必有派生中必有派生AG*。所以。所以G中必中必有派生有派生SG*w，所以所以wL(G)。因而。因而L(G)L(G)。本讲稿第二十八页，共一百一十七页b b）再证明）再证明L(G)L(G)L(GL(G)任取任取

35、wL(G)wL(G)，设，设w w在在G G中的最左派生如下：中的最左派生如下：S0 1 2 3 n1 n w，下面分两种情况讨论：下面分两种情况讨论：如果上述派生用的都是非单一产生式，则这些产生式如果上述派生用的都是非单一产生式，则这些产生式在在P P中也有，所以这些派生在中也有，所以这些派生在G G中也可以实现。中也可以实现。如果上述派生既用了单一产生式，也用了非单一产生如果上述派生既用了单一产生式，也用了非单一产生式，不妨取出其中一段：式，不妨取出其中一段：i1 i i+1 j j+1 ,非单一非单一 单一单一 非单一非单一设从设从i-1i-1 到到i i 用的是非单一产生式，从用的是非

36、单一产生式，从i到到j用的用的是单一产生式，是单一产生式，j到到j+1用的又是非单一产生式。下面用的又是非单一产生式。下面主要考察主要考察G中从中从i到到j1的的派生派生(此派生是先用单一产生此派生是先用单一产生式，后用非单一产生式式，后用非单一产生式)，看看这段派生在，看看这段派生在G中是如何实中是如何实现的现的。本讲稿第二十九页，共一百一十七页 先看看从先看看从i到到j用的是单一产生式的派生，不妨设用的是单一产生式的派生，不妨设 iyAi,i+1yAi+1,jyAj，其中其中y*，()*从从i到到j的派生写成的派生写成 yAi yAi+1 yAj，这，这些派生都是用单一产生式进行的。实际上

37、相当于派生些派生都是用单一产生式进行的。实际上相当于派生AiAi+1 Aj，所以有，所以有Ai*Aj。再看看再看看j到到j+1 的派生的派生j j+1，它用的是非单一产，它用的是非单一产生式，不妨设生式，不妨设j+1y，()*，于是此于是此派生写成派生写成yAj y，实际上此派生用的是非单一产，实际上此派生用的是非单一产生式生式Aj。于是。于是G中有派生中有派生Ai*Aj，根据，根据P的构的构成，则成，则P中必有产生式中必有产生式 Ai。于是在于是在G中有派生：中有派生：iyAiyj+1，即在，即在G中从中从i到到j+1的派生是一步完成的。的派生是一步完成的。所以当所以当SG*w 用了两种产生

38、式时，用了两种产生式时，G中也有派生中也有派生SG*w。所以所以L(G)L(G)。最后得。最后得L(G)L(G)。本讲稿第三十页，共一百一十七页作业题1给定给定CFG G=(S,A,B,C,a,b,c,P,S)，其中，其中，P：SA|B,AAb|bS|C|b,BAB|Ba,CAS b,去掉去掉G中的无用符号和单一生成式。中的无用符号和单一生成式。2给定给定CFG G=(S,A,B,C,a,b,P,S)，其中，其中，P：SABC,ABB|,BCC|a,CAA|b,去掉去掉G中的中的生成式。生成式。本讲稿第三十一页，共一百一十七页3.3 上下文无关文法的上下文无关文法的Chomsky范式范式 (C

39、homsky Normal Form，CNF)ChomskyChomsky范式形式是范式形式是：每个产生式的形式要么是：每个产生式的形式要么是A ABCBC,要要么是么是D Da a,其中其中A,B,C,DA,B,C,D是变元，是变元，a a是终极符。是终极符。这种范式在形式语言的理论和应用上都具有重要的意义。这种范式在形式语言的理论和应用上都具有重要的意义。下面介绍如何把一个下面介绍如何把一个CFG GCFG G写成写成CNFCNF形式。形式。定理定理3-3.1 任何一个不含有任何一个不含有的的CFL LCFL L都可由一个具有都可由一个具有CNFCNF形式的形式的CFG GCFG G产生。

40、产生。证明证明：由定理：由定理3-2.3可知，对一个不含有可知，对一个不含有的的CFL LCFL L都可由都可由一个不含无用符号、无一个不含无用符号、无产生式、无单一产生式的产生式、无单一产生式的CFG GCFG G产生。产生。不妨设不妨设CFG G=(CFG G=(,S),S)是一个不含无用符号、是一个不含无用符号、无无产生式、无单一产生式的产生式、无单一产生式的CFG,CFG,且且L(G)=LL(G)=L。本讲稿第三十二页，共一百一十七页1.1.先对先对P P中产生式做如下处理：中产生式做如下处理：保留右侧只有一个符号的产生式，保留右侧只有一个符号的产生式，(此符号是终极符，此符号是终极符

41、，)处理产生式处理产生式AX1X2Xn(n2)：如果其中如果其中Xi是终极符是终极符a，则引入新的变元，则引入新的变元Ca，用，用Ca代替代替a，同时添加新的产生式同时添加新的产生式Caa。经过此步处理后，使得产生式的形式只有两种：一种是经过此步处理后，使得产生式的形式只有两种：一种是Aa，a是终极符；另一种是是终极符；另一种是AB1B2Bn，其中每个，其中每个Bi都都是变是变元元(包括新引入的变元包括新引入的变元)。处理产生式处理产生式AB1B2Bn(n3)(因为因为n=2时符合要求时符合要求)，引进新的变元引进新的变元D1D2Dn-2，此产生式用下面产生式替换：，此产生式用下面产生式替换：

42、AB1D1,D1 B2D2,D2B3D3,Dn-3Bn-2Dn-2,Dn-2Bn-1Bn。显然用这显然用这n n1 1个产生式代替个产生式代替AB1B2Bn，这是个等价变，这是个等价变换。经过此步处理后，所有产生式的形式就具有换。经过此步处理后，所有产生式的形式就具有CNFCNF形式形式了了:A:ABC,DBC,Da,a,其中其中A,B,C,DA,B,C,D是变元，是变元，a a是终极符。是终极符。本讲稿第三十三页，共一百一十七页2.2.构造新的构造新的CFGCFG G G=(=(,S),S)，其中，其中中除中除了原来了原来中的变元外，还含有新增加的所有变元。中的变元外，还含有新增加的所有变元

43、。就是由经过上述处理后得到的具有就是由经过上述处理后得到的具有CNFCNF形式的产生式构成。形式的产生式构成。3.3.容易证明容易证明L(GL(G)=L(G)=L(G),这里证明从略。这里证明从略。【例例3-3.1】G是个定义算术表达式的是个定义算术表达式的CFG G=(E,T,F,a,b,+,*,(,),P,E),其中其中E表示算术表达式；表示算术表达式；T表表示项；示项；F表示因子。表示因子。P含有下面这些产生式：含有下面这些产生式：EE+T|T TT*F|F F(E)|a|b求一个具有求一个具有CNF 形式的形式的CFG G,使得使得L(G)=L(G)。解解：1先先简简化化G，因因为为G

44、中不含无用符号，也无中不含无用符号，也无产产生式，生式，所以只去掉所以只去掉单单一一产产生式。生式。1）去掉去掉TF，添加如下，添加如下产产生式：生式：T(E)|a|b 2）去掉去掉ET，添加如下，添加如下产产生式：生式：ET*F|(E)|a|b2保留符合要求的保留符合要求的产产生式生式：Ea|b,Ta|b,Fa|b 本讲稿第三十四页，共一百一十七页3处理产生式处理产生式AX1X2Xn(n2)：终极符：终极符Xi变成变元。变成变元。EE+T 变成变成 EEC+T C+ET*F 变成变成 ETC*F C*E(E)变成变成 EC(EC)C(C)TT*F 变成变成 TTC*F T(E)变成变成 TC

45、(EC)F(E)变成变成 FC(EC)4 4处理产生式处理产生式AB1B2Bn(Bi都是变元都是变元,n3)：引进新：引进新的变元的变元D1,D2,Dn-2。E EECEC+T T 变成变成 E EEDED1 1 D D1 1C C+T T E ETCTC*F F 变成变成 E ETDTD2 2 D D2 2C C*F F E EC C(ECEC)变变成成 E EC C(D D3 3 D D3 3ECEC)T TTCTC*F F 变变成成 T TTDTD2 2 T TC C(ECEC)变变成成 T TC C(D D3 3 F FC C(ECEC)变变成成 F FC C(D D3 3本讲稿第三十

46、五页，共一百一十七页5 5最后得具有最后得具有CNFCNF形式的形式的CFGCFG G G=(=(,P,P,E),E),其中其中E,T,F,CE,T,F,C+,C,C*,C,C(,C,C),D,D1 1,D,D2 2,D,D3 3 a,b,+,a,b,+,*,(,),(,)P P:E:EEDED1 1|TD|TD2 2|C|C(D D3 3|a|b|a|b T TTDTD2 2|C|C(D D3 3|a|b|a|b F FC C(D D3 3|a|b|a|b D D1 1C C+T T D D2 2C C*F F D D3 3ECEC)C C+C C*C C(C C)本讲稿第三十六页，共一百一

47、十七页3.4 CFG 的的Greibach范式范式 (GNF)下面我们讨论下面我们讨论CFG的另外一种范式的另外一种范式Greibach范式范式(GNF)。定义定义：CFG G=(,S)，P中产生式形式都是：中产生式形式都是：Aa，其中，其中a是一个终极符，是一个终极符，a，是变元符号是变元符号串，串，*，则称此文法具有，则称此文法具有GNF形式。形式。任何一个不含有任何一个不含有的的CFL，都可以由一个具有，都可以由一个具有GNF形形式的式的CFG产生。那么如何将一个产生。那么如何将一个CFG变成具有变成具有GNF形式形式的的CFG，应用下面两个引理应用下面两个引理可以实现。可以实现。本讲稿

48、第三十七页，共一百一十七页引理引理3-4.1 设设G=(,S)是个是个CFG，A1B2是是P中一个产生式，又中一个产生式，又B1|2|3|m是是P中变元中变元B的的所有产生式。又令所有产生式。又令G=(,S)，其中，其中P构成如构成如下：从下：从P中删除中删除A1B2，再添加产生式，再添加产生式A112|122|132|1m2，则，则L(G)=L(G)。证明证明：显然有：显然有L(G)L(G)。因为如果。因为如果A1i2(1im)用在用在G的一个派生中，虽然在的一个派生中，虽然在G中没有此产生式，但是在中没有此产生式，但是在G中有如下派生：中有如下派生：A1B21i2(1im)。所以。所以G中

49、的任何派生中的任何派生在在G中也可以实现。所以中也可以实现。所以L(G)L(G)。本讲稿第三十八页，共一百一十七页再证明再证明L(G)L(G)这里只需注意到这里只需注意到G与与G的差别是：只有的差别是：只有A1B2是在是在G中而不在中而不在G中的产生式，而中的产生式，而G中其余的产生式中其余的产生式G中也中也有。所以只要有。所以只要A1B2用于用于G的一个派生中，在其后的一个派生中，在其后的某一步推导肯定用到产生式的某一步推导肯定用到产生式Bi，用以改变变元，用以改变变元B，而这二步推导在而这二步推导在G中用一步派生中用一步派生A1i2(1im)以代之。所以以代之。所以 L(G)L(G)。最后

50、得最后得L(GL(G)L(G)L(G)。下面介绍的引理是处理带有左递归的产生式下面介绍的引理是处理带有左递归的产生式。这里所谓左递归的产生式形式：这里所谓左递归的产生式形式：AA,显然左递归不去掉，就无法变成显然左递归不去掉，就无法变成GNF形式。因为要求形式。因为要求产生式的右侧第一个符号是终极符。当然这不像上面引产生式的右侧第一个符号是终极符。当然这不像上面引理那么简单。理那么简单。应用下面引理解决这个问题。应用下面引理解决这个问题。本讲稿第三十九页，共一百一十七页引理引理3-4.2 设设G=(,S)是个是个CFG，AA1|A2|Am是是P中变元中变元A的所有带有左递归的产生式。的所有带有