《形式语言与自动机》课件ch4.2.ppt
《《形式语言与自动机》课件ch4.2.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件ch4.2.ppt(36页珍藏版)》请在文库网上搜索。
1、12023/6/7School of Computer Science,BUPT4.2上下文无关文法的变换上下文无关文法的变换nCFG的的简化化n消无用符号消无用符号n消消 产生式生式n消消单产生式生式n对生成式形式生成式形式进行行标准化准化22023/6/7School of Computer Science,BUPT生成式的标准形式生成式的标准形式nChomsky范式(CNF-ChomskyNormalForm)生成式形式为ABC,Aa,A,B,CN,aT(后面将证明,每个上下文无关文法都有一个CNF文法)nGreibach范式(GNF)生成式形式为Aa,aT,N*意义:对每个2型语言都可
2、找到一个文法使产生式的右端都以终结符开始中心思想:消除左递归.32023/6/7School of Computer Science,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.称符号
3、称符号X 是是可达可达符号符号(reachable symbol),当且仅当当且仅当存在存在,(N T)*,满足满足S X.42023/6/7School of Computer Science,BUPT计算生成符号(计算生成符号(generating symbol)集集计算可达符号(计算可达符号(reachable symbol)集集消去非生成符号、不可达符号消去非生成符号、不可达符号消去无用符号消去无用符号消去相关产生式消去相关产生式52023/6/7School of Computer Science,BUPT计算生成符号集计算生成符号集思路思路对于对于 CFG G=(N,T,P,S),
4、可通过下列归纳可通过下列归纳步骤计算生成符号集合:步骤计算生成符号集合:基础基础任何终结符任何终结符a T都是生成符号;都是生成符号;归纳归纳如果有产生式如果有产生式A ,其中其中 (N T)*的的每一个符号都是生成符号,则每一个符号都是生成符号,则A 也是生成符号;也是生成符号;62023/6/7School of Computer Science,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=N小
5、小结:算算法法1找找出出能能推推出出终结符符串串的的非非终结符符作作为有有用符号用符号.算法算法1:找出有用非终结符找出有用非终结符 72023/6/7School of Computer Science,BUPT一一层层向向外外扩展展,直直至至最最外外两两层相相等等为止止。所所得得集集合合即是算法即是算法1的有用符号。的有用符号。算法算法1:找出有用非终结符(图示)找出有用非终结符(图示)82023/6/7School of Computer Science,BUPT计算可达符号集计算可达符号集思路思路对于对于 CFG G=(N,T,P,S),可通过下列归纳可通过下列归纳步骤计算可达符号集合
6、:步骤计算可达符号集合:基础基础S是可达符号;是可达符号;归纳归纳如果如果A是可达符号,并且有产生式是可达符号,并且有产生式A ,其中其中 (N T)*,则则 中的每一个符号都是可中的每一个符号都是可达符号;达符号;92023/6/7School of Computer Science,BUPT算法步算法步骤:(1)N0=S(2)N=x|A N0且且Ax N0(N为有用符号集合有用符号集合)(3)如果如果N0N转(4),否否则转(5)(4)N0=N;转(2)(继续迭代下去迭代下去)(5)N0=NNT1=NTP1由由P内只含内只含N中符号的生成式中符号的生成式组成成(即即删去了从去了从S起不可达
7、的符号起不可达的符号).算法算法2:找出有用符号找出有用符号(从从S可达的符号可达的符号)102023/6/7School of Computer Science,BUPT一一层层外外扩,找出从找出从S可达的所有符号可达的所有符号(含非含非终结符和符和终结符符)算法算法2:找出从找出从S可达的符号可达的符号(图示)(图示)112023/6/7School of Computer Science,BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号例例:(书书P102例例1)已知已知2型文法型文法G=(S,A,B,a,P,S)P:SAB,Sa,Aa由算法由算法1:B推不出推不出终结符串符
8、串,删除之除之,并并删SAB.N1=S,A,P1:Sa,Aa由算法由算法2:A不出不出现在在S能推能推导出的句型中出的句型中,删除之除之.并并删Aa 结果果为G1=(S,a,Sa,S)应用算法用算法1和算法和算法2,可可删去文法中所有无用符号去文法中所有无用符号.122023/6/7School of Computer Science,BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号注意注意:必必须先先执行算法行算法1,再再执行算法行算法2,不能不能颠倒倒.否否则,可能可能导致无用符号不会被完全致无用符号不会被完全删除除.例例:上例中上例中,若先用算法若先用算法2,得得Sa,SAB
9、,Aa再用算法再用算法1,得得Sa,Aa。而而Aa是多余的是多余的.定理定理:任任何何非非空空的的上上下下文文无无关关语言言,可可由由不不存存在在无无用用符符号的上下文无关号的上下文无关语言言产生生(证明略明略)。132023/6/7School of Computer Science,BUPT消去消去 产生式产生式目的目的方便文法的设计方便文法的设计,利于文法规范化利于文法规范化.影响影响消去消去 产生式产生式,除了文法不能产生字符除了文法不能产生字符串串 外,不会影响到原文法相应的语言中其它字外,不会影响到原文法相应的语言中其它字符串的产生符串的产生.可致空符号(可致空符号(nullabl
10、e symbol)对于对于 CFG G=(N,T,P,S),称符号称符号A N 是是可致可致空空的的,当且仅当,当且仅当A .消去消去 产生式及其影响,需要计算可致空符号的产生式及其影响,需要计算可致空符号的集合集合.142023/6/7School of Computer Science,BUPT算法算法3:生成无生成无 文法文法定义定义:若G的生成式中无任何产生式,或只有一个生成式S且S不出现在任何生成式的右边,则称G为无文法.思路思路对于CFGG=(NT,P,S),可通过下列归纳步骤计算可致空符号集合:基础基础对于所有产生式对于所有产生式A ,A 是一个可致空符是一个可致空符号号归纳归纳
11、如果有产生式如果有产生式B C1C2Ck,其中每一个其中每一个Ci N 是可致空符号,则是可致空符号,则B 是一个可致空符号;是一个可致空符号;152023/6/7School of Computer Science,BUPT算法算法3:生成无生成无 文法文法算法步骤算法步骤:(1)利用算法1,找出N=A|AN且A=+(找出能推导出的所有非终结符A)(2)用以下两步组成P1如果生成式A0C11C2CnnPn0且每个Ck(1kn)均在N内而对于0jn,没有j在N内(i也可能是终结符)则P1应加入A0Y11Y22Ynn其中Yk或是Ck或是(即所有的可能组合)但A不加入P1162023/6/7Sch
12、ool of Computer Science,BUPT算法算法3:生成无生成无 文法文法算法步骤(续)算法步骤(续):如果SN,则P1中应加入以下生成式S1|SS1是新的起始符N1=NS1如果SN,则N1=N,S1=S由此得出G1=(N1,T,P1,S1)172023/6/7School of Computer Science,BUPT消去消去 产生式产生式例例:(书书P103例例2)G=(N,T,P,S)其中N=S,T=a,bP:SaSbS|bSaS|求其无文法G1=(N1,T,P1,S1)解解:(1)S=+N=S(2)P1的构造由SaSbS;加入SaSbS|abS|aSb|ab由SbSa
13、S;加入SbSaS|baS|bSa|ba但S不加入P1由SN得出S1SN1=NS1=S,S1182023/6/7School of Computer Science,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.192023/6/7School of Computer Science,BUPT消去单产生式消去单产生式单产生
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 ch4