《形式语言与自动机》课件ch4.3.ppt

1、1School of Computer Science,BUPT4.3 Chomsky范式和范式和Greibach范式范式nChomsky范式定义：n 2型文法型文法G（N，T，P，S），），若生成式形式都若生成式形式都是是ABC和和Aa，A、B、CN，aT，则则G是是Chomsky范式。若范式。若L（G），），则则S是是P的一的一个生成式，但个生成式，但S不能在任何其它生成式的右边。不能在任何其它生成式的右边。n每个上下文无关文法都具有等效的每个上下文无关文法都具有等效的CNF（定理定理4.3.1）2School of Computer Science,BUPTCNF 的构成步骤的构成步骤1

2、.用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式2.对生成式对生成式AD1D2Dn n2 若若DiT，则引入新生成式则引入新生成式BiDi，Bi是新非终结符是新非终结符 若若DiN，则令则令BiDi，从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时，再将其变为时，再将其变为 AB1C1，C1B2C2，C2B3C3，Cn1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。定理证明定理证明自学自学3School of Computer Science,BUPTCNF 的构成例的构成例 例例:设设G（A，B，S，a，b，P，S

3、）是无是无、无循环、无循环、无无用符号、无单生成式的文法。无无用符号、无单生成式的文法。P：SaAB BA ABBB a BAS b 求等效的求等效的CNF G1解解：SBASBA，AaAa，BAS,BbBAS,Bb已是已是CNFCNF 加入到加入到P P1 1中中对对SaABSaAB，将其变换为将其变换为SCSCa aC C1 1，C Ca aaa，C C1 1ABAB 将将ABBBABBB变换为变换为ABCABC2 2，C C2 2BBBB.4School of Computer Science,BUPTCNF 的构成例的构成例 例例:2 2型文法型文法G G（AA，B B，SS，aa，b

4、b，P P，S S）P:SbAaB AbAAaSa BaBBbSb P:SbAaB AbAAaSa BaBBbSb 求等效的求等效的CNFCNF解解：SCSCb bACACa aB B，增加增加C Cb bbb，C Ca aaa AC ACb bDCDCa aSaSa，增加增加DAADAA BC BCa aECECb bSbSb，增加增加EBBEBB5School of Computer Science,BUPTGreibachGreibach范式范式n Greibach范式(GNF)定义：n2型文法G（N，T，P，S），若生成式的形式都是Aa，AN，aT，N*，且G不含生成式，则称G为Gre

5、ibach范式，记为GNF。n 任何2型文法都具有等效的GNF（定理4.3.2）6School of Computer Science,BUPTGNF 的构成步骤的构成步骤1.将将2 2型文法变换为型文法变换为CNFCNF。（。（AaAa，ABCABC形式）形式）2.2.将非终结符排序将非终结符排序,再进行代换。再进行代换。对形如对形如A Ai iAAj j（jijili）。）。3.3.消左递归。消左递归。对最高的对最高的A An nAAn n进行变换，使进行变换，使A An n生成式变为终结符开头。生成式变为终结符开头。4.4.回代。回代。将将A An n生成式回代入生成式回代入A An n

6、1 1生成式，使其右部首符为终结符，生成式，使其右部首符为终结符，将将A An n1 1生成式回代入生成式回代入A An n2 2生成式，使其右部首符为终结符生成式，使其右部首符为终结符 5.5.最后将消直接左递归时引入的最后将消直接左递归时引入的A A1 1、A A2 2、A An n生成式右部进行生成式右部进行代换。使其首符变为终结符。代换。使其首符变为终结符。7School of Computer Science,BUPTGNF 的构成例的构成例 例例:(书书P111 例例2)设已有设已有CNF：ABCABC，BCAb BCAb，CABa CABa，将其变换为将其变换为GNF。解解:按其

7、非终结符排列为按其非终结符排列为A A、B B、C C，A A是低位，是低位，C C是高位。是高位。、中，右部首符序号高于左部的非终结符、中，右部首符序号高于左部的非终结符 无需变换。无需变换。对，需要变换，对，需要变换，将代入得将代入得 CBCBa CBCBa ，仍需变换，仍需变换，将代入得将代入得 CCACBbCBa CCACBbCBa 8School of Computer Science,BUPTGNF 的构成例的构成例 对上述变换后所得结果消直接左递归对上述变换后所得结果消直接左递归 对对CCCCACBACBbCBbCBa a 变换为变换为 1 1 1 1 2 2 C C1 12 2

8、1 1C C2 2C CC C 1 11 1 C C即即 CbCBabCBCCbCBabCBC aC aC C CACBACBCACBACBC 9School of Computer Science,BUPTGNF 的构成例的构成例 回代回代将将C C的生成式回代入的生成式回代入B B的生成式的生成式 BBC CAb Ab 被变换为被变换为 BbCBAaAbCBCBbCBAaAbCBCAaCAaCAb Ab 将新的将新的B B生成式回代入生成式回代入A A的生成式的生成式 AAB BC C 被变换为被变换为 AbCBACaACbCBCAbCBACaACbCBCACaCACaCACbC ACbC 再将新的再将新的A A生成式代入新引入的生成式代入新引入的C C生成式生成式 C CA ACBCBA ACBCCBC 被变换为被变换为 （略）略）注意：新引入的注意：新引入的A Ai i相当于排在最低位。相当于排在最低位。