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

《形式语言自动机——上下文无关文法与下推自动机(二).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4.2上下文无关文法的变换CFG的简化消无用符号消产生式消单产生式对生成式形式进行标准化1CollegeofComputerScience&Technology,BUPT生成式的标准形式Chomsky范式(CNF-ChomskyNormalForm)生成式形式为A→BC,A→a,A,B,C∈N,a∈T(后面将证明,每个上下文无关文法都有一个CNF文法)Greibach范式(GNF)生成式形式为A→aβ,a∈T,β∈N*意义:对每个2型语言都可找到一个文法使产生式的右端都以终结符开始中心思想:消除左

2、递归.2CollegeofComputerScience&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)*，满

3、足SX.3CollegeofComputerScience&Technology,BUPT计算生成符号（generatingsymbol）集计算可达符号（reachablesymbol）集消去非生成符号、不可达符号消去无用符号消去相关产生式4CollegeofComputerScience&Technology,BUPT计算生成符号集思路对于CFGG=(N,T,P,S)，可通过下列归纳步骤计算生成符号集合：基础任何终结符aT都是生成符号；归纳如果有产生式A，其中(NT)*的每

4、一个符号都是生成符号，则A也是生成符号；5CollegeofComputerScience&Technology,BUPT步骤:(1)N0=(赋为)N0为有用的非终结符集(2)N’={A

5、A→ω且ω∈T*}N’为非终结符集合(3)如果N0≠N’则转(4),否则转(6)(4)N0=N’(5)N’=N0∪{A

6、A→α且α∈(T∪N0)*},转(3)(6)N1=N’小结:算法1找出能推出终结符串的非终结符作为有用符号.算法1:找出有用非终结符6CollegeofComputerScience&Techn

7、ology,BUPT一层层向外扩展，直至最外两层相等为止。所得集合即是算法1的有用符号。算法1:找出有用非终结符（图示）7CollegeofComputerScience&Technology,BUPT计算可达符号集思路对于CFGG=(N,T,P,S)，可通过下列归纳步骤计算可达符号集合：基础S是可达符号；归纳如果A是可达符号，并且有产生式A，其中(NT)*，则中的每一个符号都是可达符号；8CollegeofComputerScience&Technology,BUPT算法步骤:(1)N0

8、={S}(2)N’={x

9、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可达的符号)9CollegeofComputerScience&Technology,BUPT一层层外扩,找出从S可达的所有符号(含非终结符和终结符)算法2:找出从S可达的符号（图示）10CollegeofCompu

10、terScience&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,可删去文法中所有无用符号.11CollegeofComputerScience&Technology,BUPT消去

11、非生成符号及不可达符号注意:必须先执行算法1,再执行算法2,不能颠倒.否则,可能导致无用符号不会被完全删除.例:上例中,若先用算法2,得S→a,A→AB,A→a再用算法1,得S→a,A→a。而A→a是多余的.定理:任何非空的上下文无关语言,可由不存在无用符号的上下文无关语言产生(证明略)。12CollegeofComputerScience&Technology,BUPT消去产生式目的方便文法的设计,利于文法规范化.影响消去产生式,除了文法不能产生字