编译原理第五章(共4页).docx

《编译原理第五章(共4页).docx》由会员分享，可在线阅读，更多相关《编译原理第五章(共4页).docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第五章2对下面的文法G：ETE/E/+E|TFT/T/T|FPF/F/*F/|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个方法是LL(1)的。(3) 构造它的预测分析表。(4) 构造它的递归下降分析程序。解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E/)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T/)=FIRST(T)=(,a,b,

2、;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F/)=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;/不包含FOLLOW(T/)=FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;/不包含FOLLOW(F/)=FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;FOLLO

3、W(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(ETE/)=FIRST(T)=(,a,b,;SELECT(E/+E)=+;SELECT(E/)=FOLLOW(E/)=),#SELECT(TFT/)=FIRST(F)=(,a,b,;SELECT(T/T)=FIRST(T)=(,a,b,;SELECT(T/)=FOLLOW(T/)=+,),#;SELECT(FPF/)=FIRST(P)=(,a,b,;SELECT(F/*F/)=*;SELECT(F/)=FOLLOW(F/)=(,a,b

4、,+,),#;SELECT(P(E)=(SELECT(Pa)=aSELECT(Pb)=bSELECT(P)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(3)构造它的预测分析表。文法GE的预测分析表如下：+*()ab#ETE/TE/TE/TE/E/+ETFT/FT/FT/FT/T/TTTTFPF/PF/PF/PF/F/*F/P(E)ab(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_E()/非终结符E的子程序if(IsIn(CH,FIRST_TEP) /FIRST_TEP为TTE/

5、 的右部的FIRST集合，产生式ETE/P_T();P_EP();else ERR;void P_EP()/非终结符E/的子程序if(CH=+) /产生式E/+EREAD(CH);P_E();else/产生式E/if(IsIn(CH,FOLLOW_EP) /FOLLOW_EP为E/的FOLLOW集合return ;else ERR;void P_T()/非终结符T的子程序if(IsIn(CH,FIRST_FTP) /FIRST_TEP为TFT/ 的右部的FIRST集合，产生式TFT/P_F();P_TP();else ERR;void P_TP()/非终结符T/的子程序if(IsIn(CH,F

6、IRST_T) /FIRST_T为产生式T/T 的右部的FIRST集合，产生式T/TP_T();else/产生式T/if(IsIn(CH,FOLLOW_TP) /FOLLOW_TP为T/的FOLLOW集合return ;else ERR;void P_F()/非终结符F的子程序if(IsIn(CH,FIRST_PFP) /FIRST_PFP为FPF/ 的右部的FIRST集合，产生式FPF/ P_P();P_FP();else ERR;void P_FP()/非终结符F/的子程序if(CH=*) /产生式F/*F/READ(CH);P_FP();else/产生式F/if(IsIn(CH,FOLL

7、OW_FP) /FOLLOW_FP为F/的FOLLOW集合return ;else ERR;void P_P()/非终结符P的子程序if(CH=()READ(CH);P_E();if(CH=) READCH(CH);elseERR;else if(CH=a) READ(CH);else if(CH=b) READ(CH);else if(CH=) READ(CH);else ERR;4证明下述文法不是LL（1）的。 S-C$ C-bA|aB A-a|aC|bAA B-b|bC|aBB 你能否构造一等价的文法，使其是LL（1）的，并给出判断过程。【解】因为SELECT(A-a)SELECT(A-

8、aC),根据LL（1）文法的判定条件： (1)文法不含左递归 (2)对于文法U的任意两个不同的规则有: Select(U) Select(Ub)=一个文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL（1）文法。 该文法含公共因子，消除后的文法为： S-C$ C- bA|aB A-aA|bAA A-C| B-bB| aBB B-C| 【证明】因为SELECT(C- bA) SELECT(C-aB)= SELECT(A-Aa) SELECT(A-bAA) = SELECT(A-C) SELECT(A-)=(FIRST(C)- )FOLLOW(A) 因此消除公共因子后得到文法也不是LL（1）文法。专心-专注-专业