第三章习题解答

第三章自上而下分析,习题解答,已知一个文法.消除文法的左递归、提取公共左因子（4分）.对得到的文法求First集合和Follow集合（4分）.对得到的文法构造一个预测分析表；（4分）.已知一个句子，给出分析过程。（3分）,题目类型,4.1对文法GSSa|(T)TT,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,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a),对(a,a),(a),a)的最左推导,S(T)(T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(S,S,S),S)(T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)(a,a),(T),S)(a,a),(S),S)(a,a),(a),S)(a,a),(a),a),Sa|(T)TT,S|S,文法GS,(2)改写文法为：0)Sa1)S2)S(T)3)TSN4)N,SN5)N,Sa|(T)TT,S|S,文法GS,procedureS;beginifsym=aorsym=thenabvanceelseifsym=(thenbeginadvance;T;ifsym=)thenadvance;elseerror;endelseerrorend;,procedureT;beginS;Nend,procedureNBeginifsym=,thenbeginadvance;s;Nendend,(2)改写文法为：0)Sa1)S2)S(T)3)TSN4)N,SN5)N,Sa|(T)TT,S|S,文法GS,非终结符FIRST集FOLLOW集Sa,(#,)Ta,()N,.),预测分析表,(3)对输入串（a,a）#的分析过程为：,栈剩余输入符所用产生式#S(a,a)#S(T)#)T(a,a)#)Ta,a)#TSN#)NSa,a)#Sa#)Naa,a)#)N,a)#N,SN#)NS,a)#)NSa)#Sa#)Naa)#)N)#N#)#,文法：,FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,(1),FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#,(2)考虑下列产生式:,FIRST(+E)FIRST()=+=FIRST(E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a)FIRST(b)FIRST()=,所以,该文法式LL(1)文法.,(3),(4),procedureE;beginifsym=(orsym=aorsym=borsym=thenbeginT;EendelseerrorendprocedureE;beginifsym=+thenbeginadvance;Eendelseifsym)andsym#thenerrorend,procedureT;beginifsym=(orsym=aorsym=borsym=thenbeginF;TendelseerrorendprocedureT;beginifsym=(orsym=aorsym=borsym=thenTelseifsym=*thenerrorend,procedureF;beginifsym=(orsym=aorsym=borsym=thenbeginP;FendelseerrorendprocedureF;beginifsym=*thenbeginadvance;Fendend,procedureP;beginifsym=aorsym=borsym=thenadvanceelseifsym=(thenbeginadvance;E;ifsym=)thenadvanceelseerrorendelseerrorend;,(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。(4)是，满足三个条件。,3,4.对下面文法Expr-ExprExpr(Expr)|VarExprTailExprTail-Expr|VaridVarTailVar