《编译原理第4章习题解答》由会员分享，可在线阅读，更多相关《编译原理第4章习题解答（11页珍藏版）》请在金锄头文库上搜索。
1、第 4 章习题解答：1，2，3，4 解答解答 略！略！ 5.5. 解答：解答：(1) (2) (3) (4) (5) (6)(7)(8) 6.6. 解答：解答： (1)A： B： C： D： E： (2)A： B： C： D： E： 7.解答：解答： (1) 消除给定文法中的左递归，并提取公因子： bexprbterm or bterm btermbfactor and bfactor bfactornot bfactor | (bexpr) | true |false (2) 用类 C 语言写出其递归分析程序: void bexpr();bterm();WHILE(lookahead =or
2、) match (or);bterm();void bterm();bfactor();WHILE(lookahead =and)match (and);bfactor();void bfactor();if (llokahead=not) then match (not);bfactor();else if(lookahead=() then match ();bexpr();match();else if(lookahead =true) then match (true)else if (lookahead=false)then match (false);else error; 8.8
3、. 解答：解答： 消除所给文法的左递归，得 G：S (L)|a L SLL ,SL | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合 控制，下面构造预测分析表： 根据文法 G有：First(S) = ( , a )Follow(S) = ) , , , # First(L) = ( , a )Follow(L) = ) First(L) = ,Follow(L) = ) 按以上结果，构造预测分析表 M 如下：文法 G是 LL(1)的，因为它的 LL(1)分析表不含多重定义入口。 预测分析器对输入符号串(a,(a,a)做出的分析动作如下：步骤栈剩余输入串输出1#S(
4、a,(a,a)#2#)L(a,(a,a)#S (L)3#)La,(a,a)#4#)LSa,(a,a)#L SL5#)Laa,(a,a)#S a6#)L,(a,a)#7#)LS,(a,a)#L ,SL8#)LS(a,a)#9#)L)L(a,a)#S (L)10#)L)La,a)#11#)L)LSa,a)#L SL12#)L)Laa,a)#S a13#)L)L,a)#14#)L)LS,a)#L ,SL15#)L)LSa)#16#)L)Laa)#S a17#)L)L)#18#)L)#L19#)L)#20#)#L21#9. 解答：解答： 各非终结符的 First 集：First(S)=First(A)
5、First(B)b=a,b, First(A)=b=b, First(B)a=a,First(C)=First(A) First(D)First(b) =a,b,c First(D)=ac=a,c 各个候选式的 First 集为：First(AB)=a,b, First(bC)=b First() First(b)b First(aD)=a First(AD)=a,b,c First(b)=b First(aS)=a First(c)=c 各非终结符的 Follow 集的计算：Follow(S)=#Follow(D) =# Follow(A)=(First(B)Follow(S)First(D
6、) =a,#,c Follow(B)=Follow(S) =# Follow(C)=Follow(S) =#Follow(D)=Follow(B)Follow(C) =# 10解答：解答： (1) 求 First 和 Follow 集 First(E)=First(T)=(,a,b, First(E)=+, First(T)=First(F)=(,a,b, First(T)=(,a,b, , First(F)=First(P)=(,a,b, First(F)=*， First(P)=(,a,b, （计算顺序）Follow(E)= #, ) Follow(E)= Follow(E)=#，) (1
7、)（使用的产生式） Follow(T) = First(E)Follow(T) (1,2)= +),#=+,),# Follow(T)= Follow(T)=+,# (3) Follow(F)= First(T)Follow(T) (3,4)= (,a,b,+ ,),# Follow(F)= Follow(F) (5)= (,a,b,+ ,),# Follow(P)= First(F)Follow(F) (5,6)=*,(,a,b,+ ,),# (2) 证明: a. 文法不含左递归； b. 每个非终结符的各个侯选式的 First 集不相交；c. First(E)Follow(E)=+, #,)
8、,= First(T)Follow(T)=(,a,b, +,)= First(F)Follow(F)=*, ,a,( ,+,#= 改造后的文法满足 LL(1)文法的三个条件，是 LL(1)文法。 (3) 预测分析表如下所示。ab*+()#EETEETEETEEE+EE ETTFTTFTTFTTFTTTTTTTTTTT TFFPFFPFFPFFPFFFFF*FFFFFFPPaPbPP(E)11. 解答：解答： (1)a. 文法不含左递归； b. S,A,B 各候选式的 First 集不相交；c. First(A)Follow(A)=a,b=First(B)Follow(B)=b,= 该文法为 L
9、L(1)文法。 (2) a. 文法不含左递归； b. S,A,B 各候选式的 First 集不相交；c. First(A)Follow(A)=a,b, b=b 该文法不是 LL(1)文法。 12. 解答：解答： 最右推导： E=T=F=(E)=(ET)=(EF)=(Ei)= (Ti)=(T*Fi) 语法树：图 4.1 句型(T*Fi)的语法树 短语：(T*Fi)，T*Fi，T*F，i 素短语：T*F，i 最左素短语：T*F 由于 E =E+T =E+T*F，故 E+T*F 为该文法的句型 短语：T*F、E+T*F 直接短语： T*F 句柄： T*F 13.13. 解答解答： 最左推导：S= (
10、T) = (T,S) = (S,S) = (a,S) = (a,(T) = (a,(T,S) = (a,(S,S) = (a,(a,S) = (a,(a,a) 最右推导：S= (T) = (T,S) = (T,(T) = (T,(T,S) = (T,(T,a) = (T,(T,a) = (T,(a,a) = (S,(a,a) = (a,(a,a) 文法中 S 和 T 的 FirstVT 和 LastVT 集为：FirstVT(S)=a,( FirstVT(T)=,a, ( lastVT(S)=a, ） lastVT(T)=,a,)SAbc Aa BbSAbAaB Bb 文法 GS的算符优先关系
11、表： 根据优先关系表，对每个终结符或#建立符号 f 与 g，把 f(和 g)分成一组。根据 GS的 算符优先关系表，画出如下的有向图。优先函数如下：用算符优先分析法分析句子(a,(a,a)。给定的输入符号串是文法的一个句子。 14.14. 解答：解答： (1) 该文法的拓广文法 G为 0S S 1S aSAB 2S BA 3A aA 4A B 5B b 其 LR(0)项目集规范族和识别活前缀的 DFA 如下: I0 = SS, SaSAB, SBA, Bb I1 = SS I2 = Bb I3 = SaSAB, SaSAB, SBA, Bb I4 = SBA, AaA, AB, Bb I5 =
12、 SaSAB, AaA, AB, Bb I6 = SaSAB, Bb I7 = AaA, AaA, AB, Bb I8 = AB I9 = SBA I10 = SaSAB I11 = AaA显然，上述状态中没有出现冲突。显然，该文法是 LR(0)的文法，因此也是 SLR(1)的。求各个非终结符的 Follow 集，以便构造分析表：Follow(S)=# Follow(S)=a,b,#Follow(A)=a,b,# Follow(B)=a,b,# 构造的 SLR(1)分析表如下：(2) 该文法的拓广文法 G为 0S S 1S Sab 2S bR 3R S 4R a 其 LR(0)项目集规范族和识别活前缀的 DFA 如下: I0 = SS, SSab, SbR I1 = SS, SSab I2 = SbR, RS, Ra, SSab, SbR I3 = SSab I4 = SbR I5 = RS, SSab I6 = Ra I7 = SSab显然，I1和 I5存在移进-归约冲突。求 S和 R 的 Follow 集：Follow(S)=#Follow(R)=Follow(S)=a,# 在 I5中，出现的移进归约冲突，且 Follow(R)a=a，不能用
