蔣立源編譯原理第三版第四章-習(xí)題與答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第五章 習(xí)題5-1 設(shè)有文法GS： SA/ AaAAS/(1) 找出部分符號序偶間的簡單優(yōu)先關(guān)系。(2) 驗證GS不是簡單優(yōu)先文法。 5-2 對于算符文法GS：SE EE-TT TT*FF F-PP P(E)i(1) 找出部分終結(jié)符號序偶間的算符優(yōu)先關(guān)系。(2) 驗證GS不是算符優(yōu)先文法。5-3 設(shè)有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相應(yīng)的簡單優(yōu)先矩陣如題圖5-3所示，試給出對符號串（i+i）進行簡單優(yōu)先分析的過程。題圖5-3

2、 文法GE的簡單優(yōu)先矩陣5-4 設(shè)有文法GE：EE+T|TTT*F|FF(E)|i其相應(yīng)的算符優(yōu)先矩陣如題圖5-4所示。試給出對符號串（i+i）進行算符優(yōu)先分析的過程。(i*+)#( eq oac(,) eq oac(,) eq oac(,) eq oac(,) eq oac(,)i eq oac(,) eq oac(,) eq oac(,) eq oac(,)* eq oac(,) eq oac(,) eq oac(,) eq oac(,) eq oac(,) eq oac(,)+ eq oac(,) eq oac(,) eq oac(,) eq oac(,) eq oac(,) eq oa

3、c(,) eq oac(,) eq oac(,) eq oac(,) eq oac(,)# eq oac(,) eq oac(,) eq oac(,) eq oac(,)題圖5-4 文法GE的算符優(yōu)先矩陣5-5 對于下列的文法，試分別構(gòu)造識別其全部可歸前綴的DFA和LR(0)分析表，并判斷哪些是LR(0)文法。(1) SaSbaScab(2) SaSSbaSSSc(3) SA AAba5-6 下列文法是否是SLR(1)文法？若是，構(gòu)造相應(yīng)的SLR(1)分析表，若不是，則闡明其理由。(1) SSabbR RSa(2) SaSABBA AaAB Bb(3) SaAbB AcAd BcBdd5-7

4、對如下的文法分別構(gòu)造LR(0)及SLR(1)分析表，并比較兩者的異同。 ScAdb AASca 5-8 對于文法GS:SA ABA BaBb (1) 構(gòu)造LR(1)分析表；(2) 給出用LR(1)分析表對輸入符號串a(chǎn)bab的分析過程。5-9 對于如下的文法，構(gòu)造LR(1)項目集族，并判斷它們是否為LR(1)文法。 (1) SA AAB BaBb (2) SaSaa第4章 習(xí)題答案2 5-1 解：(1) 由文法的產(chǎn)生式和如答案圖5-1(a)所示的句型Aa的語法樹，可得G中的部分優(yōu)先關(guān)系如答案圖5-1(b)所示。(2) 由答案圖5-1(b)可知，在符號A和/之間，即存在等于關(guān)系，又存在低于關(guān)系，故

5、文法GS不是簡單優(yōu)先文法。 5-2 解：(1) 由文法GS的產(chǎn)生式可直接看出：（ eq oac(,=) ）此外，再考察句型P(E)和i*(T*F)的語法樹 (見答案圖5-2(a)及(b)。由答案圖5-2(a)可得： eq oac(,) , eq oac(,) , eq oac(,) ( 由答案圖5-2(b)可得： i eq oac(,) * , * eq oac(,) ( , ( eq oac(,) * , * eq oac(,) ） (2) 由答案圖5-2(a)可知，在終結(jié)符號和之間，存在兩種算符優(yōu)先關(guān)系： eq oac(,) , eq oac(,) 故文法GS不是算符優(yōu)先文法。5-3 解：

6、對符號串(i+i)進行簡單優(yōu)先分析的過程如答案表5-3所示。因為分析成功，所以符號串(i+i)是文法GE的合法句子。答案表5-3 符號串(i+i)的簡單優(yōu)先分析過程步驟分析棧關(guān)系當前符號余留輸入串句柄所用產(chǎn)生式0#低于（i+i)# 1#(低于i+i)# 2#(i優(yōu)于+i)# iFi3#(F優(yōu)于+i)# FTF4#(T優(yōu)于+i)# TT1T5#(T1優(yōu)于+i)# T1E1T16#(E1等于+i)# 7#(E1+低于i)# 8#(E1+i優(yōu)于)# iFi9#(E1+F優(yōu)于)# FTF10#(E1+T優(yōu)于)# TT1T 11#(E1+T1優(yōu)于)# E1+T1E1E1+T1 12#(E1優(yōu)于)# E1

7、EE1 13#(E等于)# 14#(E)優(yōu)于#(E)F(E) 15#F優(yōu)于#FTF16#T優(yōu)于#TT1T17#T1優(yōu)于#T1E1T1 18#E1優(yōu)于#E1EE1 19#E優(yōu)于#分析成功5-4 解：對符號串(i+i)進行算符優(yōu)先分析的過程如答案表5-4所示。 因為分析成功，所以符號串(i+i)是文法GE的合法句子。句子(i+i)及其分析過程中所得句型的語法樹如答案圖5-4所示。答案表5-4 符號串（i+i)的算符優(yōu)先分析過程步驟分析棧當前棧頂終結(jié)符號優(yōu)先關(guān)系當前輸入符號余留輸入串最左素短語0# eq oac(,)（i+i)# 1# eq oac(,)(（ eq oac(,)i+i)# 2# eq

8、 oac(,)( eq oac(,)ii eq oac(,)+i)# i3# eq oac(,)(F( eq oac(,)+i)# 4# eq oac(,)( eq oac(,)F+ eq oac(,)i)# 5# eq oac(,)( eq oac(,)F+ eq oac(,)ii eq oac(,)# i6# eq oac(,)( eq oac(,)F+F+ eq oac(,)# F+F7# eq oac(,)(E( eq oac(,)# 8# eq oac(,)( eq oac(,)E) eq oac(,)#(E) 9#F#分析成功 5-5 解：(1) 在文法GS中引入一個新的開始符號S

9、，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S aScaSb ab識別文法GS全部可歸前綴的DFA如答案圖5-5-(1)所示。因為文法GS的每個LR(0)項目集中都不含沖突項目，所以文法GS是LR(0)文法，故可構(gòu)造出不含沖突動作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOabc#S0123456s2 s2 r3 r1r2 s4s5r3r1 r2s6r3r1r2accr3r1r213(2) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S a

10、SSSaSSb c識別文法GS全部可歸前綴的DFA如答案圖5-5-(2)所示。因為文法GS的每個LR(0)項目集中都不含沖突項目，所以文法GS是LR(0)文法，故可構(gòu)造出不含沖突動作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOabc#S01234567s2 s2 r3s2 s2r1r2 r3r1 r2s3s3 r3s3s3r1r2accr3r1r21457(3) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S AbA a識別文法GS全部可歸前綴的DFA如答案圖5-

11、5-(3)所示。因為在LR(0)項目集I2中含有移進-歸約沖突項目，所以文法GS不是LR(0)文法，故構(gòu)造出的LR(0)分析表中含有沖突動作。文法GS的LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOab#SA01234s3 r1 r3r2 s4 ,r1r3r2accr1 r3r212 5-6 解：(1) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S SSab a2. SbR識別文法GS全部可歸前綴的DFA如答案圖5-6-(1)所示。由答案圖5-6-(1)可知，在項目

12、集I1 和I4中都存在“移進-歸約”沖突。在項目集I4 = RS, SSab 中, 由于FOLLOR(R)=a，F(xiàn)OLLOR(R)a=a?，所以其項目集的“移進-歸約”沖突不可能通過SLR(1)規(guī)則得到解決，從而該文法不是SLR(1)文法。(2) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S aAaSAB BBA b識別文法GS全部可歸前綴的DFA如答案圖5-6-(2)所示。答案圖5-6-(2) 識別GS全部可歸前綴的DFA因為文法GS的每個LR(0)項目集中都不含沖突項目，所以文法GS是LR(0)文法，故也是SLR(1)文法。因為F

13、OLLOW(S)=a,b,#, FOLLOW(A)=a,b,#, FOLLOW(B)=a,b,#, 所以文法GS的SLR(1)分析表如答案表5-6-(2)所示。答案表5-6-(2) 文法GS的SLR(1)分析表狀態(tài)ACTIONGOTOab#SAB01234567891011s2 s2 s7r5 s7r2s7r4r1r3s4s4 s4 r5s4r2s4r4s4r1r3accr5r2r4r1r31569113388810(3) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S aA cBddbB 3. AcAd識別文法GS全部可歸前綴的DFA

14、如答案圖5-6-(3)所示。由答案圖5-6-(3)可知，在項目集I2 ,I3 ,I5 和I9中都存在“移進-歸約”沖突。因為在項目集I2 和I5中, 由于FOLLOR(A)=d,#，F(xiàn)OLLOR(A)c=?，所以其項目集的“移進-歸約”沖突能通過SLR(1)規(guī)則得到解決；又因為在項目集I3 和I9中, 由于FOLLOR(B)=d,#，F(xiàn)OLLOR(B)c=?，所以其項目集的“移進-歸約”沖突也能通過SLR(1)規(guī)則得到解決；所以文法GS是SLR(1)文法。因為FOLLOR(S)=#，F(xiàn)OLLOR(A)=d,#，F(xiàn)OLLOR(B)=d,#，所以文法GS的SLR(1)分析表如答案表5-6-(3)所

15、示。答案表5-6-(3) 文法GS的SLR(1)分析表狀態(tài)ACTIONGOTOabcd#SAB0123456789101112s2 s3s5s9s5s9r4r6r4s7r3r6s11s12r5accr4r6r1 r4r3r2r6r5146810 5-7 解：在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S ASccAd ab 識別文法GS全部可歸前綴的DFA如答案圖5-7所示。因為文法GS的每個LR(0)項目集中都不含沖突項目，所以文法GS是LR(0)文法。文法GS的LR(0)分析表如答案表5-7-(a)所示。答案表5-7-(a) 文法G

16、S的LR(0)分析表狀態(tài)ACTIONGOTOabcd#SA012345678 s4 r2r4r1r3s3r2r4s3r1r3s2r2r4s2r1s8r3r2r4s6r1r3accr2 r4 r1 r3 175因為FOLLOR(S)=#,c，F(xiàn)OLLOR(A)=b,c,d，所以文法GS的SLR(1)分析表如答案表5-7-(b)所示。答案表5-7-(b) 文法GS的SLR(1)分析表狀態(tài)ACTIONGOTOabcd#SA012345678 s4 s3r4s3r3s2r2r4s2r1s8r3r4s6r3accr2 r1 175兩個表的相同之處為：(1) 兩個表的GOTO表部分完全相同。(2) 在兩個

17、表的ACTION表中，不含歸約項目的項目集對應(yīng)的行的元素完全相同，即第0,2,5,7行完全相同。兩個表的不同之處為：在兩個表的ACTION表中，含有歸約項目的項目集對應(yīng)的行的元素不同，即第3,4,6,8行的元素不同。以第3行為例，答案表5-7-(a)中的所有元素都為r2 ；而在答案表5-7-(b)中 , 因為FOLLOR(S)=#,c，故僅在“#”和“c”列對應(yīng)的元素為r2 。5-8 解：(1) 在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS：S A aBBA b文法GS的LR(1)項目集及DFA如答案圖5-8所示。文法GS的LR(1)分析

18、表如答案表5-8-(1)所示。答案表5-8-(1) 文法GS的LR(1)分析表狀態(tài)ACTIONGOTOab#SAB01234567s4 s4s4r5r4s5s5s5r5r4r3accr1r3r5r2r4126337(2) 用LR(1)分析表對輸入符號串a(chǎn)bab的分析過程如答案表5-8-(2)所示。因為分析成功，所以符號串a(chǎn)bab是文法GS的合法句子。答案表5-8-(2) 符號串a(chǎn)bab的LR分析過程步驟狀態(tài)棧符號棧余留輸入串分析動作下一狀態(tài)1I0#abab#s442I0I4#a bab#s553I0I4I5 #ab ab#r5GOTOI4 ,B=74 I0I4I7 #aB ab#r4GOTOI0 ,B=35 I0I3 #B ab#s446I0I3I4 #Ba b#s557I0I3I4I5 #Bab #r5GOTOI4 ,B=78 I0I3I4I7 #BaB #r4GOTOI3 ,B=39 I0I3I3 #BB #r