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

1、第五章習(xí)題5-1設(shè)有文法GS:Sf AAf aAl AS I /(1) 找出部分符號序偶間的簡單優(yōu)先關(guān)系。(2) 驗(yàn)證GS不是簡單優(yōu)先文法。5-2 對于算符文法GS:4 EEf E-TI TTf T*F I FFf -P I PPf (E) I i(1) 找出部分終結(jié)符號序偶間的算符優(yōu)先關(guān)系。(2) 驗(yàn)證GS不是算符優(yōu)先文法。5-3 設(shè)有文法GE:EfEiEifEi+Ti|TiTi fTTf T*F|FFf (E)|i其相應(yīng)的簡單優(yōu)先矩陣如題圖5-3所示，試給出對符號串(i+i)進(jìn)行簡單優(yōu)先分析的過程。EiTiT F +*()EEi Ti T F += 二.= i題圖5-3文法GE的簡單優(yōu)先矩

2、陣5-4 設(shè)有文法GE:Ef E+T|TT*F|FFf (E)|i其相應(yīng)的算符優(yōu)先矩陣如題圖5-4所示。試給出對符號串(i+i)進(jìn)行算符優(yōu)先分析的過(i*+)#(ggggigggg*ggggg+ggggg)gggg#gggg題圖5-4文法GE的算符優(yōu)先矩陣5-5 對于下列的文法，試分別構(gòu)造識別其全部可歸前綴的DFA和LR(0)分析表，并判斷哪些是LR(O文法。(1) Sf aSbl aScI ab Sf aSSbl aSSS c(3) Sf AAf Ab I a5-6下列文法是否是SLR(1文法若是,其理由。(1) SfSabi bRRfSI a(2) Sf aSABI BAAf aAI B

3、Sf aA I bBAf cAd I e構(gòu)造相應(yīng)的 SLR(1分析表，若不是，則闡明Bf bBf cBdd I 5-7 對如下的文法分別構(gòu)造 LR(O及SLR(1分析表，并比較兩者的異同。4 cAd I bAf AScI a5-8 對于文法 GS:4AAf BAIBf aB I b(1) 構(gòu)造LR(1)分析表；給出用LR(1)分析表對輸入符號串a(chǎn)bab的分析過程。5-9 對于如下的文法，構(gòu)造 LR(1項(xiàng)目集族，并判斷它們是否為LR(1)文法。(1) Sf AAf AB I Bf aB I b Sf aSa I a第4 章 習(xí)題答案 25-1 解：G 中的(1)由文法的產(chǎn)生式和如答案圖5-1(a

4、)所示的句型A/ a/的語法樹，可得 部分優(yōu)先關(guān)系如答案圖 5-1(b)所示。A/IIIAa. 丨1IASIIA/I/A = A a SA .A A / / a a /(a)句型A/a/的語法樹(b)部分符號序偶間的優(yōu)先關(guān)系答案圖5-1(2)由答案圖5-1(b)可知，在符號A和/之間，即存在等于關(guān)系，又存在低于關(guān)系,故文法GS不是簡單優(yōu)先文法5-2 解：(1)由文法GS的產(chǎn)生式可直接看出：()此外，再考察句型一P (E)和i*(T*F)的語法樹(見答案圖5-2(a)及(b)。由答案圖5-2(a)可得：CB , -? - ,(由答案圖5-2(b)可得：(a)句型-P-(E)的語法樹(b)句型i*

5、(T*F)的語法樹答案圖5-2(2)由答案圖5-2(a)可知，在終結(jié)符號一和一之間，存在兩種算符優(yōu)先關(guān)系:故文法GS不是算符優(yōu)先文法。5-3解：對符號串(i+i)進(jìn)行簡單優(yōu)先分析的過程如答案表5-3所示。因?yàn)榉治龀晒?，所以符號?i+i)是文法GE的合法句子。答案表5-3符號串(i+i)的簡單優(yōu)先分析過程步驟分析棧關(guān)系當(dāng)前符號余留輸入串句柄所用產(chǎn)生式0#低于(i+i)#1#(低于i+i)#2#(i優(yōu)于+i)#iFT3#(F優(yōu)于+i)#FTf F4#(T優(yōu)于+i)#TTT5#(優(yōu)于+i)#T16#(日等于+i)#7#(E1 +低于i)#8#(E1+i優(yōu)于)#iFT9#(Ei+F優(yōu)于)#FTf F

6、10#(E1+T優(yōu)于)#TTuT11#(Ei+T1優(yōu)于)#E1+T1E1f E1+T112#(E1優(yōu)于)#E1Ef E113#(E等于)#14#(E)優(yōu)于#(E)Ff(E)15#F優(yōu)于#FTf F16#T優(yōu)于#TT1fT17#T1優(yōu)于#T1E1f T118#E1優(yōu)于#E1Ef E119#E優(yōu)于#分析成功5-4解：對符號串（i+i）進(jìn)行算符優(yōu)先分析的過程如答案表5-4所示。因?yàn)榉治龀晒?，所以符號串（i+i）是文法GE的合法句子。句子（i+i）及其分析過程中所得句型的語法樹如答案圖5-4所示。答案表5-4符號串（i+i）的算符優(yōu)先分析過程步驟分析棧當(dāng)前棧頂終結(jié)符號優(yōu)先關(guān)系當(dāng)前輸入符號余留輸入串最左

7、素短語0#(i+i)#1# (i+i)#2# (i+i)#i3心（F(+i)#4# (0 F+0i)#5# (0 F+0ii0)#i6# (0 F+F+0)#F+F7#0(E(0)#8#0 (0 E)0#(E)9#F#分析成功答案圖5-4句子(i+i)及其分析過程中所得句型的語法樹5-5 解：(1)在文法GS中引入一個新的開始符號 S；且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS:E 1 T I F E TI FEI TI F E +I EI TI F T F -1UJ 1 Ll UJ I + EI TFI iSf aSc識別文法GS全部可歸前綴的DFA如答案圖5-5-(1

8、)所示。答案圖5-5-(1)識別GS全部可歸前綴的DFA因?yàn)槲姆℅S的每個LR(O項(xiàng)目集中都不含沖突項(xiàng)目，所以文法GS是 LR(O文法,故可構(gòu)造出不含沖突動作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOabc#S0123456S2S23門r25455 r3 rir2S6 r3 ri r2accr3rir213在文法GS中引入一個新的開始符號S；且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS:f aSSSf aSSb識別文法GS全部可歸前綴的DFA如答案圖5-5-(2)所示。答案圖5-5-(2) 識別GS

9、全部可歸前綴的DFA因?yàn)槲姆℅S的每個LR(O項(xiàng)目集中都不含沖突項(xiàng)目，所以文法GS是 LR(O文法,故可構(gòu)造出不含沖突動作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOabc#S0S2S311acc2S2S343r3r3r3r34567S2S2 ri r2r1 r2S3S3r1r2r1 r257(3) 在文法GS中引入一個新的開始符號S；且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS:Sf Abf Af a識別文法GS全部可歸前綴的DFA如答案圖5-5-(3)所示。答案圖5-5-(3)識別GS全部可歸前綴

10、的DFA因?yàn)樵贚R(0項(xiàng)目集12中含有移進(jìn)-歸約沖突項(xiàng)目，所以文法 GS不是LR(0)文法，故 構(gòu)造出的LR(0)分析表中含有沖突動作。文法GS的 LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOab#SA0S3121acc2門S4 ,r1r133334r2r225-6 解：(1)在文法GS中引入一個新的開始符號 S,且將SS作為第0個產(chǎn)生式添加到 文法G中，從而得到G的拓廣文法G S:f SfSabf a2. 4 bR識別文法GS全部可歸前綴的DFA如答案圖5-6-(1)所示。答案圖5-6-(1)識別GS全部可歸前綴的DFA

11、由答案圖5-6-(1)可知，在項(xiàng)目集Ii和|4中都存在“移進(jìn)-歸約”沖突。在項(xiàng)目集 14 = Rf Sf S- a中,由于 FOLLOR(R)=a FOLLORR) Q a=a所以其項(xiàng)目集的 移進(jìn)- 歸約”沖突不可能通過SLR(1規(guī)則得到解決，從而該文法不是 SLR(1文法。(2) 在文法GS中引入一個新的開始符號S,且將Sf作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法G S:Sf aAf aSABf Bf BAf b識別文法GS全部可歸前綴的DFA如答案圖5-6-(2)所示。答案圖5-6-(2)識別GS全部可歸前綴的DFA因?yàn)槲姆℅S的每個LR(O項(xiàng)目集中都不含沖突項(xiàng)目，所以文法GS

12、是 LR(O文法，故也是SLR(1文法。因?yàn)?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#SAB(3) 在文法GS中引入一個新的開始符號S,且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法G S:f aAf cBddf bBf 3. Af cAd識別文法GS全部可歸前綴的DFA如答案圖5-6-(3)所示。答案圖5-6-(3) 識別GS全部可歸前綴的DFA由答案圖5-6-(3)可知，在項(xiàng)目集1

13、2 ,|3 ,|5和|9中都存在“移進(jìn)-歸約”沖突。因?yàn)樵陧?xiàng)目集12和I5中,由于FOLLOR(A)=d,#FOLLOR(AT =,所以其項(xiàng)目集的 移 進(jìn)-歸約”沖突能通過SLR(1規(guī)則得到解決；又因?yàn)樵陧?xiàng)目集 b和|9中,由于FOLLOR(B)=d,# FOLLOR(B C=,所以其項(xiàng)目集 的移進(jìn)-歸約”沖突也能通過SLR(1規(guī)則得到解決；所以文法 GS是 SLR(1文法。因?yàn)?FOLLOR(S)=# FOLLOR(A)=d,# FOLLOR(B)=d,#所以文法 GS的 SLR(1分 析表如答案表5-6-(3)所示。答案表5-6-(3) 文法GS的SLR(1分析表狀態(tài)ACTIONGOTOa

14、bcd#SAB0S2S311acc2S5r4r443S9r6r685-7解：在文法GS中引入一個新的開始符號S,且將S令作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法GS:f AScf cAdf af b識別文法GS全部可歸前綴的DFA如答案圖5-7所示。答案圖5-7 識別GS全部可歸前綴的DFA因?yàn)槲姆℅S的每個LR(O項(xiàng)目集中都不含沖突項(xiàng)目，所以文法GS是LR(O文法。文法GS的 LR(0分析表如答案表5-7-(a)所示。答案表5-7-(a) 文法GS的LR(0)分析表狀態(tài)ACTIONGOTOabcd#SA0S3S211acc2S453r2r2r2r24r4r4r4r4r45S3S2

15、S376r1riririri7S883r3r3r3r3因?yàn)?FOLLOR(S)=#,c FOLLOR(A)=b,c,d所以文法 GS的 SLR(1分析表如答案表5-7-(b)所示。答案表5-7-(b) 文法GS的SLR(1分析表狀態(tài)ACTIONGOTOabcd#SA0S3S211acc2S453r2r24r4r4r45S3S2S376r1r17S88r3r3r3兩個表的相同之處為：(1) 兩個表的GOTO表部分完全相同。(2) 在兩個表的ACTION表中，不含歸約項(xiàng)目的項(xiàng)目集對應(yīng)的行的元素完全相同， 即第0,2,5,7行完全相同。兩個表的不同之處為：在兩個表的ACTION表中，含有歸約項(xiàng)目的項(xiàng)

16、目集對應(yīng)的行的元素不同， 即第3,4,6,8 行的元素不同。以第3行為例，答案表5-7-(a)中的所有元素都為2 ；而在答案表5-7-(b) 中,因?yàn)镕OLLOR(S)=#,，故僅在“ #”和“ c”列對應(yīng)的元素為 遼。5-8 解：(1)在文法GS中引入一個新的開始符號S,且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法G S:f Af aBf BAf b文法GS的LR(1)項(xiàng)目集及DFA如答案圖5-8所示。答案圖5-8 文法GS的LR 項(xiàng)目集及DFA文法GS的LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1) 文法GS的LR(1)分析表狀態(tài)ACTIONGOTOab#

17、SAB0S4S5r31231acc2r13S4S5r3634S4S575r5r5r56r27r4r4r4用LR(1)分析表對輸入符號串a(chǎn)bab的分析過程如答案表5-8-(2)所示。因?yàn)榉治龀晒?，所以符號串a(chǎn)bab是文法GS的合法句子答案表5-8-(2)符號串a(chǎn)bab的LR分析過程步驟狀態(tài)棧符號棧余留輸入串分析動作下一狀態(tài)1I0#abab#S442|0|4#abab#S553|0|4|5#abab#r5GOTO4 ,B=74I0I4I7#aBab#r4GOTOb ,B=35|0|3#Bab#S446|0|3|4#Bab#S557|0|3|4|5#Bab#r5GOTO4,B=78|0|3|4 |7

18、#BaB#r4GOTO3 ,B=39I0I3I3#BB#3GOTO3 ,A=610|0|3|3 |6#BBA#r2GOTO3 ,A=611I0I3I6#BA#2GOTOb ,A=212I0I2#A#r1GOTOb ,S=113|0|1#S#acc5-9 解：(1)在文法GS中引入一個新的開始符號S,且將SS作為第0個產(chǎn)生式添加到文法G中，從而得到G的拓廣文法G S:f Af aBf ABf b文法GS的LR(1)項(xiàng)目集及DFA如答案圖5-9-(1)所示。Io： S S , #A , #AB , a/b/# , a/b/# I1: S S , #I2： S A , #AA B , a/b/#B aB , a/b/#B b , a/b/#.I3: AAB , a/b/#I4： B b , a/b/#16： BaB , a/b/# aaI5: B aB,a/b/#B aB,a/b/#bB b ,a/b/#bB答案圖5-9-(1) 文法GS的LR(1)項(xiàng)目集及DFA文法GS的LR(1)分析表如答案表5-9-(1)所示。因?yàn)榉治霰碇胁缓嘀囟x的元素,所以文法GS是 LR(1)文法。答案表5-9-(1) 文法GS的LR(1)分析表狀態(tài)ACTIONGOTOab#SAB0r3r3r3121acc32S5S4r13