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

蔣立源編譯原理第三版第四章-習(xí)題與答案第五章習(xí)題5-1設(shè)有文法G[S]:S→A/A→aA∣AS∣/(1)找出部分符號(hào)序偶間得簡單優(yōu)先關(guān)系。(2)驗(yàn)證G[S]不就是簡單優(yōu)先文法。5-2對于算符文法G[S]:S→EE→E-T∣TT→T*F∣FF→-P∣PP→(E)∣i(1)找出部分終結(jié)符號(hào)序偶間得算符優(yōu)先關(guān)系。(2)驗(yàn)證G[S]不就是算符優(yōu)先文法。5-3設(shè)有文法G′[E]:E→E1E1→E1+T1|T1T1→TT→T*F|FF→(E)|i其相應(yīng)得簡單優(yōu)先矩陣如題圖5-3所示,試給出對符號(hào)串(i+i)進(jìn)行簡單優(yōu)先分析得過程。題圖5-3文法G′[E]得簡單優(yōu)先矩陣5-4設(shè)有文法G[E]:E→E+T|TT→T*F|FF→(E)|i其相應(yīng)得算符優(yōu)先矩陣如題圖5-4所示。試給出對符號(hào)串(i+i)進(jìn)行算符優(yōu)先分析得過程。(i*+)#(i*+)#題圖5-4文法G[E]得算符優(yōu)先矩陣5-5對于下列得文法,試分別構(gòu)造識(shí)別其全部可歸前綴得DFA與LR(0)分析表,并判斷哪些就是LR(0)文法。(1)S→aSb∣aSc∣ab(2)S→aSSb∣aSSS∣c(3)S→AA→Ab∣a5-6下列文法就是否就是SLR(1)文法？若就是,構(gòu)造相應(yīng)得SLR(1)分析表,若不就是,則闡明其理由。(1)S→Sab∣bRR→S∣a(2)S→aSAB∣BAA→aA∣BB→b(3)S→aA∣bBA→cAd∣εB→cBdd∣ε5-7對如下得文法分別構(gòu)造LR(0)及SLR(1)分析表,并比較兩者得異同。S→cAd∣bA→ASc∣a5-8對于文法G[S]:S→AA→BA∣εB→aB∣b(1)構(gòu)造LR(1)分析表;(2)給出用LR(1)分析表對輸入符號(hào)串a(chǎn)bab得分析過程。5-9對于如下得文法,構(gòu)造LR(1)項(xiàng)目集族,并判斷它們就是否為LR(1)文法。(1)S→AA→AB∣εB→aB∣b(2)S→aSa∣a第4章習(xí)題答案25-1解:(1)由文法得產(chǎn)生式與如答案圖5-1(a)所示得句型A／／a／得語法樹,可得G中得部分優(yōu)先關(guān)系如答案圖5-1(b)所示。(2)由答案圖5-1(b)可知,在符號(hào)A與/之間,即存在等于關(guān)系,又存在低于關(guān)系,故文法G[S]不就是簡單優(yōu)先文法。5-2解:(1)由文法G[S]得產(chǎn)生式可直接瞧出:()此外,再考察句型－P－－(E)與i*(T*F)得語法樹(見答案圖5-2(a)及(b))。由答案圖5-2(a)可得:－－,－－,－(由答案圖5-2(b)可得:i*,*(,(*,*)(2)由答案圖5-2(a)可知,在終結(jié)符號(hào)－與－之間,存在兩種算符優(yōu)先關(guān)系:－－,－－故文法G[S]不就是算符優(yōu)先文法。5-3解:對符號(hào)串(i+i)進(jìn)行簡單優(yōu)先分析得過程如答案表5-3所示。因?yàn)榉治龀晒?所以符號(hào)串(i+i)就是文法G′[E]得合法句子。答案表5-3符號(hào)串(i+i)得簡單優(yōu)先分析過程步驟分析棧關(guān)系當(dāng)前符號(hào)余留輸入串句柄所用產(chǎn)生式0#低于(i+i)#1#(低于i+i)#2#(i優(yōu)于+i)#iF→i3#(F優(yōu)于+i)#FT→F4#(T優(yōu)于+i)#TT1→T5#(T1優(yōu)于+i)#T1E1→T16#(E1等于+i)#7#(E1+低于i)#8#(E1+i優(yōu)于)#iF→i9#(E1+F優(yōu)于)#FT→F10#(E1+T優(yōu)于)#TT1→T11#(E1+T1優(yōu)于)#E1+T1E1→E1+T112#(E1優(yōu)于)#E1E→E113#(E等于)#14#(E)優(yōu)于#(E)F→(E)15#F優(yōu)于#FT→F16#T優(yōu)于#TT1→T17#T1優(yōu)于#T1E1→T118#E1優(yōu)于#E1E→E119#E優(yōu)于#分析成功5-4解:對符號(hào)串(i+i)進(jìn)行算符優(yōu)先分析得過程如答案表5-4所示。因?yàn)榉治龀晒?所以符號(hào)串(i+i)就是文法G[E]得合法句子。句子(i+i)及其分析過程中所得句型得語法樹如答案圖5-4所示。答案表5-4符號(hào)串(i+i)得算符優(yōu)先分析過程步驟分析棧當(dāng)前棧頂終結(jié)符號(hào)優(yōu)先關(guān)系當(dāng)前輸入符號(hào)余留輸入串最左素短語0##(i+i)#1#((i+i)#2#(ii+i)#i3#(F(+i)#4#(F++i)#5#(F+ii)#i6#(F+F+)#F+F7#(E()#8#(E))#(E)9#F##分析成功5-5解:(1)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S2、S→aSc1、S→aSb3、S→ab識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-5-(1)所示。因?yàn)槲姆℅[S]得每個(gè)LR(0)項(xiàng)目集中都不含沖突項(xiàng)目,所以文法G[S]就是LR(0)文法,故可構(gòu)造出不含沖突動(dòng)作得LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1)文法G[S]得LR(0)分析表狀態(tài)ACTIONGOTOabc#S0123456s2s2r3r1r2s4s5r3r1r2s6r3r1r2accr3r1r213(2)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S2、S→aSSS1、S→aSSb3、S→c識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-5-(2)所示。因?yàn)槲姆℅[S]得每個(gè)LR(0)項(xiàng)目集中都不含沖突項(xiàng)目,所以文法G[S]就是LR(0)文法,故可構(gòu)造出不含沖突動(dòng)作得LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2)文法G[S]得LR(0)分析表狀態(tài)ACTIONGOTOabc#S01234567s2s2r3s2s2r1r2r3r1r2s3s3r3s3s3r1r2accr3r1r21457(3)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S2、A→Ab1、S→A3、A→a識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-5-(3)所示。因?yàn)樵贚R(0)項(xiàng)目集I2中含有移進(jìn)-歸約沖突項(xiàng)目,所以文法G[S]不就是LR(0)文法,故構(gòu)造出得LR(0)分析表中含有沖突動(dòng)作。文法G[S]得LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3)文法G[S]得LR(0)分析表狀態(tài)ACTIONGOTOab#SA01234s3r1r3r2s4,r1r3r2accr1r3r2125-6解:(1)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S3、R→S1、S→Sab4、R→a2、S→bR識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-6-(1)所示。由答案圖5-6-(1)可知,在項(xiàng)目集I1與I4中都存在“移進(jìn)-歸約”沖突。在項(xiàng)目集I4={R→S·,S→S·ab}中,由于FOLLOR(R)={a},FOLLOR(R)∩{a}={a}≠,所以其項(xiàng)目集得“移進(jìn)-歸約”沖突不可能通過SLR(1)規(guī)則得到解決,從而該文法不就是SLR(1)文法。(2)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S3、A→aA1、S→aSAB4、A→B2、S→BA5、B→b識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-6-(2)所示。答案圖5-6-(2)識(shí)別G[S]全部可歸前綴得DFA因?yàn)槲姆℅[S]得每個(gè)LR(0)項(xiàng)目集中都不含沖突項(xiàng)目,所以文法G[S]就是LR(0)文法,故也就是SLR(1)文法。因?yàn)镕OLLOW(S)={a,b,#},FOLLOW(A)={a,b,#},FOLLOW(B)={a,b,#},所以文法G[S]得SLR(1)分析表如答案表5-6-(2)所示。答案表5-6-(2)文法G[S]得SLR(1)分析表狀態(tài)ACTIONGOTOab#SAB01234567891011s2s2s7r5s7r2s7r4r1r3s4s4s4r5s4r2s4r4s4r1r3accr5r2r4r1r31569113388810(3)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S4、A→ε1、S→aA5、B→cBdd2、S→bB6、B→ε3、A→cAd識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-6-(3)所示。由答案圖5-6-(3)可知,在項(xiàng)目集I2,I3,I5與I9中都存在“移進(jìn)-歸約”沖突。因?yàn)樵陧?xiàng)目集I2與I5中,由于FOLLOR(A)={d,#},FOLLOR(A)∩{c}=,所以其項(xiàng)目集得“移進(jìn)-歸約”沖突能通過SLR(1)規(guī)則得到解決;又因?yàn)樵陧?xiàng)目集I3與I9中,由于FOLLOR(B)={d,#},FOLLOR(B)∩{c}=,所以其項(xiàng)目集得“移進(jìn)-歸約”沖突也能通過SLR(1)規(guī)則得到解決;所以文法G[S]就是SLR(1)文法。因?yàn)镕OLLOR(S)={#},FOLLOR(A)={d,#},FOLLOR(B)={d,#},所以文法G[S]得SLR(1)分析表如答案表5-6-(3)所示。答案表5-6-(3)文法G[S]得SLR(1)分析表狀態(tài)ACTIONGOTOabcd#SAB0123456789101112s2s3s5s9s5s9r4r6r4s7r3r6s11s12r5accr4r6r1r4r3r2r6r51468105-7解:在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S3、A→ASc1、S→cAd4、A→a2、S→b識(shí)別文法G[S]全部可歸前綴得DFA如答案圖5-7所示。因?yàn)槲姆℅[S]得每個(gè)LR(0)項(xiàng)目集中都不含沖突項(xiàng)目,所以文法G[S]就是LR(0)文法。文法G[S]得LR(0)分析表如答案表5-7-(a)所示。答案表5-7-(a)文法G[S]得LR(0)分析表狀態(tài)ACTIONGOTOabcd#SA012345678s4r2r4r1r3s3r2r4s3r1r3s2r2r4s2r1s8r3r2r4s6r1r3accr2r4r1r3175因?yàn)镕OLLOR(S)={#,c},FOLLOR(A)={b,c,d},所以文法G[S]得SLR(1)分析表如答案表5-7-(b)所示。答案表5-7-(b)文法G[S]得SLR(1)分析表狀態(tài)ACTIONGOTOabcd#SA012345678s4s3r4s3r3s2r2r4s2r1s8r3r4s6r3accr2r1175兩個(gè)表得相同之處為:(1)兩個(gè)表得GOTO表部分完全相同。(2)在兩個(gè)表得ACTION表中,不含歸約項(xiàng)目得項(xiàng)目集對應(yīng)得行得元素完全相同,即第0,2,5,7行完全相同。兩個(gè)表得不同之處為:在兩個(gè)表得ACTION表中,含有歸約項(xiàng)目得項(xiàng)目集對應(yīng)得行得元素不同,即第3,4,6,8行得元素不同。以第3行為例,答案表5-7-(a)中得所有元素都為r2;而在答案表5-7-(b)中,因?yàn)镕OLLOR(S)={#,c},故僅在“#”與“c”列對應(yīng)得元素為r2。5-8解:(1)在文法G[S]中引入一個(gè)新得開始符號(hào)S′,且將S′→S作為第0個(gè)產(chǎn)生式添加到文法G中,從而得到G得拓廣文法G′[S′]:0、S′→S3、A→ε1、S→A4、B→aB2、A→BA5、B→b文法G[S]得LR(1)項(xiàng)目集及DFA如答案圖5-8所示。文法G[S]得LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1)文法G[S]得LR(1)分析表狀態(tài)ACTIONGOTOab#SAB01234567s4s4s4r5r4s5s5s5r5r4r3accr1r3r5r2r4126337(2)用LR(1)分析表對輸入符號(hào)串a(chǎn)bab得分析過程如答案表5-8-(2)所示。因?yàn)榉治龀晒?所以符號(hào)串a(chǎn)bab就是文法G[S]得合法句子。答案表5-8-(2)符號(hào)串a(chǎn)bab得LR分析過程步驟狀態(tài)棧符號(hào)棧余留輸入串分析動(dòng)作下一狀態(tài)1I0#abab#s442I0I4#abab#s553I0I4I5#abab#r5GOTO[I4,B]=74I0I4I7#aBab#r4GOTO[I0,B]=35I0I3#Bab#s446I0I3I4#Bab#s557I0I3I4I5#Bab#r5GOTO[I4,B]=78I0I3I4I7#BaB#r4GOTO[I3,B]=39I0I3I3#BB#r3GOTO[I3,A]=610I0I3I3I6#BBA#r2GOTO[I3,A]=611I0I3I6#BA#r2GOTO[I0,A]=212I0I2#A#r1GOTO[I0,S]=113I0I1#S#acc