编译原理第五章(共4页).docx
精选优质文档-倾情为你奉上第五章2对下面的文法G：EàTE/E/à+E|TàFT/T/àT|FàPF/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,;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,+,),#;FOLLOW(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(EàTE/)=FIRST(T)=(,a,b,;SELECT(E/à+E)=+;SELECT(E/à)=FOLLOW(E/)=),#SELECT(TàFT/)=FIRST(F)=(,a,b,;SELECT(T/àT)=FIRST(T)=(,a,b,;SELECT(T/à)=FOLLOW(T/)=+,),#;SELECT(FàPF/)=FIRST(P)=(,a,b,;SELECT(F/à*F/)=*;SELECT(F/à)=FOLLOW(F/)=(,a,b,+,),#;SELECT(Pà(E)=(SELECT(Pàa)=aSELECT(Pàb)=bSELECT(Pà)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(3)构造它的预测分析表。文法GE的预测分析表如下：+*()ab#EàTE/àTE/àTE/àTE/E/à+EààTàFT/àFT/àFT/àFT/T/ààTààTàTàTàFàPF/àPF/àPF/àPF/F/àà*F/ààààààPà(E)àaàbà(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_E()/非终结符E的子程序if(IsIn(CH,FIRST_TEP) /FIRST_TEP为TàTE/ 的右部的FIRST集合，产生式EàTE/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为TàFT/ 的右部的FIRST集合，产生式TàFT/P_F();P_TP();else ERR;void P_TP()/非终结符T/的子程序if(IsIn(CH,FIRST_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为FàPF/ 的右部的FIRST集合，产生式FàPF/ P_P();P_FP();else ERR;void P_FP()/非终结符F/的子程序if(CH=*) /产生式F/à*F/READ(CH);P_FP();else/产生式F/àif(IsIn(CH,FOLLOW_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->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）文法。专心-专注-专业
