资源描述:
《编译原理第五章》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第五章2.对下面的文法G:EàTE/E/à+E
2、εTàFT/T/àT
3、εFàPF/F/à*F/
4、εPà(E)
5、a
6、b
7、^(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)
8、∪{ε}={(,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/)
9、=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
10、(T/)={+,),#};SELECT(FàPF/)=FIRST(P)={(,a,b,^};SELECT(F/à*F/)={*};SELECT(F/àε)=FOLLOW(F/)={(,a,b,^,+,),#};SELECT(Pà(E))={(}SELECT(Pàa)={a}SELECT(Pàb)={b}SELECT(Pà^)={^}可见,相同左部产生式的SELECT集的交集均为空,所以文法G[E]是LL(1)文法。(3)构造它的预测分析表。文法G[E]的预测分析表如下:+*()ab^#EàTE/àTE/àTE/àTE/E/à+EàεàεTàFT/àFT/àFT/àFT/T/àεàTàεà
11、TàTàTàεFàPF/àPF/àPF/àPF/F/àεà*F/àεàεàεàεàεàεPà(E)àaàbà^(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下:charCH;//存放当前的输入符号voidP_E()//非终结符E的子程序{if(IsIn(CH,FIRST_TEP))//FIRST_TEP为TàTE/的右部的FIRST集合,产生式EàTE/{P_T();P_EP();}elseERR;}voidP_EP()//非终结符E/的子程序{if(CH==’+’)//产生式E/à+E{READ(CH);P_E();}else//产生式E/àε{if(IsIn
12、(CH,FOLLOW_EP))//FOLLOW_EP为E/的FOLLOW集合return;elseERR;}}voidP_T()//非终结符T的子程序{if(IsIn(CH,FIRST_FTP))//FIRST_TEP为TàFT/的右部的FIRST集合,产生式TàFT/{P_F();P_TP();}elseERR;}voidP_TP()//非终结符T/的子程序{if(IsIn(CH,FIRST_T))//FIRST_T为产生式T/àT的右部的FIRST集合,产生式T/àT{P_T();}else//产生式T/àε{if(IsIn(CH,FOLLOW_TP))//FOLLOW_TP为T/的
13、FOLLOW集合return;elseERR;}}voidP_F()//非终结符F的子程序{if(IsIn(CH,FIRST_PFP))//FIRST_PFP为FàPF/的右部的FIRST集合,产生式FàPF/{P_P();P_FP();}elseERR;}voidP_FP()//非终结符F/的子程序{if(CH==’*’)//产生式F/à*F/{READ(CH);P_FP();}else//产生式F/àε{if(IsIn(CH,F