編譯原理實(shí)踐及應(yīng)用習(xí)題的參考答案(編輯修改稿)
2024-07-23 18:38 本頁面
【文章內(nèi)容簡介】 ) = {+}∪{),}={+,),}Follow(T39。)= Follow(T)={+,},} (3)Follow(F)= First(T39。)＼{e}∪Follow(T) (3,4) = {(,a,b,∧,+ ,),}Follow(F39。)= Follow(F) (5) = {(,a,b,∧,+ ,),}Follow(P)= First(F39。)＼{e}∪Follow(F) (5,6) ={*,(,a,b,∧,+ ,),} (2) 證明: ∵a. 文法不含左遞歸；b. 每個非終結(jié)符的各個侯選式的First集不相交；c. First(E39。)∩Follow(E39。)={+, e}∩{,),}=FFirst(T39。)∩Follow(T39。)={(,a,b,∧, e}∩{+,)}=FFirst(F39。)∩Follow(F39。)={*, e}∩{,a,( ∧,+,},}= F∴改造后的文法滿足LL(1)文法的三個條件，是LL(1)文法。(3) 預(yù)測分析表如下所示。ab*+∧()EE→TE39。E→TE39。E→TE39。E39。E39?！?EE39?！鷈E39。→eTT→FT39。T→FT39。T→FT39。T→FT39。T39。T39。→TT39。→TT39?！鶷T39?！鶷T39?！鷈T39?！鷈FF→PF39。F→PF39。F→PF39。F→PF39。F39。F39?！鷈F39?！鷈F39?！?F39。F39?！鷈F39?！鷈F39?！鷈F39?！鷈F39?！鷈PP→aP→bP→∧P→(E)11. 解答：(1)S→Abc A→a│eB→b│ea. 文法不含左遞歸； b. S,A,B各候選式的First集不相交；c. First(A)∩Follow(A)={a,e}∩=F First(B)∩Follow(B)={b,e}∩F=F∴該文法為LL(1)文法。(2) S→AbA→a│B│e B→b│e a. 文法不含左遞歸；b. S,A,B各候選式的First集不相交；c. First(A)∩Follow(A)={a,b, e}∩={b }≠F∴ 該文法不是LL(1)文法。12. 解答：① 最右推導(dǎo)：E=T=F=(E)=(E＋T)=(E＋F)=(E＋i)= (T＋i)=(T*F＋i)語法樹： 句型(T*F＋i)的語法樹② 短語：(T*F＋i)，T*F＋i，T*F，i 素短語：T*F，i最左素短語：T*F③ 由于E =E+T =E+T*F，故E+T*F為該文法的句型 短語：T*F、E+T*F 直接短語： T*F 句柄： T*F13. 解答：最左推導(dǎo)：S= (T) = (T,S) = (S,S) = (a,S) = (a,(T)) = (a,(T,S)) = (a,(S,S)) = (a,(a,S)) = (a,(a,a))最右推導(dǎo)：S= (T) = (T,S) = (T,(T)) = (T,(T,S)) = (T,(T,a)) = (T,(T,a)) = (T,(a,a)) = (S,(a,a)) = (a,(a,a))文法中S和T的FirstVT和LastVT集為：FirstVT(S)={a,(} FirstVT(T)={,a, (} lastVT(S)={a, ）} lastVT(T)={,a,)}文法G[S]的算符優(yōu)先關(guān)系表： 根據(jù)優(yōu)先關(guān)系表，對每個終結(jié)符或建立符號f與g，把f(和g)分成一組。根據(jù)G[S]的算符優(yōu)先關(guān)系表，畫出如下的有向圖。優(yōu)先函數(shù)如下：用算符優(yōu)先分析法分析句子(a,(a,a))。給定的輸入符號串是文法的一個句子。14. 解答：(1) 該文法的拓廣文法G39。為 0．S39。 → S 1．S → aSAB2．S → BA 3．A → aA4．A → B 5．B → b其LR(0)項目集規(guī)范族和識別活前綴的DFA如下:I0 = {S39?！鶶, S→aSAB, S→BA, B→b}I1 = {S39?！鶶}I2 = {B→b}I3 = {S→aSAB, S→aSAB, S→BA, B→b}I4 = {S→BA, A→aA, A→B, B→b}I5 = {S→aSAB, A→aA, A→B, B→b}I6 = {S→aSAB, B→b}I7 = {A→aA, A→aA, A→B, B→b}I8 = {A→B}I9 = {S→BA}I10 = {S→aSAB}I11 = {A→aA}顯然，上述狀態(tài)中沒有出現(xiàn)沖突。顯然，該文法是LR(0)的文法，因此也是SLR(1)的。 求各個非終結(jié)符的Follow集，以便構(gòu)造分析表： Follow(S39。)={} Follow(S)={a,b,}Follow(A)={a,b,}Follow(B)={a,b,}構(gòu)造的SLR(1)分析表如下： (2) 該文法的拓廣文法G39。為 0．S39。 → S 1．S → Sab 2．S → bR 3．R → S 4．R → a 其LR(0)項目集規(guī)范族和識別活前綴的DFA如下:I0 = {S39?！鶶, S→Sab, S→bR}I1 = {S39?！鶶, S→Sab}I2 = {S→bR, R→S, R→a, S→Sab, S→bR}I3 = {S→Sab}I4 = {S→bR}I5 = {R→S, S→Sab}I6 = {R→a}I7 = {S→Sab}顯然，I1和I5存在移進(jìn)歸約沖突。求S39。和R的Follow集： Follow(S39。)={ } Follow(R)=Follow(S)={a,}在I5中，出現(xiàn)的移進(jìn)－歸約沖突，且Follow(R)∩{a}={a}，不能用SLR(1)方法解決。因此，此文法不是SLR(1)文法。15. 解答：(1) 構(gòu)造其拓廣文法G39。的產(chǎn)生式為 0．S39。 → S 1．S → A2．A → BA 3．A → e4．B → aB 5．B → b構(gòu)造其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下:I0 = { [S39?！鶶, ], [S→A, ], [A→BA, , [A→, ], [B→aB, a/b/], [B→b, a/b/]} I1 = {[S39?！鶶, ]}I2 = {[S→A, ]}I3 = {[A→BA, ], [A→BA, ], [A→, ],[B→aB, a/b/], [B→b, a/b/]}I4 = {[B→b, a/b/]} I5 = {[B→aB, a/b/], [B→aB, a/b/], [B→b, a/b/]}I6 = {[A→BA, ]}I7 = {[B→aB, a/b/]}該文法的LR(1)項目集規(guī)范族中沒有沖突，所以該文法是LR(1)文法。構(gòu)造LR(1)分析表如下：以上分析表無多的定義入口，所以該文法為LR(1)文法。(3)對于輸入串a(chǎn)bab，其分析過程如下： 16. 解答：(1) 對于產(chǎn)生式S→AaAb|BbBa 來說First(AaAb)∩First(BbBa)={a}∩=FA，B∈VN僅有一條候選式。因此，這個文法是LL(1)的。(2) 下面構(gòu)造這個文法的識別活前綴的DFA。I0 = {S39?！鶶, S→AaAb, S→BbBa, A→, B→} I1 = {S39?！鶶}I2 = {S→AaAb}I3
公司管理相關(guān)推薦
鄂ICP備17016276號-1