形式语言与自动机课件上下文无关文法

1CollegeofComputerScience&Technology,BUPT§4.2上下文无关文法的变换CFG的简化消无用符号消产生式消单产生式对生成式形式进行标准化2CollegeofComputerScience&Technology,BUPT生成式的标准形式Chomsky范式(CNF-ChomskyNormalForm)生成式形式为A→BC,A→a,A,B,C∈N,a∈T(后面将证明,每个上下文无关文法都有一个CNF文法)Greibach范式(GNF)生成式形式为A→aβ,a∈T,β∈N*意义:对每个2型语言都可找到一个文法使产生式的右端都以终结符开始中心思想:消除左递归.3CollegeofComputerScience&Technology,BUPT变换算法--消去无用符号无用符号（uselesssymbol）–非生成符号–不可达符号有用符号（usefulsymbol）对于CFGG=(N,T,P,S)，称符号XNT是有用的，当且仅当SXw，其中wT*，,(NT)*.–称符号X是生成符号（generatingsymbol），当且仅当存在wT*，满足Xw.–称符号X是可达符号（reachablesymbol），当且仅当存在,(NT)*，满足SX.4CollegeofComputerScience&Technology,BUPT计算生成符号（generatingsymbol）集计算可达符号（reachablesymbol）集消去非生成符号、不可达符号消去无用符号消去相关产生式5CollegeofComputerScience&Technology,BUPT计算生成符号集思路对于CFGG=(N,T,P,S)，可通过下列归纳步骤计算生成符号集合：基础任何终结符aT都是生成符号；归纳如果有产生式A，其中(NT)*的每一个符号都是生成符号，则A也是生成符号；6CollegeofComputerScience&Technology,BUPT步骤:(1)N0=(赋为)N0为有用的非终结符集(2)N’={A|A→ω且ω∈T*}N’为非终结符集合(3)如果N0≠N’则转(4),否则转(6)(4)N0=N’(5)N’=N0∪{A|A→α且α∈(T∪N0)*},转(3)(6)N1=N’小结:算法1找出能推出终结符串的非终结符作为有用符号.算法1:找出有用非终结符7CollegeofComputerScience&Technology,BUPT一层层向外扩展，直至最外两层相等为止。所得集合即是算法1的有用符号。算法1:找出有用非终结符（图示）N0=空N'={A|A→ω且ω∈T*}A1A3A2N''=N0∪{B|B→α且α∈(T∪N')*}B2B18CollegeofComputerScience&Technology,BUPT计算可达符号集思路对于CFGG=(N,T,P,S)，可通过下列归纳步骤计算可达符号集合：基础S是可达符号；归纳如果A是可达符号，并且有产生式A，其中(NT)*，则中的每一个符号都是可达符号；9CollegeofComputerScience&Technology,BUPT算法步骤:(1)N0={S}(2)N’={x|A∈N0且A→αxβ}∪∈N0(N’为有用符号集合)(3)如果N0≠N’转(4),否则转(5)(4)N0=N’;转(2)(继续迭代下去)(5)N0=N’∩NT1=N’∩TP1由P内只含N’中符号的生成式组成(即删去了从S起不可达的符号).算法2:找出有用符号(从S可达的符号)10CollegeofComputerScience&Technology,BUPT一层层外扩,找出从S可达的所有符号(含非终结符和终结符)算法2:找出从S可达的符号（图示）N0=SN'={x|A∈N0且A→αxβ}∪N0A1A3A2N''αC1βαC2β11CollegeofComputerScience&Technology,BUPT消去非生成符号及不可达符号例:(书P135例1)已知2型文法G=({S,A,B},{a},P,S)P:S→AB,S→a,A→a由算法1:B推不出终结符串,删除之,并删S→AB.N1={S,A},P1:S→a,A→a由算法2:A不出现在S能推导出的句型中,删除之.并删A→a∴结果为G1=({S},{a},{S→a},S)应用算法1和算法2,可删去文法中所有无用符号.12CollegeofComputerScience&Technology,BUPT消去非生成符号及不可达符号注意:必须先执行算法1,再执行算法2,不能颠倒.否则,可能导致无用符号不会被完全删除.例:上例中,若先用算法2,得S→a,A→AB,A→a再用算法1,得S→a,A→a。而A→a是多余的.定理:任何非空的上下文无关语言,可由不存在无用符号的上下文无关语言产生(证明略)。13CollegeofComputerScience&Technology,BUPT消去产生式目的方便文法的设计,利于文法规范化.影响消去产生式,除了文法不能产生字符串外，不会影响到原文法相应的语言中其它字符串的产生.可致空符号（nullablesymbol）对于CFGG=(N,T,P,S)，称符号AN是可致空的，当且仅当A.消去产生式及其影响，需要计算可致空符号的集合.14CollegeofComputerScience&Technology,BUPT算法3:生成无文法定义:若G的生成式中无任何产生式,或只有一个生成式S→ε且S不出现在任何生成式的右边,则称G为无文法.思路对于CFGG=(NT,P,S)，可通过下列归纳步骤计算可致空符号集合：基础对于所有产生式A，A是一个可致空符号归纳如果有产生式BC1C2…Ck，其中每一个CiN是可致空符号，则B是一个可致空符号；15CollegeofComputerScience&Technology,BUPT算法3:生成无文法算法步骤:(1)利用算法1,找出N’={A|A∈N且A=+ε}(找出能推导出的所有非终结符A)(2)用以下两步组成P1①如果生成式A→β0C1β1C2…Cnβn∈Pn≥0且每个Ck(1≤k≤n)均在N’内而对于0≤j≤n,没有βj在N’内(βi也可能是终结符)则P1应加入A→β0Y1β1Y2β2…Ynβn其中Yk或是Ck或是ε(即所有的可能组合)但A→ε不加入P116CollegeofComputerScience&Technology,BUPT算法3:生成无文法算法步骤（续）:②如果S∈N’,则P1中应加入以下生成式S1→ε|SS1是新的起始符N1=N∪{S1}如果SN’,则N1=N,S1=S由此得出G1=(N1,T,P1,S1)17CollegeofComputerScience&Technology,BUPT消去产生式例:(书P137例2)G=(N,T,P,S)其中N={S},T={a,b}P:S→aSbS|bSaS|ε求其无ε文法G1=(N1,T,P1,S1)解:(1)∵S=+ε∴N’={S}(2)①P1的构造由S→aSbS;加入S→aSbS|aεbS|aSbε|aεbε由S→bSaS;加入S→bSaS|bεaS|bSaε|bεaε但S→ε不加入P1由S∈N’得出S1→ε∣SN1=N∪{S1}={S,S1}18CollegeofComputerScience&Technology,BUPT消去产生式练习以下产生式表示的文法中，D为可致空符号：SA;A0BD;B0BC;B1;C1;D.通过上述步骤，消去产生式，得到如下产生式集合：SA;A0BD;A0B;B0BC;B1;C1.19CollegeofComputerScience&Technology,BUPT消去单产生式单产生式形如AB的产生式，其中A、B为非终结符.消去单产生式的目的可简化某些证明，减少推导步数,利于文法规范化.单元偶对（unitpairs）对于CFGG=(N,T,P,S)，A，BN，称(A，B)是单元偶对，当且仅当AB，且该推导过程仅使用过单产生式.消去单产生式时，需要计算所有单元偶对的集合.20CollegeofComputerScience&Technology,BUPT消去单产生式思路设CFGG=(N,T,P,S)，对每个单元偶对(A，B)，在G1中加入产生式A，其中B为一个非单产生式；从而消去G中的单产生式，得到CFGG1=(N,T,P1,S)：算法步骤:(1)对每个A∈N,构造非终结符集NA={B|A=*B}(NA是可由A推出的单生成式中的非终结符集)。构造方法分三步:①N0={A}②N’={C|如果B→CP且BN0}∪N0③若N’≠N0,则N0=N’,转向②(继续迭代)否则NA=N’,转向(2).(已得到了完整的NA)21CollegeofComputerScience&Technology,BUPT消去单产生式算法步骤（续）:(2)构造P1:如果B→αP且不是单生成式,则对于B∈NA的所有A,把A→α加入到P1中(即对每个BNA(意味着A=+B)的非单生成式B→αP,直接将α与NA的A连接,构成新产生式A→α加入到P1中)(3)得到G1=(N1,T1,P1,S)N0=AB1B2NAC1C222CollegeofComputerScience&Technology,BUPTCFG的简化小结设CFGG=(V,T,P,S)，可以通过下列步骤对G进行简化：（1）消除G中的产生式；（2）消除G中的单元产生式；（3）消除G中的无用符号.结论设CFGG的语言至少包含一个非的字符串，通过上述步骤从G构造G1，则有L(G1)=L(G)-{}.注意以上简化步骤的次序.23CollegeofComputerScience&Technology,BUPT消去单产生式（例）例:设2型文法G=({S,A,B},{(,),+,*,a},P,S)P:S→S+A|AA→A*B|BB→(S)|a构造无单生成式的文法G1解:(1)构造NS,NA,NB①N0={S}②N’={C|B→CP且BN0}∪N0={A}∪{S}={A,S}③∵N0≠N’∴N0=N’={A,S}继续转②N’={B}∪{A,S}={B,A,S}∵N0≠N’∴N0=N’={B,A,S}继续转②有N’={B,A,S}=N0∴NS={B,A,S}同理可得:NA={A,B},NB={B}24CollegeofComputerScience&Technology,BUPT消去单产生式（续）(2)构造P1对NS={S,A,B}∵S→S+AP且不是单生成式,且SNS于是，将S→S+A加到P1中.又∵A→A*BP,ANS∴将S→A*B加到P1中.(∵S→A,A→A*B∴直接用S→A*B代替这两条产生式)又∵B→(S)P,BNS∴将S→（S）加到P1中.又∵B→aP,BNS∴将S→a加到P1中.25CollegeofComputerScience&Technology,BUPT消去单产生式（续）同理:对NA={A,B}∵A→A*BP且非单生成式,ANA∴将A→A*B加到P1中.∵B→(S)|a∈P且非单生成式,BNA∴将A→(S)|a加到P1中.同理:对NB={B}将B→(S)|a加到P1中.结果:P1为S→S+A|A*B|(S)|aA→A*B|(S)|aB→(S)|a26CollegeofComputerScience&Technology,BUPT消除递归递归的定义:在2型文法中若存在A=+αAβ,A∈N，则称G是递归文法。若存在A=+AβG是左递归文法若存在A=+αAG是右递归文法若存在A=+AG是循环文法27CollegeofComputerScience&Technology,BUPT生成式的代换定义: