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

1、编译原理习题解答页 1/1第五章 自顶向下语法分析方法1 对文法 GSS a|A|(T)T T,S|S(1)给岀(a,(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),a)的最左推导为S (T)(T,S)(S,a)(T),a)(T,S),a)

2、(T,S,S),a)(S,A,(T),a)(T),A,(S),a)(T,S),A,(a),a)(S,a),A,(a),a)(a,a),A,(a),a)由于有 T T,S 的产生式，所以消除该产生式的左递归，增中一个非终结符U 有新的文法 GS:S a|A|(T)T SUU ，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

3、 FIRST(x2) THEN P(x2)ELSE .IF CH IN FIRST(x n) THEN P(x n)ELSE ERROR其中，CH 存放当前的输入符号，是一个全程变量；ERROR1 一段处理岀错信息的程序;P(xj)为相应的子程序。对于符号串 x=y1y2.y n;p(x)的含义为：BEGINP(y1);P(y2);P(y n);END如果 yi 是非终结符，则 P(yi)代表调用处理 yi 的子程序；如果 yi 是终结符，则 P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下

4、一个待输入符号到CH 中,否则表明出错。如果文法中有空规则U:=EPSILON,则算法中的语句IF CH IN FIRST(x n) THEN P(x n)编译原理习题解答页 1/2ELSE ERROR改写为：IF CH IN FIRST(x n) THEN P(x n)ELSE IF CH IN FOLLOW(U) THEN RETURNERROR(5)要分析一个 OrgStr,应在该串的后面加上一个串括号#,并从子程序 P(S)(S 为文法的开始符号如果中途没有产生错误，并且最后CH=#,则说明 OrgStr 串合法，否则该串不合法。对每个非终结符写出不带回溯的递归子程序如下：char C

5、H;/存放当前的输入符号void P_S()非终结符 S 的子程序if(CH= aREAD(CH);/ 产生式 S aelse if(CH= A ) READ(C 产生式 SAelse 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为 T SU 的右部的 FIRST 集合P_S()；P_U()；void P_U()/非终结符 U 的子程序if(CH=,产生式 U ，SUREAD(CH);P_

6、S()；P_U()；else/产生式 U if(IsIn(CH,FOLLOW_U) /FOLLOW_U为 U 的 FOLLOW 集合return ;else ERR;判断文法 GS是否为 LL(1)文法。各非终结符的 FIRST 集合如下：FIRST(S)=a,人,(FIRST(T)=FIRST(S)=a,人,(FIRST(U)= , , 各非终结符的 FOLLOW!合如下：） 开始,编译原理习题解答页 1/3FOLLOW(S)=#UFIRST(U)UFOLLOW(T)UFOLLOW(U)=#,)FOLLOW(T)=)FOLLOW(U)=FOLLOW(T)=)每个产生式的 SELECT 集合如

7、下：SELECT(S a)=aSELECT(SA)=ASELECT(S (T)=(SELECT(T SU)=FIRST(S)=a,A,(SELECT(U , SU)=, SELECT(UE)=FOLLOW(U)=)可见，相同左部产生式的SELECT 集的交集均为空，所以文法GS是 LL(1)文法文法 GS的预测分析表如下：aA()#SaA(T)TSUSUSUUE,SU(5)给岀输入串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#S (T)2#)T(a,a)#(匹配3#)Ta,a)#T SU4#)USa,a)#S a5#)Uaa,a)#a 匹配6#)U,a)#U , SU

8、7#)US,a)#,匹配8#)USa)#S a9#)Uaa)#a 匹配10#)U)#UE11#)#)匹配12#接受2.对下面的文法 G:E TEE +E|ET FTT/T|EF PFF/*F/|EP (E)|a|bF(1)计算这个文法的每个非终结符的FIRST 集和 FOLLOW!。证明这个方法是LL(1)的。(3)构造它的预测分析表。(4)构造它的递归下降分析程序。解：(1)计算这个文法的每个非终结符的FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,br;编译原理习题解答页 1/4FIRST(E/)=+,

9、EFIRST(T)=FIRST(F)=FIRST(P)=(,a,br;FIRST(T/)=FIRST(T)UE=(,a,b=E；FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,A;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(/E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)UFOLLOW(E)=+,),#;不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E/)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,

10、+,),#;不包含 FOLLOW(F=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F)UFOLLOW(F)=*,(,a,b,A,+,),#;不包含 证明这个方法是 LL(1)的。各产生式的 SELECT 集合有：SELECT(E TE)=FIRST(T)=(,a,br;SELECT(E +E)=+;SELECT(E )=FOLLOW(E)=),#SELECT(T F)=FIRST(F)=(,a,b,A;SELECT(T T)=FIRST(T)=(,a,br;SELECT(T )=FOLLOW(T)=+,),#；SELEC

11、T(F PF)=FIRST(P)=(,a,br;SELECT(F *F/)=*；SELECT(F )=FOLLOW(F)=(,a,b,A,+,),#;SELECT(P (E)=(SELECT(P a)=aSELECT(P b)=bSELECT(PA)=A可见，相同左部产生式的SELECT 集的交集均为空，所以文法GE是 LL(1)文法(3)构造它的预测分析表。 文法 GE的预测分析表如下:+*()abA#ETETEPTETE/匚+ETFTFTFTFT/TTTTTFPFPFPFPF/F/*F/P(E)abA(4)构造它的递归下降分析程序。对每个非终结符写出不带回溯的递归子程序如下：char CH

12、;/存放当前的输入符号void P_E()/非终结符 E 的子程序if(IsIn(CH,FIRST_TEP) FIRST_TEP为 E TE 的右部的 FIRST 集合，产生式 E TE编译原理习题解答页 1/5P_T()；P_EP()；编译原理习题解答页 1/6else ERR;void P_EP()非终结符 U 的子程序if( CH= +) / 产生式 U +EREAD(CH);P_E()；else/ 产生式 E/&if(IsIn(CH,FOLLOW_EP) FOLLOW_EP为 E 的 FOLLO 喋合return ;else ERR;void P_T()/ 非终结符 T 的子程

13、序if(lsln(CH,FIRST_FTP) FIRST_ FTP为 T F的右部的 FIRST 集合，产生式 T FTP_F();P_TP();else ERR;void P_TP()/非终结符 F 的子程序编译原理习题解答页 1/7void P_P()非终结符 P 的子程序if(CH=( )READ(CH);P_E()；if(CH= ) ) READCH(C H);elseERR;else if(CH= a ) READ(CH);else if(CH= b ) READ(CH);else if(CH= A ) READ(CH);else ERR;3 已知文法 GS:S MH|aH LSo|

14、 K dML|L eHfM K|bLM判断 G 是否是 LL (1)文法，如果是，构造 LL (1)分析表。解：首先求各非终结符的 FIRST 集合：if(IsI n(CH,FIRST_T) FIRST_T为产生式P_T();else/ 产生式 T/if(Is In (CH,FOLLOW_TP) FOLLOW_TPreturn ;else ERR;void P_F()/非终结符 F 的子程序if(IsIn(CH,FIRST_PFP) /FIRST_PFP 为 F P_P();P_FP();else ERR;void P_FP()/非终结符 F/的子程序if( CH= *) / 产生式 F/*F

15、/READ(CH); P_FP();else/ 产生式 F/if(Is In (CH,FOLLOW_FP) FOLLOW_FPreturn ;else ERR;T T 的右部的 FIRST 集合，产生式 T T为 T 的 FOLLO 喋合PF的右部的FIRST集合，产生式F PF为 U 的 FOLLO 喋合编译原理习题解答页 1/8FIRST(S)=aUFIRST(M)UFIRST(H)=aUb,d,Ue,=a,b,d,e,;FIRST(H)=FIRST(L)U=e,;FIRST(K)=d, ；FIRST(L)=e;FIRST(M)=FIRST(K)Ub=b,d,;然后求非终结符的 FOLLO

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

17、d,e,o,#;SELECT(S a)=aSELECT(H LSo)=eSELECT(H )=FOLLOW(H)=f,o,#SELECT(K dML)=dSELECT(K )=FOLLOW(K)=e,o,#SELECT(L eHf)=eSELECTM K)=(FIRST(K)-)UFOLLOW(M)=d,e,o,#SELECT(M bLM)=b可见，相同左部产生式的SELECT 集的交集均为空，所以文法GS是 LL(1)文法文法 GE的预测分析表如下：aodefb#SaMHMHMHMHMHHLSoKdMLLeHfMKKKbLMK7.对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(

18、1)文法？试对下面方法进行改写，并对改写后的文法进行判断。(1) AbaB| B Abb|aAaABe|aB Bb|d解：对于一个文法若消除了左递归，提取了左公共因子后不一定为LL(1)文法。如果新的文法中无空产生式，则一定为 LL(1)文法，如果有空产生式，则需要进行LL(1)判断才能决定新方法是否一定是LL(1)文法。(1)由于 SELECT(A baB)=b,SELECT(A)=FOLLOW(A)=b,#,两集合有交集,所以该文法不是 LL(1)方法。 该文法已经消除了左递归，与左公共因子，一般来说是不能再改写了。但根据本文法的具体情况有以下改写： 用产生式 A baB 与 A 分别替换产生式B Abb 有：B baBbb|bb，提取这两个新产生式的左公共因子有：BbBB aBbb|b,这样改写后文法 GA为：A baB| &B bB/|aB/aBbb|b每个产生式的 SELECT 集合为：SELECT(A baB)=bSELECT(A )=SELECT(B bB/)=bSELECT(B a)=aSELECT(B aBbb)=aSELECT(B b)=b可见，相同左部产生式的SELECT 集的交集