08.語(yǔ)法分析文法等價(jià)變換

1、第三章：語(yǔ)法分析 文法等價(jià)變換增加拓廣產(chǎn)生式定理一：對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，G2的開始符不出現(xiàn)于任何產(chǎn)生式的右部。證明：假設(shè)S是G1的開始符，若S出現(xiàn)在某規(guī)則的右部，則引入新的語(yǔ)法符號(hào)S，增加一條新產(chǎn)生式SS即可，其中S是新的開始符。刪除無(wú)用規(guī)則定理二：對(duì)任一文法G1都可以構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中的每個(gè)非終極符必出現(xiàn)在它的某個(gè)句型中。證明：根據(jù)G1，構(gòu)造文法G2的方法如下：令=S，S是文法G1的開始符遞歸擴(kuò)充 =B|AxBy, BVN, A。若A，則刪除以A為左部的所有產(chǎn)生式。刪除無(wú)用規(guī)則例子：ZaB|bcBbC|aAaB|aCc

2、DAB|a1.=Z2.=Z,B2.=Z,B,CA,D無(wú)用3.ZaB|bc BbC|a Cc消除特型產(chǎn)生式定義特型產(chǎn)生式：AB，且BVN定理三：對(duì)任一文法G1，可以構(gòu)造文法G2，使得L(G1)=L(G2)，且在G2中沒(méi)有特型產(chǎn)生式。證明：G2的構(gòu)造如下：對(duì)文法G1中任意非終極符A，求集合 A=B | A+B, BVN。若BA，且B是文法G中的一個(gè)非特型產(chǎn)生式，則補(bǔ)充如下規(guī)則A。去掉文法G1中的所有的特型產(chǎn)生式。去掉新的文法中的無(wú)用產(chǎn)生式。消除特型產(chǎn)生式例子AB|D|aBBC|bCcDB|dA=B,C,DB=CC=D=B,C補(bǔ)充規(guī)則：Ab|c|dBcDb|c刪去特型產(chǎn)生式：Ab|c|d|aBBc|

3、bCcDb|c|d刪去無(wú)用產(chǎn)生式：Ab|c|d|aBBc|b消除特型產(chǎn)生式例子EE+TETTT*FTFF(E)|iE=T,FT=FF=補(bǔ)充規(guī)則：ET*F|i|(E)T(E)|i刪去特型產(chǎn)生式：EE+T|T*F|i|(E)TT*F|(E)|iF(E)|i刪去無(wú)用產(chǎn)生式：EE+T|T*F|i|(E)TT*F|(E)|iF(E)|i消除空產(chǎn)生式空產(chǎn)生式：APASCAL語(yǔ)言例子： var |定理四：對(duì)任一文法G1，可構(gòu)造文法G2，使得L(G1)=L(G2)，且G2中無(wú)空產(chǎn)生式。消除空產(chǎn)生式=A|A，直接推出空的非終極符=A|A +, +，遞歸擴(kuò)展隱式的可以推出空的非終極符對(duì)于文法中任意產(chǎn)生式 AX1X

4、i-1XiXi+1Xn(n2),若Xi， 補(bǔ)充規(guī)則 A X1X2Xi-1Xi+1Xn 重復(fù)3，直到不產(chǎn)生新的產(chǎn)生式。刪除所有形如A的產(chǎn)生式。消除空產(chǎn)生式例子AaBcDBb|DBB|d=B 直接=B,D 隱式擴(kuò)充：由AaBcD 有AaBc AacD由AaBc有Aac由DBB 有DB刪去空產(chǎn)生式BAaBcD|acD| aBc|acBbDBB|B|d提取公共前綴公共前綴:A的不同產(chǎn)生式的右部具有相同的前綴A1 | 2 | n | 1| 2 | m (其 中每個(gè)不以開頭)則將這些規(guī)則寫成： AA| 1 |2|m A1 | 2 |n 提取公共前綴例子：AaB|aC|cDBbB|bD|cDd提取公共前綴AaAAB|C|DBbB|cBB|DDd消除直接左遞歸對(duì)于簡(jiǎn)單情形AA| 即有A* 則轉(zhuǎn)化 AA AA| 對(duì)于一般情形 AA1 | A2 | Am | 1 | 2| | n 則轉(zhuǎn)化A( 1 | 2 | n ) AA(1 | 2 | m) A | 消除直接左遞歸例子E E+T | TT T *F | FF ( E ) | iAA| EE+T | T=+T =TETEE+TE|ETEE+TE|TFTT*FT|F ( E ) | i消除左遞歸基本思想： 類似于方程中的代入，把所有的形如AB中的B作為左部的規(guī)則代入，然后消除文法中