編譯原理第4章習題解答

1、第4章習題解答：1，2，3，4 解答 略！5. 解答：(1) (2) (3) (4) (5)(6)(7)(8)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) match (or);bterm();void bter

2、m();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. 解答：消除所給文法的左遞歸，得G：S (L)|a L S

3、LL ,SL |e 實現(xiàn)預測分析器的不含遞歸調用的一種有效方法是使用一張分析表和一個棧進行聯(lián)合控制，下面構造預測分析表：根據(jù)文法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(a,(a,a)#2#)L(a,(a,a)#S (L)3#)La,(a,a)#4#)LSa

4、,(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)#Le19#)L)#20#)#Le21# 9. 解答：各非終結符的First集：First(S)=First(A)eFirst(B)eeb=a,b, eFirst(A)=be=b,eFirst(B)ea=a,

5、eFirst(C)=First(A) eFirst(D)First(b) =a,b,cFirst(D)=ac=a,c各個候選式的First集為：First(AB)=a,b, e First(bC)=bFirst(e)e First(b)bFirst(aD)=a First(AD)=a,b,cFirst(b)=b First(aS)=aFirst(c)=c 各非終結符的Follow集的計算：Follow(S)=#Follow(D) =#Follow(A)=(First(B)e)Follow(S)First(D) =a,#,cFollow(B)=Follow(S) =#Follow(C)=Foll

6、ow(S) =#Follow(D)=Follow(B)Follow(C) =#10解答：(1) 求First和Follow集 First(E)=First(T)=(,a,b, First(E)=+, e First(T)=First(F)=(,a,b, First(T)=(,a,b, , e First(F)=First(P)=(,a,b, First(F)=*，e First(P)=(,a,b, （計算順序）Follow(E)= #, ) Follow(E)= Follow(E)=#，) (1)（使用的產(chǎn)生式）Follow(T) = First(E)eFollow(T) (1,2) = +)

7、,#=+,),#Follow(T)= Follow(T)=+,# (3)Follow(F)= First(T)eFollow(T) (3,4) = (,a,b,+ ,),#Follow(F)= Follow(F) (5) = (,a,b,+ ,),#Follow(P)= First(F)eFollow(F) (5,6) =*,(,a,b,+ ,),# (2) 證明: a. 文法不含左遞歸；b. 每個非終結符的各個侯選式的First集不相交；c. First(E)Follow(E)=+, e#,),=FFirst(T)Follow(T)=(,a,b, e+,)=FFirst(F)Follow(F

8、)=*, e,a,( ,+,#= F改造后的文法滿足LL(1)文法的三個條件，是LL(1)文法。(3) 預測分析表如下所示。ab*+()#EETEETEETEEE+EEeEeTTFTTFTTFTTFTTTTTTTTTTTeTeFFPFFPFFPFFPFFFeFeF*FFeFeFeFeFePPaPbPP(E)11. 解答：(1)SAbc AaeBbea. 文法不含左遞歸； b. S,A,B各候選式的First集不相交；c. First(A)Follow(A)=a,eb=F First(B)Follow(B)=b,eF=F該文法為LL(1)文法。(2) SAbAaBe Bbe a. 文法不含左遞歸

9、；b. S,A,B各候選式的First集不相交；c. First(A)Follow(A)=a,b, eb=b F 該文法不是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*F13. 解答：最左推導：S= (T) = (T,S) = (S,S) = (a,S) = (a,(T) = (a,(

10、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,)文法GS的算符優(yōu)先關系表： 根據(jù)優(yōu)先關系表，對每個終結符或#建立符號f與g，把f(和g)分成一組。根據(jù)GS的算符優(yōu)先關系表，畫出如下的有向圖。優(yōu)先函數(shù)如下：用算符優(yōu)先分

11、析法分析句子(a,(a,a)。給定的輸入符號串是文法的一個句子。14. 解答：(1) 該文法的拓廣文法G為 0S S1S aSAB2S BA3A aA4A B5B b其LR(0)項目集規(guī)范族和識別活前綴的DFA如下:I0 = SS, SaSAB, SBA, BbI1 = SSI2 = BbI3 = SaSAB, SaSAB, SBA, BbI4 = SBA, AaA, AB, BbI5 = SaSAB, AaA, AB, BbI6 = SaSAB, BbI7 = AaA, AaA, AB, BbI8 = ABI9 = SBAI10 = SaSABI11 = AaA顯然，上述狀態(tài)中沒有出現(xiàn)沖突。

12、顯然，該文法是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)項目集規(guī)范族和識別活前綴的DFA如下:I0 = SS, SSab, SbRI1 = SS, SSabI2 = SbR, RS, Ra, SSab, SbRI3 = SSabI4 = SbRI5 = RS, SSabI6 = RaI7 = SSab顯然，

13、I1和I5存在移進-歸約沖突。求S和R的Follow集： Follow(S)=# Follow(R)=Follow(S)=a,#在I5中，出現(xiàn)的移進歸約沖突，且Follow(R)a=a，不能用SLR(1)方法解決。因此，此文法不是SLR(1)文法。15. 解答：(1) 構造其拓廣文法G的產(chǎn)生式為 0S S1S A2A BA3A e4B aB5B b構造其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = SS, #, SA, #, ABA, #, A, #, BaB, a/b/#, Bb, a/b/# I1 = SS, #I2 = SA, #I3 = ABA, #, AB

14、A, #, A, #,BaB, a/b/#, Bb, a/b/#I4 = Bb, a/b/# I5 = BaB, a/b/#, BaB, a/b/#, Bb, a/b/#I6 = ABA, #I7 = BaB, a/b/#該文法的LR(1)項目集規(guī)范族中沒有沖突，所以該文法是LR(1)文法。構造LR(1)分析表如下：以上分析表無多的定義入口，所以該文法為LR(1)文法。(3)對于輸入串a(chǎn)bab，其分析過程如下： 16. 解答：(1) 對于產(chǎn)生式SAaAb|BbBa 來說First(AaAb)First(BbBa)=ab=FA，BVN僅有一條候選式。因此，這個文法是LL(1)的。(2) 下面構造這個文法的識別活前綴的DFA。I0 = SS, SAaAb, SBbBa, A, B I1 = SSI2 = SAaAbI3 = SBbBaI4 = SAaAb, AI5 = SBbBa, BI6 = SAaAbI7 = SBbBaI8 = SAaAbI9 = SBbBa由于Follow(A)=Follow(B)=a, b,因此項目集I0中存在歸約-歸約沖突。在I0狀態(tài)下，當輸入符號是a或是b時，不知用Ae還是Be進行歸約。故此文法不是SLR(1)的。但是，此文法時LR(1)的。17. 解答：該文法的拓廣文法G為 0S