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

编译原理习题解答 页7/7第五章 自顶向下语法分析方法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,(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)由于有TT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/S:Sa|(T)TSUU，SU|分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。(1) 对于每个非终结号U，编写一个相应的子程序P(U)；(2) 对于规则U:=x1|x2|.|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。(3) 对于符号串x=y1y2.yn;p(x)的含义为：BEGIN P(y1);P(y2);.P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。(4) 如果文法中有空规则U:=EPSILON,则算法中的语句IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR改写为：IF CH IN FIRST(xn) THEN P(xn)ELSE IF CH IN FOLLOW(U) THEN RETURN ERROR(5) 要分析一个OrgStr,应在该串的后面加上一个串括号#,并从子程序P(S)(S为文法的开始符号)开始，如果中途没有产生错误，并且最后CH=#,则说明OrgStr串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_S()/非终结符S的子程序if(CH=a) READ(CH);/产生式Saelse if(CH=) READ(CH);/产生式Selse if(CH=()/产生式S(T)READ(CH);P_T();IF (CH=) THEN READ(CH) else ERRORelse ERR;void P_T()/非终结符S的子程序if(IsIn(CH,FIRST_SU) /FIRST_SU为TSU的右部的FIRST集合P_S();P_U();void P_U()/非终结符U的子程序if(CH=,)/产生式U，SUREAD(CH);P_S();P_U();else/产生式Uif(IsIn(CH,FOLLOW_U) /FOLLOW_U为U的FOLLOW集合return ;else ERR;(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集合如下：SELECT(Sa)=aSELECT(S)=SELECT(S(T)=(SELECT(TSU)=FIRST(S)=a,（SELECT(U，SU)=，SELECT(U)=FOLLOW(U)=)可见，相同左部产生式的SELECT集的交集均为空，所以文法G/S是LL(1)文法。文法G/S的预测分析表如下：a()，#Sa(T)TSUSUSUU，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)( 匹配TSUSaa匹配U，SU,匹配Saa匹配U)匹配接受2对下面的文法G：ETE/E/+E|TFT/T/T|FPF/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(ETE/)=FIRST(T)=(,a,b,;SELECT(E/+E)=+;SELECT(E/)=FOLLOW(E/)=),#SELECT(TFT/)=FIRST(F)=(,a,b,;SELECT(T/T)=FIRST(T)=(,a,b,;SELECT(T/)=FOLLOW(T/)=+,),#;SELECT(FPF/)=FIRST(P)=(,a,b,;SELECT(F/*F/)=*;SELECT(F/)=FOLLOW(F/)=(,a,b,+,),#;SELECT(P(E)=(SELECT(Pa)=aSELECT(Pb)=bSELECT(P)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(3)构造它的预测分析表。文法GE的预测分析表如下：+*()ab#ETE/TE/TE/TE/E/+ETFT/FT/FT/FT/T/TTTTFPF/PF/PF/PF/F/*F/P(E)ab(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：char CH;/存放当前的输入符号void P_E()/非终结符E的子程序if(IsIn(CH,FIRST_TEP) /FIRST_TEP为ETE/ 的右部的FIRST集合，产生式ETE/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_ FTP为TFT/ 的右部的FIRST集合，产生式TFT/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为FPF/ 的右部的FIRST集合，产生式FPF/ 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;3已知文法GS：SMH|aHLSo|KdML|LeHfMK|bLM判断G是否是LL（1）文法，如果是，构造LL（1）分析表。解：首先求各非终结符的FIRST集合：FIRST(S)=aFIRST(M)FIRST(H)=ab,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)oFOLLOW(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(SMH)=(FIRST(MH)-)FOLLOW(S)=b,d,eo,#=b,d,e,o,#;SELECT(Sa)=aSELECT(HLSo)=eSELECT(H)=FOLLOW(H)=f,o,#SELECT(KdML)=dSELECT(K)=FOLLOW(K)=e,o,#SELECT(LeHf)=eSELECT(MK)=(FIRST(K)-)FOLLOW(M)=d,e,o,#SELECT(MbLM)=b可见，相同左部产生式的SELECT集的交集均为空，所以文法GS是LL(1)文法。文法GE的预测分析表如下：aodefb#SaMHMHMHMHMHHLSoKdMLLeHfMKKKbLMK7对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面方法进行改写，并对改写后的文法进行判断。(1)AbaB|BAbb|a(2)AaABe|aBBb|d解：对于一个文法若消除了左递归，提取了左公共因子后不一定为LL(1)文法。如果新的文法中无空产生式，则一定为LL(1)文法，如果有空产生式，则需要进行LL(1)判断才能决定新方法是否一定是LL(1)文法。(1)由于SELECT(AbaB)=b,SELECT(A)=FOLLOW(A)=b,#,两集合有交集,所以该文法不是LL(1)方法。该文法已经消除了左递归，与左公共因子，一般来说是不能再改写了。但根据本文法的具体情况有以下改写：用产生式AbaB 与A分别替换产生式BAbb有：BbaBbb|bb，提取这两个新产生式的左公共因子有：BbB/,B/aBbb|b,这样改写后文法G/A为：AbaB|BbB/|aB/aBbb|b每个产生式的SELECT集合为：SELECT(AbaB)=bSELECT(A)=SELECT(BbB/)=bSELECT(Ba)=aSELECT(B/aBbb)=aSELECT(B/b)=b可见，相同左部产生式的SELECT集的交集均为空，所以文法G/A是LL(1)文法。(2) 显然文法的第1，2个产生式的右部具有左公共因子a,而产生工BBb具有左递归，因此文法可改写为：AaA/A/ABe|BdB/B/bB/|由于SELECT(A/ABe)=a,SELECT(A/)=FOLLOW(A/)=FOLLOW(A)=FIRST(B)#=d,#,交集为空。而SELECT(B/bB/=b,SELECT(B/)=FOLLOW(B/)=FOLLOW(B)=e,交集也为空。而非终结符A与B都只有一个产生式，不存在求SELECT的交集问题。所以改写后的方法为LL(1)文法。