形式语言自动机——上下文无关文法与下推自动机(二).ppt-淘文阁

资源描述

《形式语言自动机——上下文无关文法与下推自动机(二).ppt》由会员分享，可在线阅读，更多相关《形式语言自动机——上下文无关文法与下推自动机(二).ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、4.2上下文无关文法的变换上下文无关文法的变换nCFG的简化的简化n消无用符号消无用符号n消消产生式产生式n消单产生式消单产生式n对生成式形式进行标准化对生成式形式进行标准化1College of Computer Science&Technology,BUPT生成式的标准形式生成式的标准形式nChomsky范式(CNF-ChomskyNormalForm)生成式形式为ABC,Aa,A,B,CN,aT(后面将证明,每个上下文无关文法都有一个CNF文法)nGreibach范式(GNF)生成式形式为Aa,aT,N*意义:对每个2型语言都可找到一个文法使产生式的右端都以终结符开始中心思想:消除左递

2、归.2College of Computer Science&Technology,BUPT变换算法变换算法-消去无用符号消去无用符号无用符号（无用符号（useless symbol）非生成非生成符号符号不可达不可达符号符号有用符号（有用符号（useful symbol）对于对于 CFG G=(N,T,P,S)，称符号称符号X N T 是是有用的有用的，当且仅当，当且仅当S X w，其中其中w T*，,(N T)*.称符号称符号X 是是生成生成符号符号（generating symbol），当且仅当存在当且仅当存在w T*，满足满足X w.称符号称符号X 是是可达可达符号符号（reachabl

3、e symbol），当且仅当存在当且仅当存在,(N T)*，满足满足S X.3College of Computer Science&Technology,BUPT计算生成符号（计算生成符号（generating symbol）集集计算可达符号（计算可达符号（reachable symbol）集集消去非生成符号、不可达符号消去非生成符号、不可达符号消去无用符号消去无用符号消去相关产生式消去相关产生式4College of Computer Science&Technology,BUPT计算生成符号集计算生成符号集思路思路对于对于 CFG G=(N,T,P,S)，可通过下列归纳可通过下列归纳步骤

4、计算生成符号集合：步骤计算生成符号集合：基础基础任何终结符任何终结符a T都是生成符号；都是生成符号；归纳归纳如果有产生式如果有产生式A ，其中其中 (N T)*的的每一个符号都是生成符号，则每一个符号都是生成符号，则A 也是生成符号；也是生成符号；5College of Computer Science&Technology,BUPT步骤步骤:(1)N0=(赋为赋为)N0为有用的非终结符集为有用的非终结符集(2)N=A|A且且 T*N为非终结符集合为非终结符集合(3)如果如果N0N则转则转(4),否则转否则转(6)(4)N0=N(5)N=N0 A|A且且(T N0)*,转转(3)(6)N1=

5、N小小结结:算算法法1找找出出能能推推出出终终结结符符串串的的非非终终结结符符作作为为有有用符号用符号.算法算法1:找出有用非终结符找出有用非终结符 6College of Computer Science&Technology,BUPT一一层层层层向向外外扩扩展展，直直至至最最外外两两层层相相等等为为止止。所所得得集集合合即是算法即是算法1的有用符号。的有用符号。算法算法1:找出有用非终结符（图示）找出有用非终结符（图示）7College of Computer Science&Technology,BUPT计算可达符号集计算可达符号集思路思路对于对于 CFG G=(N,T,P,S)，可通过

6、下列归纳可通过下列归纳步骤计算可达符号集合：步骤计算可达符号集合：基础基础S是可达符号；是可达符号；归纳归纳如果如果A是可达符号，并且有产生式是可达符号，并且有产生式A ，其中其中 (N T)*，则则中的每一个符号都是可中的每一个符号都是可达符号；达符号；8College of Computer Science&Technology,BUPT算法步骤算法步骤:(1)N0=S(2)N=x|A N0且且AxN0(N为有用符号集合为有用符号集合)(3)如果如果N0N转转(4),否则转否则转(5)(4)N0=N;转转(2)(继续迭代下去继续迭代下去)(5)N0=NNT1=NTP1由由P内只含内只含N

7、中符号的生成式组成中符号的生成式组成(即删去了从即删去了从S起不可达的符号起不可达的符号).算法算法2:找出有用符号找出有用符号(从从S可达的符号可达的符号)9College of Computer Science&Technology,BUPT一一层层层层外外扩扩,找找出出从从S可可达达的的所所有有符符号号(含含非非终终结结符符和和终终结符结符)算法算法2:找出从找出从S可达的符号可达的符号（图示）（图示）10College of Computer Science&Technology,BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号例例:(书书P135例例1)已知已知2型文法型

8、文法G=(S,A,B,a,P,S)P:SAB,Sa,Aa由算法由算法1:B推不出终结符串推不出终结符串,删除之删除之,并删并删SAB.N1=S,A,P1:Sa,Aa由算法由算法2:A不出现在不出现在S能推导出的句型中能推导出的句型中,删除之删除之.并删并删Aa 结果为结果为G1=(S,a,Sa,S)应用算法应用算法1和算法和算法2,可删去文法中所有无用符号可删去文法中所有无用符号.11College of Computer Science&Technology,BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号注意注意:必须先执行算法必须先执行算法1,再执行算法再执行算法2,不能颠倒

9、不能颠倒.否则否则,可能导致无用符号不会被完全删除可能导致无用符号不会被完全删除.例例:上例中上例中,若先用算法若先用算法2,得得Sa,AAB,Aa再用算法再用算法1,得得Sa,Aa。而而Aa是多余的是多余的.定理定理:任任何何非非空空的的上上下下文文无无关关语语言言,可可由由不不存存在在无无用用符符号的上下文无关语言产生号的上下文无关语言产生(证明略证明略)。12College of Computer Science&Technology,BUPT消去消去产生式产生式目的目的方便文法的设计方便文法的设计,利于文法规范化利于文法规范化.影响影响消去消去产生式产生式,除了文法不能产生字符串除

10、了文法不能产生字符串外，不会影响到原文法相应的语言中其它字符串外，不会影响到原文法相应的语言中其它字符串的产生的产生.可致空符号（可致空符号（nullable symbol）对于对于 CFG G=(N,T,P,S)，称符号称符号A N 是是可致可致空空的的，当且仅当，当且仅当A .消去消去产生式及其影响，需要计算可致空符号的产生式及其影响，需要计算可致空符号的集合集合.13College of Computer Science&Technology,BUPT算法算法3:生成无生成无文法文法定义定义:若G的生成式中无任何产生式,或只有一个生成式S且S不出现在任何生成式的右边,则称G为无文法

11、.思路思路对于CFGG=(NT,P,S)，可通过下列归纳步骤计算可致空符号集合：基础基础对于所有产生式对于所有产生式A ，A 是一个可致空符号是一个可致空符号归纳归纳如果有产生式如果有产生式B C1C2Ck，其中每一个其中每一个Ci N 是可致空符号，则是可致空符号，则B 是一个可致空符号；是一个可致空符号；14College of Computer Science&Technology,BUPT算法算法3:生成无生成无文法文法算法步骤算法步骤:(1)利用算法1,找出N=A|AN且A=+(找出能推导出的所有非终结符A)(2)用以下两步组成P1如果生成式A0C11C2CnnPn0且每个Ck(1

12、kn)均在N内而对于0jn,没有j在N内(i也可能是终结符)则P1应加入A0Y11Y22Ynn其中Yk或是Ck或是(即所有的可能组合)但A不加入P115College of Computer Science&Technology,BUPT算法算法3:生成无生成无文法文法算法步骤（续）算法步骤（续）:如果SN,则P1中应加入以下生成式S1|SS1是新的起始符N1=NS1如果SN,则N1=N,S1=S由此得出G1=(N1,T,P1,S1)16College of Computer Science&Technology,BUPT消去消去产生式产生式例例:(书书P137例例2)G=(N,T,P,S

13、)其中N=S,T=a,bP:SaSbS|bSaS|求其无文法G1=(N1,T,P1,S1)解解:(1)S=+N=S(2)P1的构造由SaSbS;加入SaSbS|abS|aSb|ab由SbSaS;加入SbSaS|baS|bSa|ba但S不加入P1由SN得出S1SN1=NS1=S,S117College of Computer Science&Technology,BUPT消去消去产生式产生式练习练习以下产生式表示的文法中以下产生式表示的文法中，D 为可致空符号：为可致空符号：S A;A 0BD;B 0BC;B 1;C 1;D .通过通过上述步骤，上述步骤，消去消去产生式产生式，得到如下产生式

14、集合：，得到如下产生式集合：S A;A 0BD;A 0B;B 0BC;B 1;C 1.18College of Computer Science&Technology,BUPT消去单产生式消去单产生式单产生式单产生式形如形如A B 的产生式，其中的产生式，其中A、B 为非为非终结符终结符.消去单产生式的目的消去单产生式的目的可简化某些证明，减少推可简化某些证明，减少推导步数导步数,利于文法规范化利于文法规范化.单元偶对（单元偶对（unit pairs）对于对于 CFG G=(N,T,P,S)，A，B N，称称(A，B)是是单元偶单元偶对对，当且仅当，当且仅当AB，且该推导过程仅使用过单产生式且

15、该推导过程仅使用过单产生式.消去单产生式时，需要计算所有单元偶对的集合消去单产生式时，需要计算所有单元偶对的集合.19College of Computer Science&Technology,BUPT消去单产生式消去单产生式思路思路设设 CFG G=(N,T,P,S)，对每个单元偶对对每个单元偶对(A，B)，在在G1 中加入产生式中加入产生式A ，其中其中B 为一个非单产生式；从为一个非单产生式；从而消去而消去G 中的单产生式，中的单产生式，得到得到CFG G1=(N,T,P1,S)：算法步骤算法步骤:(1)对每个对每个A N,构造非终结符集构造非终结符集NA=B|A=*B(NA是可由是可

16、由A推出的单生成式中的非终结符集推出的单生成式中的非终结符集)。构造方法分三步构造方法分三步:N0=AN=C|如果如果BC P且且B N0 N0若若NN0,则则N0=N,转向转向(继续迭代继续迭代)否则否则NA=N,转向转向(2).(已得到了完整的已得到了完整的NA)20College of Computer Science&Technology,BUPT消去单产生式消去单产生式算法步骤（续）算法步骤（续）:(2)构造构造P1:如如果果B P且且不不是是单单生生成成式式,则则对对于于B NA的的所所有有A,把把A加入到加入到P1中中(即即对对每每个个B NA(意意味味着着A=+B)的的非非单单

17、生生成成式式B P,直直接接将将与与NA的的A连连接接,构构成成新新产产生生式式A加加入到入到P1中中)(3)得到得到G1=(N1,T1,P1,S)21College of Computer Science&Technology,BUPTCFG的简化的简化小结小结设设 CFG G=(V,T,P,S)，可以通过下列步骤对可以通过下列步骤对G 进行简化进行简化：（1）消除消除G 中的中的产生式产生式；（2）消除消除G 中的单元产生式；中的单元产生式；（3）消除消除G 中的中的无用符号无用符号.结论结论设设 CFG G 的语言至少包含一个非的语言至少包含一个非的字符串，通的字符串，通过过上述步骤

18、上述步骤从从G 构造构造G1，则有则有L(G1)=L(G)-.注意注意以上简化步骤的次序以上简化步骤的次序.22College of Computer Science&Technology,BUPT消去单产生式消去单产生式（例）（例）例例:设设2型文法型文法G=(S,A,B,(,),+,*,a,P,S)P:SS+A|AAA*B|BB(S)|a构造无单生成式的文法构造无单生成式的文法G1解解:(1)构造构造NS,NA,NBN0=SN=C|BC P且且B N0 N0=A S=A,S N0N N0=N=A,S继续转继续转N=B A,S=B,A,S N0N N0=N=B,A,S继续转继续转有有N=B,

19、A,S=N0 NS=B,A,S同理可得同理可得:NA=A,B,NB=B23College of Computer Science&Technology,BUPT消去单产生式消去单产生式（续续）(2)构造构造P1对对NS=S,A,B SS+A P且不是单生成式且不是单生成式,且且S NS于是，将于是，将SS+A加到加到P1中中.又又AA*B P,A NS 将将SA*B加到加到P1中中.(SA,AA*B 直接用直接用SA*B代替这两条产生式代替这两条产生式)又又B(S)P,B NS 将将S（S）加到加到P1中中.又又Ba P,B NS 将将Sa加到加到P1中中.24College of Compu

21、G是递归文法。是递归文法。若存在若存在A=+AG是左递归文法是左递归文法若存在若存在A=+AG是右递归文法是右递归文法若存在若存在A=+AG是循环文法是循环文法26College of Computer Science&Technology,BUPT生成式的代换生成式的代换定义定义:2型文法中所有形如型文法中所有形如A的生成式称为的生成式称为A生成式生成式.引理引理1:对对A的的A生成式可进行变换生成式可进行变换设设G=(N,T,P,S)AB是是P中的生成式中的生成式,B N,(N T)*Br1|r2|rk是是P中的中的B生成式生成式可生成可生成G1=(N1,T,P1,S)P1中的生成式是将中

23、ter Science&Technology,BUPT生成式的代换生成式的代换其句子其句子aabbbaabbb的推导树为的推导树为即将子树根S用下一层的直接后代代替了.29College of Computer Science&Technology,BUPT消除直接左递归消除直接左递归引理引理2:消除直接左递归消除直接左递归设设G=(N,T,P,S),P中有中有A生成式生成式AA1|A2|Am|1|2|n其中其中i的第一个字符不是非终结符的第一个字符不是非终结符A(可以是其它非终结符可以是其它非终结符)可构成可构成G1=(N A,T,P1,S),A为新引入的非终结符为新引入的非终结符G1中的

24、中的P1为，将为，将P中的中的A生成式用以下生成式取代生成式用以下生成式取代A1|2|n|1A|2A|nAA1|2|m|1A|2A|mA证明思路证明思路:G和和G1二者的正则式都是二者的正则式都是(1+2+n)(1+m)*30College of Computer Science&Technology,BUPT消除直接左递归消除直接左递归（例）（例）例例:(书书P142例例4 4)SS+A|A,AA*B|B,B(S)|a1111可变换为可变换为SA A|ASS+A|+ASAB B|BAA*B*B|*BAB(S)(S)|a31College of Computer Science&Technol

25、ogy,BUPT消除直接左递归对推导树的影响消除直接左递归对推导树的影响G中局部：32College of Computer Science&Technology,BUPT消除左递归的算法消除左递归的算法Why消左递归消左递归?以后的句法分析算法不适用于左递归以后的句法分析算法不适用于左递归,会引起死循环。会引起死循环。对于给定的对于给定的2型文法型文法,该文法不存在无用符号该文法不存在无用符号,无循环且是无循环且是无无生成式的文法生成式的文法,为了消除为了消除G中可能存在的左递归中可能存在的左递归,构成一构成一个等效的无左递归的文法个等效的无左递归的文法G1,可用算法可用算法5。算法算法5在

26、原理上与求解正规表达式方程组的算法类似在原理上与求解正规表达式方程组的算法类似.33College of Computer Science&Technology,BUPT排列非终结符排列非终结符N=A1,A2,Ami:=1将将AiAi1|Ain|1|p变换为变换为Ai1|p|1Ai|pAi Ai 1|n|1Ai|nAi i=m i=m？Y Y 结束结束 i i：=i+1=i+1，j j：=1=1 对每个对每个AiAj，Aj1|n 用用Ai1|2|n代替代替 Y j=i-1Y j=i-1？N j N j：=j+1=j+1算法算法5:消除全部左递归消除全部左递归34College of Compu

27、ter Science&Technology,BUPTA1A2A3|a（1）A2A3A1|A1b（2）A3A1A2|A3A3|a（3）排序：排序：A1，A2，A3当当i=1对（对（1）变换，不用变。）变换，不用变。A1A2A3|a当当i=2对（对（2）变换）变换A2A3A1|A2A3b|ab（4）112消直接左递归消直接左递归A2A3A1|ab|A3A1A2|abA2（5）A2A3b|A3bA2（6）当当i=3，j=1A3A1A2|A3A3|aA2A3A2|aA2|A3A3|a（7）消除左递归消除左递归(示例示例)35College of Computer Science&Technology,BUPT112j=2A3A3A1A3A2|abA3A2|A3A1A2A3A2|abA2A3A2|aA2|A3A3|a（8）2334对（对（8）消直接左递归）消直接左递归A31A3|2A3|3A3|4A3|1|2|3|4A31|2|3|1A3|2A3|3A3|消除左递归消除左递归(示例示例)36College of Computer Science&Technology,BUPT作业作业Ch4习题：习题：6.8.9.37College of Computer Science&Technology,BUPT

展开阅读全文