(完整版)编译原理第五章作业参考答案

1、第五章自顶向下语法分析方法1. 对文法GSS»A|(T)TTT,S|S(1) 给出(a,(a,a)和(a,a),A,(a),a)的最左推导。(2) 对文法G,进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。解：(1) (a,(a,a)的最左推导为ST弓(T,S)弓(S,S)弓(a,(T)弓(a,(T,S)弓(a,(S,a)弓(a,(a,a)(a,a),A,(a),a)的最左推导为ST(T)T(T,S)T(S,a)T(T),a)T(T,S),a)T(T,S,S

2、),a)T(S,A,(T),a)T(T),A,(S),a)T(T,S),A,(a),a)T(S,a),A,(a),a)T(a,a),A,(a),a)由于有TTT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/S:STa|A|(T)TTSUUT，SU|£分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1) 对于每个非终结号U,编写一个相应的子程序P(U)；(2) 对于规则U:=x1|x2|.|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IFCHINFIRST(x1)THENP(x1)ELSEIFCHINFIRST(x2)

3、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:=

4、EPSILON,则算法中的语句IFCHINFIRST(xn)THENP(xn)ELSEERROR改写为：IFCHINFIRST(xn)THENP(xn)ELSEIFCHINFOLLOW(U)THENRETURNERROR(5) 要分析一个OrgStr,应在该串的后面加上一个串括号并从子程序P(S)(S为文法的开始符号)开始,如果中途没有产生错误，并且最后CH='#',则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：charCH;/存放当前的输入符号voidP_S()非终结符S的子程序if(CH='a')READ(CH);/产

5、生式STaelseif(CH='A')READ(CH);/产生式STAelseif(CH='(')/产生式ST(T)READ(CH);P_T();IF(CH=')')THENREAD(CH)elseERRORelseERR;voidP_T()/非终结符S的子程序if(IsIn(CH,FIRST_SU)FIRST_SU为TTSU的右部的FIRST集合P_S();P_U();voidP_U()/非终结符U的子程序if(CH=',')/产生式UT,SUREAD(CH);P_S();P_U();else/产生式UTeif(IsIn(CH,

6、FOLLOW_U)/FOLLOW_U为U的FOLLOW集合return;elseERR;(3)判断文法G/S是否为LL(1)文法。各非终结符的FIRST集合如下：FIRST(S)=a,A,(FIRST(T)=FIRST(S)=a,A,(FIRST(U)=,£各非终结符的FOLLOW集合如下：FOLLOW(S)=#UFIRST(U)UFOLLOW(T)UFOLLOW(U)=#,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每个产生式的SELECT集合如下：SELECT(STa)二aSELECT(SA)=ASELECT(S(T)=(SELECT(TSU)=FIRST(

7、S)=a,A,(SELECT(UT,SU)=,SELECT(U£)=FOLLOW(U)=)可见，相同左部产生式的SELECT集的交集均为空，所以文法G/S是LL(1)文法。文法G/S的预测分析表如下：aA(),#STaTAT(T)TTSUTSUTSUUT8T,SU给出输入串（a,a）#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#ST(T)2#)T(a,a)#（匹配3#)Ta,a)#TTSU4#)USa,a)#STa5#)Uaa,a)#a匹配6#)U,a)#UT,SU7#)US,a)#，匹配8#)USa)#STa9#)Uaa)#a匹配10#)u)#UT811#)#）匹配1

8、2#接受2. 对下面的文法G：ETTE/E/E|eTTFT/T/TT|eFTPF/F/T*F/1ePT(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/)=+,eFIRST(T)=FIRST(F)=FIRST(P)=(,a,b,"FIRST(T/)=

9、FIRST(T)Ue=(,a,b,e;FIRST(F)=FIRST(P)=(,a,b,'FIRST(F/)=FIRST(P)=*,e;FIRST(P)=(,a,b,'FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;/不包含eFOLLOW(T/)=FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)UFOLLOW(T)=(,a,b,',+,),#;/不包含eFOLLOW(F/)=FOLLOW(F

10、)=FIRST(T/)UFOLLOW(T)=(,a,b,：+,),#;FOLLOW(P)=FIRST(F/)UFOLLOW(F)=*,(,a,b,：+,),#;/不包含e(2) 证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(ETTE/)=FIRST(T)=(,a,b,'SELECT(E/T+E)=+;SELECT(E/Te)=FOLLOW(E/)=),#SELECT(TTFT/)=FIRST(F)=(,a,b,'SELECT(T/TT)=FIRST(T)=(,a,b,'SELECT(T/Te)=FOLLOW(T/)=+,),#;SELECT(F

11、TPF/)=FIRST(P)=(,a,b,'SELECT(F/T*F/)=*;SELECT(F/Te)=FOLLOW(F/)=(,a,b,',+,),#;SELECT(PT(E)=(SELECT(PTa)=aSELECT(PTb)=bSELECT(PV)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(3) 构造它的预测分析表。文法GE的预测分析表如下：+*()ab#ETTE/TTE/TTE/TTE/E/T+ETeTeTTFT/TFT/TFT/TFT/T/TeTTTeTTTTTTTeFTPF/TPF/TPF/TPF/F/TeT*F/TeTeTe

12、TeTeTePT(E)TaTbT(4) 构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：charCH;/存放当前的输入符号voidP_E()/非终结符E的子程序if(IsIn(CH,FIRST_TEP)/FIRST_TEP为ETTE/的右部的FIRST集合，产生式ETTE/P_T();P_EP();elseERR;voidP_EP()/非终结符E/的子程序if(CH='+')/产生式E/T+EREAD(CH);P_E();else/产生式E/Teif(IsIn(CH,FOLLOW_EP)/F0LL0W_EP为E/的FOLLOW集合return;elseER

13、R;voidP_T()/非终结符T的子程序if(IsIn(CH,FIRST_FTP)/FIRST_FTP为TTFT/的右部的FIRST集合，产生式TTFT/P_F();P_TP();elseERR;voidP_TP()/非终结符T/的子程序if(IsIn(CH,FIRST_T)/FIRST为产生式T/TT的右部的FIRST集合，产生式T/TTP_T();else/产生式T/Teif(IsIn(CH,FOLLOW_TP)/FOLLOW_TP为T/的FOLLOW集合return;elseERR;voidP_F()/非终结符F的子程序if(IsIn(CH,FIRST_PFP)/FIRST_PFP为F

14、TPF/的右部的FIRST集合，产生式FTPF/P_P();P_FP();elseERR;voidP_FP()/非终结符F/的子程序if(CH='*')/产生式F/T*F/READ(CH);P_FP();else/产生式F/Teif(IsIn(CH,FOLLOW_FP)/FOLLOW_FP为F/的FOLLOW集合return;elseERR;voidP_P()/非终结符P的子程序if(CH='()READ(CH);P_E();if(CH=')')READCH(CH);elseERR;elseif(CH='a')READ(CH);elsei

15、f(CH='b')READ(CH);elseif(CH=''')READ(CH);elseERR;已知文法GS：STMH|aHLSo|eKdML|eLTeHfMTK|bLM解：判断G是否是LL(1)文法，如果是，构造LL(1)分析表。首先求各非终结符的FIRST集合：FIRST(S)=aUFIRST(M)UFIRST(H)=aUb,d,eUe,e=a,b,d,e,e;FIRST(H)=FIRST(L)Ue=e,e；FIRST(K)=d,e;FIRST(L)=e;FIRST(M)=FIRST(K)Ub=b,d,e;然后求非终结符的FOLLOW集合：FOLL

16、OW(S)=o,#FOLLOW(H)=FOLLOW(S)Uf=f,o,#FOLLOW(K)=FOLLOW(M)=FIRST(H)UFOLLOW(S)=e,o,#;/不包含eFOLLOW(L)=FIRST(S)UoUFOLLOW(K)UFIRST(M)UFOLLOW(M)=a,b,d,e,o,#UF0LL0W(M)=a,b,d,e,o,#;/不包含eFOLLOW(M)=FIRST(L)UFIRST(H)UFOLLOW(S)=e,o,#/不包含e最后求各产生式的SELECT集合：SELECT(STMH)=(FIRST(MH)-e)UFOLLOW(S)=b,d,eUo,#=b,d,e,o,#;SEL

17、ECT(STa)=aSELECT(HTLSo)=eSELECT(HTe)=FOLLOW(H)=f,o,#SELECT(KTdML)=dSELECT(KTe)=F0LL0W(K)=e,o,#SELECT(LTeHf)=eSELECT(MTK)=(FIRST(K)-e)UFOLLOW(M)=d,e,o,#SELECT(MTbLM)=b可见，相同左部产生式的SELECT集的交集均为空，所以文法GS是LL(1)文法。文法GE的预测分析表如下：aodefb#STaTMHTMHTMHTMHTMHH->eTLSo->e->eK->eTdML->e->eLMTKTKTeHf

18、TKTbLMtk7.对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面方法进行改写，并对改写后的文法进行判断。(1)AbaB|eBTAbb|aA->aABe|aBTBb|d解：对于一个文法若消除了左递归，提取了左公共因子后不一定为LL(1)文法。如果新的文法中无空产生式，则一定为LL文法，如果有空产生式，贝懦要进行LL判断才能决定新方法是否一定是LL文法。(1)由于SELECT(ATbaB)=b,SELECT(AT£)=FOLLOW(A)=b,#,两集合有交集，所以该文法不是LL(1)方法。该文法已经消除了左递归，与左公共因子，一般来说是不能再改写了。但根据本文法的具体情况有以下改写：BTbB/,B/TaBbb|b,这样改写后文法G/A为:ATbaB|eBTbB/|a用产生式ATbaB与ATe分别替换产生式BTAbb有：BTbaBbb|bb，提取这两个新产生式的左公共因子有:B/TaBbb|b每个产生式的SELECT集合为：SELECT(ATbaB)=bSELECT(ATe)=0SELECT(BTbB/)=bSELECT(BTa)=aSELECT(B/TaBbb)=aSELECT(B/Tb)=b可见，相