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

1、第五章習(xí)題5-1設(shè)有文法GS：SA/AaAAS/找出部分符號序偶間的簡單優(yōu)先關(guān)系?？紦?jù)GS不是簡單優(yōu)先文法。5-2對于算符文法GS：SEEE-TTTT*FFF-PPP(E)i找出部分終結(jié)符號序偶間的算符優(yōu)先關(guān)系。考據(jù)GS不是算符優(yōu)先文法。5-3設(shè)有文法GE：EEEE+T|T1TTTT*F|FF(E)|i11111其相應(yīng)的簡單優(yōu)先矩陣如題圖5-3所示，試給出對符號串（i+i）進行簡單優(yōu)先解析的過程。題圖5-3文法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*+)#(i*+)#題

2、圖5-4文法GE的算符優(yōu)先矩陣5-5對于以下的文法，試分別構(gòu)造鑒別其全部可歸前綴的DFA和LR(0)解析表，并判斷哪些是LR(0)文法。SaSbaScabSaSSbaSSScSAAAba5-6以下文法是否是SLR(1)文法？若是，構(gòu)造相應(yīng)的SLR(1)解析表，若不是，則說明其原由。(1)SSabbRRSa(2)SaSABBAAaABBb(3)SaAbBAcAdBcBdd5-7對以下的文法分別構(gòu)造LR(0)及SLR(1)解析表，并比較兩者的異同。ScAdbAASca5-8對于文法GS:SAABABaBb構(gòu)造LR(1)解析表；(2)給出用LR(1)解析表對輸入符號串a(chǎn)bab的解析過程。5-9對于以

3、下的文法，構(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)。由答案圖5-2(a)可得：,(由答案圖5-2(b)可得：i*,*(,(*,*）由答案圖5-2(a)可知，在終結(jié)符號和之間，存在

4、兩種算符優(yōu)先關(guān)系：,故文法GS不是算符優(yōu)先文法。5-3解：對符號串(i+i)進行簡單優(yōu)先解析的過程如答案表5-3所示。由于解析成功，所以符號串(i+i)是文法GE的合法句子。答案表5-3符號串(i+i)的簡單優(yōu)先解析過程當(dāng)前余留所用步驟解析棧關(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)于)#TT1T11#(E1+T優(yōu)于)#E+TEE+T11111

5、112#(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)由于解析成功，所以符號串進行算符優(yōu)先解析的過程如答案表(i+i)是文法GE的合法句子。5-4所示。句子(i+i)及其解析過程中所得句型的語法樹如答案圖5-4所示。答案表5-4符號串（i+i)的算符優(yōu)先解析過程當(dāng)前棧頂步驟解析棧終結(jié)符號0#1（#(2i#(i3(#(F4+#(F+5#(F+ii6+#(F+F7#(E(8)#(E)優(yōu)先當(dāng)前輸余留最左關(guān)系入符號輸入串素短語（i

6、+i)#i+i)#+i)#i+i)#i)#)#i)#F+F)#(E)解析9#F#成功5-5解：(1)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而獲取G的拓廣文法GS：SaScaSbab鑒別文法GS全部可歸前綴的DFA如答案圖5-5-(1)所示。由于文法GS的每個LR(0)項目集中都不含矛盾項目，所以文法GS是LR(0)文法，故可構(gòu)造出不含矛盾動作的LR(0)解析表如答案表5-5-(1)所示。答案表5-5-(1)文法GS的LR(0)解析表ACTIONGOTO狀態(tài)abc#S0s211acc2s2s433s5s64r3r3r3r35r1r1r1r16r2r2r2r

7、2(2)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而獲取G的拓廣文法GS：SaSSSaSSbc鑒別文法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#S0s2s311acc2s2s343r3r3r3r34s2s355s2s376r1r1r1r17r2r2r2r2(3)在文法GS中引入一個新的開始符號S，且將加到文法G中，從而獲取G

8、的拓廣文法GS：SAbAa鑒別文法GS全部可歸前綴的DFA如答案圖5-5-(3)SS作為第所示。0個產(chǎn)生式添由于在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#SA0s3121acc2r1s4,r1r13r3r3r34r2r2r25-6解：(1)在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而獲取SSabG的拓廣文法GS：Sa2.SbR鑒別文法GS全部可歸前綴的

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

10、是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中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式添加到文法G中，從而獲取G的拓廣文法GS：SaAcBddbB3.AcAd鑒別文法GS

11、全部可歸前綴的DFA如答案圖5-6-(3)所示。由答案圖5-6-(3)可知，在項目集I2,I3,I5和I9中都存在“移進-歸約”矛盾。由于在項目集I2和I5中,由于FOLLOR(A)=d,#，F(xiàn)OLLOR(A)c=?，所以其項目集的“移進-歸約”矛盾能經(jīng)過SLR(1)規(guī)則獲取解決；又由于在項目集I3和I9中,由于FOLLOR(B)=d,#，F(xiàn)OLLOR(B)c=?，所以其項目集的“移進-歸約”矛盾也能經(jīng)過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-(

12、3)所示。答案表5-6-(3)文法狀態(tài)ACTIONabcd0s2s312s5r43s9r645s5r46s77r389s9r610s1111s1212r5GS的SLR(1)解析表GOTO#SAB1accr44r68r1r46r3r2r610r55-7解：在文法GS中引入一個新的開始符號S，且將SS作為第0個產(chǎn)生式增加到文法G中，從而獲取G的拓廣文法GS：SASccAdab鑒別文法GS全部可歸前綴的DFA如答案圖5-7所示。由于文法GS的每個LR(0)項目集中都不含矛盾項目，所以文法GS是LR(0)文法。文法GS的LR(0)解析表如答案表5-7-(a)所示。答案表5-7-(a)文法GS的LR(0

13、)解析表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#SA0s3s211acc2s453r2r24r4r4r45s3s2s676r1r17s88r3r3r3兩個表的相同之處為：兩個表的GOTO表部分完好相同。在兩個表的ACTION表中，不含歸約項目的項目集對應(yīng)的行

14、的元素完好相同，即第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中，從而獲取G的拓廣文法GS：SAaBBAbGS的LR(1)項目集及DFA如答案圖5-8所示。SS作為第0個產(chǎn)生式添文法GS的LR(1)解析表如答案表5-8-(1)所示。答案表5-8-(1)文法GS的L

15、R(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=74I0I4I7#aBab#r4GOTOI0,B=35I0I3#Bab#s446III4#Bab#s55037IIII5#Ba

16、b#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中，從而獲取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#SAB0r3r3r3121acc32s5s4r13r2r2r2