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

1、蔣立源編譯原理第三版第四章習(xí)題及答案蔣立源編譯原理第三版第四章習(xí)題及答案15/15蔣立源編譯原理第三版第四章習(xí)題及答案第五章習(xí)題5-1設(shè)有文法GS：SA/AaAAS/找出部分符號序偶間的簡單優(yōu)先關(guān)系。考證GS不是簡單優(yōu)先文法。5-2關(guān)于算符文法GS：SEEE-TTTT*FFF-PPP(E)i找出部分終結(jié)符號序偶間的算符優(yōu)先關(guān)系?？甲CGS不是算符優(yōu)先文法。5-3設(shè)有文法GE：EEEE+T|T1TTTT*F|FF(E)|i11111其相應(yīng)的簡單優(yōu)先矩陣如題圖5-3所示，試給出對符號串（i+i）進(jìn)行簡單優(yōu)先剖析的過程。題圖5-3文法GE的簡單優(yōu)先矩陣5-4設(shè)有文法GE：EE+T|TTT*F|FF(E

2、)|i其相應(yīng)的算符優(yōu)先矩陣如題圖5-4所示。試給出對符號串（i+i）進(jìn)行算符優(yōu)先剖析的過程。(i*+)#(i*+)#題圖5-4文法GE的算符優(yōu)先矩陣5-5關(guān)于以下的文法，試分別結(jié)構(gòu)辨別其所有可歸前綴的DFA和LR(0)剖析表，并判斷哪些是LR(0)文法。SaSbaScabSaSSbaSSScSAAAba5-6以下文法是不是SLR(1)文法？假如，結(jié)構(gòu)相應(yīng)的SLR(1)剖析表，若不是，則說明其原因。(1)SSabbRRSa(2)SaSABBAAaABBb(3)SaAbBAcAdBcBdd5-7對以下的文法分別結(jié)構(gòu)LR(0)及SLR(1)剖析表，并比較二者的異同。ScAdbAASca5-8關(guān)于文法

3、GS:SAABABaBb結(jié)構(gòu)LR(1)剖析表；(2)給出用LR(1)剖析表對輸入符號串a(chǎn)bab的剖析過程。5-9關(guān)于以下的文法，結(jié)構(gòu)LR(1)項目集族，并判斷它們能否為LR(1)文法。(1)SAAABBaBb(2)SaSaa第4章習(xí)題答案25-1解：(1)由文法的產(chǎn)生式和如答案圖5-1(a)所示的句型Aa的語法樹，可得G中的部分優(yōu)先關(guān)系如答案圖5-1(b)所示。由答案圖5-1(b)可知，在符號A和/之間，即存在等于關(guān)系，又存在低于關(guān)系，故文法GS不是簡單優(yōu)先文法。5-2解：由文法GS的產(chǎn)生式可直接看出：=）別的，再觀察句型P(E)和i*(T*F)的語法樹(見答案圖5-2(a)及(b)。由答案圖

4、5-2(a)可得：,(由答案圖5-2(b)可得：i*,*(,(*,*）由答案圖5-2(a)可知，在終結(jié)符號和之間，存在兩種算符優(yōu)先關(guān)系：,故文法GS不是算符優(yōu)先文法。5-3解：對符號串(i+i)進(jìn)行簡單優(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)于

5、)#iFi9#(E1+F優(yōu)于)#FTF10#(E1+T優(yōu)于)#TT1T11#(E1+T優(yōu)于)#E+TEE+T11111112#(E1優(yōu)于)#E1EE113#(E等于)#14#(E)優(yōu)于#(E)F(E)15#F優(yōu)于#FTF16#T優(yōu)于#TT1T17#T1優(yōu)于#T1E1T118#E優(yōu)于#EEE11119#E#剖析優(yōu)于成功5-4解：對符號串(i+i)因為剖析成功，因此符號串進(jìn)行算符優(yōu)先剖析的過程如答案表(i+i)是文法GE的合法句子。5-4所示。句子(i+i)及其剖析過程中所得句型的語法樹如答案圖5-4所示。答案表5-4符號串（i+i)的算符優(yōu)先剖析過程目前棧頂步驟剖析棧終結(jié)符號0#1（#(2i#(

6、i3(#(F4+#(F+5#(F+ii6+#(F+F7#(E(8)#(E)優(yōu)先目前輸余留最左關(guān)系入符號輸入串素短語（i+i)#i+i)#+i)#i+i)#i)#)#i)#F+F)#(E)剖析9#F#成功5-5解：(1)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得G的拓廣文法GS：SaScaSbab辨別文法GS所有可歸前綴的DFA如答案圖5-5-(1)所示。因為文法GS的每個LR(0)項目集中都不含矛盾項目，因此文法GS是LR(0)文法，故可結(jié)構(gòu)出不含矛盾動作的LR(0)剖析表如答案表5-5-(1)所示。答案表5-5-(1)文法GS的LR(0)剖析表ACT

7、IONGOTO狀態(tài)abc#S0s211acc2s2s433s5s64r3r3r3r35r1r1r1r16r2r2r2r2(2)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得G的拓廣文法GS：SaSSSaSSbc辨別文法GS所有可歸前綴的DFA如答案圖5-5-(2)所示。因為文法GS的每個LR(0)項目集中都不含矛盾項目，因此文法GS是LR(0)文法，故可結(jié)構(gòu)出不含矛盾動作的LR(0)剖析表如答案表5-5-(2)所示。答案表5-5-(2)文法GS的LR(0)剖析表狀態(tài)ACTIONGOTOabc#S0s2s311acc2s2s343r3r3r3r34s2s35

8、5s2s376r1r1r1r17r2r2r2r2(3)在文法GS中引入一個新的開始符號S，且將加到文法G中，進(jìn)而獲得G的拓廣文法GS：SAbAa辨別文法GS所有可歸前綴的DFA如答案圖5-5-(3)SS作為第所示。0個產(chǎn)生式添因為在LR(0)項目集I2中含有移進(jìn)-歸約矛盾項目，因此文法GS不是LR(0)文法，故結(jié)構(gòu)出的LR(0)剖析表中含有矛盾動作。文法GS的LR(0)剖析表如答案表5-5-(3)所示。答案表5-5-(3)文法GS的LR(0)剖析表狀態(tài)ACTIONGOTOab#SA0s3121acc2r1s4,r1r13r3r3r34r2r2r25-6解：(1)在文法GS中引入一個新的開始符號

9、S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得SSabG的拓廣文法GS：Sa2.SbR辨別文法GS所有可歸前綴的DFA如答案圖5-6-(1)所示。由答案圖5-6-(1)可知，在項目集I1和I4中都存在“移進(jìn)-歸約”矛盾。在項目集I4=RS,SSab中,因為FOLLOR(R)=a，F(xiàn)OLLOR(R)a=a?，因此其項目集的“移進(jìn)-歸約”矛盾不行能經(jīng)過SLR(1)規(guī)則獲得解決，進(jìn)而該文法不是SLR(1)文法。(2)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得G的拓廣文法GS：辨別文法SaSABBAGS所有可歸前綴的aABbDFA如答案圖5-6-(2)所

10、示。答案圖5-6-(2)辨別GS所有可歸前綴的DFA因為文法GS的每個LR(0)項目集中都不含矛盾項目，因此文法GS是LR(0)文法，故也是SLR(1)文法。因為FOLLOW(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#SAB0s2s4131acc2s2s4533s7s4684r5r5r55s7s4986r2r2r27s7s41188r4r4r49s41010r1r1r111r3r3r3(3)在文法GS中引入一個新的開始

11、符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得G的拓廣文法GS：SaAcBddbB3.AcAd辨別文法GS所有可歸前綴的DFA如答案圖5-6-(3)所示。由答案圖5-6-(3)可知，在項目集I2,I3,I5和I9中都存在“移進(jìn)-歸約”矛盾。因為在項目集I2和I5中,因為FOLLOR(A)=d,#，F(xiàn)OLLOR(A)c=?，因此其項目集的“移進(jìn)-歸約”矛盾能經(jīng)過SLR(1)規(guī)則獲得解決；又因為在項目集I3和I9中,因為FOLLOR(B)=d,#，F(xiàn)OLLOR(B)c=?，因此其項目集的“移進(jìn)-歸約”矛盾也能經(jīng)過SLR(1)規(guī)則獲得解決；因此文法GS是SLR(1)文法。因為FOLLOR(

12、S)=#，F(xiàn)OLLOR(A)=d,#，F(xiàn)OLLOR(B)=d,#，因此文法GS的SLR(1)剖析表如答案表5-6-(3)所示。答案表5-6-(3)文法狀態(tài)ACTIONabcd0s2s312s5r43s9r645s5r46s77r389s9r610s1111s1212r5GS的SLR(1)剖析表GOTO#SAB1accr44r68r1r46r3r2r610r55-7解：在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式增添到文法G中，進(jìn)而獲得G的拓廣文法GS：SASccAdab辨別文法GS所有可歸前綴的DFA如答案圖5-7所示。因為文法GS的每個LR(0)項目集中都不含矛盾項目，因此文

13、法GS是LR(0)文法。文法GS的LR(0)剖析表如答案表5-7-(a)所示。答案表5-7-(a)文法GS的LR(0)剖析表ACTIONGOTO狀態(tài)abcd#SA0s3s211acc2s453r2r2r2r2r24r4r4r4r4r45s3s2s676r1r1r1r1r17s88r3r3r3r3r3因為FOLLOR(S)=#,c，F(xiàn)OLLOR(A)=b,c,d，因此文法GS的SLR(1)剖析表如答案表5-7-(b)所示。答案表5-7-(b)文法GS的SLR(1)剖析表ACTIONGOTO狀態(tài)abcd#SA0s3s211acc2s453r2r24r4r4r45s3s2s676r1r17s88r3

14、r3r3兩個表的同樣之處為：兩個表的GOTO表部分完整同樣。在兩個表的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，且將G中，進(jìn)而獲得G的拓廣文法GS：SAaBBAbGS的LR(1)項目集及DFA如答案圖5-

15、8所示。SS作為第0個產(chǎn)生式添文法GS的LR(1)剖析表如答案表5-8-(1)所示。答案表5-8-(1)文法GS的LR(1)剖析表狀態(tài)ACTIONGOTOab#SAB0s4s5r31231acc2r13s4s5r3634s4s575r5r5r56r27r4r4r4(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#s442II4#abab#s5503I0I4I5#abab#r5GOTOI4,B=74I0I

16、4I7#aBab#r4GOTOI0,B=35I0I3#Bab#s446III4#Bab#s55037IIII5#Bab#r5GOTOI,B=703448I0I3I4I7#BaB#r4GOTOI3,B=39III3#BB#r3GOTOI,A=603310I0I3I3I6#BBA#r2GOTOI3,A=611III6#BA#r2GOTOI,A=203012II2#A#r1GOTOI,S=10013I0I1#S#acc5-9解：(1)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，進(jìn)而獲得G的拓廣文法GS：文法SAABGS的LR(1)項目集及aBbDFA如答案圖5-9-(1)所示。文法GS的LR(1)剖析表如答案表5-9-(1)所示。因為剖析表中不含多重定義的元素，因此文法GS是LR(1)文法。答案表5-9-(1)文法GS的LR(1)剖析表狀態(tài)ACTIONGOTOab#SAB0r3r3r3121acc32s5s4r13r2r