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

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

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

4、i-1XiXi+1Xn(n2),若Xi， 補充規則 A X1X2Xi-1Xi+1Xn 重復3，直到不產生新的產生式。刪除所有形如A的產生式。消除空產生式例子AaBcDBb|DBB|d=B 直接=B,D 隱式擴充：由AaBcD 有AaBc AacD由AaBc有Aac由DBB 有DB刪去空產生式BAaBcD|acD| aBc|acBbDBB|B|d提取公共前綴公共前綴:A的不同產生式的右部具有相同的前綴A1 | 2 | n | 1| 2 | m (其 中每個不以開頭)則將這些規則寫成： AA| 1 |2|m A1 | 2 |n 提取公共前綴例子：AaB|aC|cDBbB|bD|cDd提取公共前綴AaAAB|C|DBbB|cBB|DDd消除直接左遞歸對于簡單情形AA| 即有A* 則轉化 AA AA| 對于一般情形 AA1 | A2 | Am | 1 | 2| | 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作為左部的規則代入，然后消除文法中