编译原理第五章作业参考答案

编译原理习题解答页1/1第五章自顶向下语法分析方法1．对文法G[S]Sa|∧|(T)TT,S|S(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否是LL(1)的？给出它的预测分析表。(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。解：(1)(a,(a,a))的最左推导为S(T)(T,S)(S,S)(a,(T))(a,(T,S))(a,(S,a))(a,(a,a))(((a,a),∧,(a)),a)的最左推导为S(T)(T,S)(S,a)((T),a)((T,S),a)((T,S,S),a)((S,∧,(T)),a)(((T),∧,(S)),a)(((T,S),∧,(a)),a)(((S,a),∧,(a)),a)(((a,a),∧,(a)),a)(2)由于有TT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/[S]:Sa|∧|(T)TSUU，SU|ε分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1)对于每个非终结号U，编写一个相应的子程序P(U)；(2)对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IFCHINFIRST(x1)THENP(x1)ELSEIFCHINFIRST(x2)THENP(x2)ELSE......IFCHINFIRST(xn)THENP(xn)ELSEERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。(3)对于符号串x=y1y2...yn;p(x)的含义为：BEGINP(y1);P(y2);...P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IFCH=yiTHENREAD(CH)ELSEERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。(4)如果文法中有空规则U::=EPSILON,则算法中的语句IFCHINFIRST(xn)THENP(xn)编译原理习题解答页2/2ELSEERROR改写为：IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURNERROR(5)要分析一个OrgStr,应在该串的后面加上一个串括号'#',并从子程序P(S)(S为文法的开始符号)开始，如果中途没有产生错误，并且最后CH='#',则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：charCH;//存放当前的输入符号voidP_S()//非终结符S的子程序{if(CH==’a’)READ(CH);//产生式Saelseif(CH==’^’)READ(CH);//产生式S^elseif(CH==’(’)//产生式S(T){READ(CH);P_T();IF(CH==’)’)THENREAD(CH)elseERROR}elseERR;}voidP_T()//非终结符S的子程序{if(IsIn(CH,FIRST_SU))//FIRST_SU为TSU的右部的FIRST集合{P_S();P_U();}}voidP_U()//非终结符U的子程序{if(CH==’,’)//产生式U，SU{READ(CH);P_S();P_U();}else//产生式Uε{if(IsIn(CH,FOLLOW_U))//FOLLOW_U为U的FOLLOW集合return;elseERR;}}(3)判断文法G/[S]是否为LL(1)文法。各非终结符的FIRST集合如下：FIRST(S)={a,∧,（}FIRST(T)=FIRST(S)={a,∧,（}FIRST(U)={，,ε}各非终结符的FOLLOW集合如下：FOLLOW(S)={#}∪FIRST(U)∪FOLLOW(T)∪FOLLOW(U)={#,，,)}FOLLOW(T)={)}FOLLOW(U)=FOLLOW(T)={)}每个产生式的SELECT集合如下：编译原理习题解答页3/3SELECT(Sa)={a}SELECT(S∧)={∧}SELECT(S(T))={(}SELECT(TSU)=FIRST(S)={a,∧,（}SELECT(U，SU)={，}SELECT(Uε)=FOLLOW(U)={)}可见，相同左部产生式的SELECT集的交集均为空，所以文法G/[S]是LL(1)文法。文法G/[S]的预测分析表如下：a∧()，#Sa∧(T)TSUSUSUUε，SU(5)给出输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式123456789101112#S#)T(#)T#)US#)Ua#)U#)US,#)US#)Ua#)U#)#(a,a)#(a,a)#a,a)#a,a)#a,a)#,a)#,a)#a)#a)#)#)##S(T)(匹配TSUSaa匹配U，SU,匹配Saa匹配Uε)匹配接受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,^,ε};编译原理习题解答页4/4FIRST(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)={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ε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为ETE/的右部的FIRST集合，产生式ETE/{P_T();P_EP();}编译原理习题解答页5/5elseERR;}voidP_EP()//非终结符E/的子程序{if(CH==’+’)//产生式E/+E{READ(CH);P_E();}else//产生式E/ε{if(IsIn(CH,FOLLOW_EP))//FOLLOW_EP为E/的FOLLOW集合return;elseERR;}}voidP_T()//非终结符T的子程序{if(IsIn(CH,FIRST_FTP))//FIRST_FTP为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/的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,FOLLOW_FP))//FOLLOW_FP为F/的FOLLOW集合return;elseERR;}编译原理习题解答页6/6}voidP_P()//非终结符P的子程序{if(CH==’(‘){READ(CH);P_E();if(CH==’)’)READCH(CH);elseERR;}elseif(CH==’a’)READ(CH);elseif(CH==’b’)READ(CH);elseif(CH==’^’)READ(CH);elseERR;}3．已知文法G[S]：SMH|aHLSo|εKdML|εLeHfMK|bLM判断G是否是LL（1）文法，如果是，构造LL（1）分析表。解：首先求各非终结符的FIRST集合：FIRST(S)={a}∪FIRST(M)∪FIRST(H)={a}∪{b,d,ε}∪{e,ε}={a,b,d,e,ε};FIRST(H)=FIRST(L)∪{ε}={e,ε};FIRST(K)={d,ε};FIRST(L)={e};FIRST(M)=FIRST(K)∪{b}={b,d,ε};然后求非终结符的FOLLOW集合：FOLLOW(S)={o,#}FOLLOW(H)=FOLLOW(S)∪{f}={f,o,#}FOLLOW(K)=FOLLOW(M)=FIRST(H)∪FOLLOW(S)={e,o,#};//不包含εFOLLOW(L)=FIRST(S)∪{o}∪FOLLOW(K)∪FIRST(M)∪FOLLOW(M)={a,b,d,e,o,#}∪FOLLOW(M)={a,b,d,e,o,#};//不包含εFOLLOW(M)=FIRST(L)∪FIRST(H)∪FOLLOW(S)={e,o,#}//不包含ε最后求各产生式的SELECT集合：SELECT(SMH)=(FIRST(MH)-{ε})∪FOLLOW