編譯原理第七章習題參考答案.doc

《編譯原理第七章習題參考答案.doc》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第七章習題參考答案.doc（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第1 題 已知文法 A→aAd|aAb|ε 判斷該文法是否是SLR(1)文法，若是構(gòu)造相應分析表，并對輸入串a(chǎn)b#給出分析過程。 答案： 文法： A→aAd|aAb|ε 拓廣文法為G′，增加產(chǎn)生式S′→A 若產(chǎn)生式排序為： 0 S →A 1 A →aAd 2 A →aAb 3 A →ε 由產(chǎn)生式知： First (S ) = {ε,a} First (A ) = {ε,a} Follow(S ) = {#} Follow(A ) = {d,b,#} G′的LR(0)項目集族及識別活前綴的DFA 如下圖所示 在I0 中： A →.aAd 和A →.aAb 為移進項目，A →.為歸約項目，存在移進-歸約沖突，因此所給文法 不是LR(0)文法。 在I0、I2 中： Follow(A) ∩{a}= {d，b，#} ∩{a}=f 所以在I0、I2 中的移進-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下： 對輸入串a(chǎn)b#的分析過程: 第2 題 若有定義二進制數(shù)的文法如下： S→LL|L L→LB|B B→0|1 (1) 試為該文法構(gòu)造LR 分析表，并說明屬哪類LR 分析表。 (2) 給出輸入串101.110 的分析過程。 答案： 文法： S→L.L|L L→LB|B B→0|1 拓廣文法為G′，增加產(chǎn)生式S′→S 若產(chǎn)生式排序為： 0 S →S 1 S →L.L 2 S →L 3 L →LB 4 L →B 5 B →0 6 B →1 由產(chǎn)生式知： First (S ) = {0,1} First (S ) = {0,1} First (L ) = {0,1} First (B ) = {0,1} Follow(S ) = {#} Follow(S ) = {#} Follow(L ) = {.,0,1,#} Follow(B ) = {.,0,1,#} G′的LR(0)項目集族及識別活前綴的DFA 如下圖所示： 在I2 中： B →.0 和 B →.1 為移進項目，S →L.為歸約項目，存在移進-歸約沖突，因此所給文法不 是LR(0)文法。 在I2、I8 中：Follow(s) ∩{0，1}= { #} ∩{0，1}= 所以在I2 、I8 中的移進-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下： 對輸入串101.110#的分析過: 第6 題 文法G=({U,T,S},{a,b,c,d,e},P,S) 其中P 為： S→UTa|Tb T→S|Sc|d U→US|e (1) 判斷G 是LR(0)，SLR(1)，LALR(1)還是LR(1)，說明理由。 (2) 構(gòu)造相應的分析表。 答案： 文法： S→UTa|Tb T→S|Sc|d U→US|e 拓廣文法為G，增加產(chǎn)生式S→S 若產(chǎn)生式排序為： 0 S →S 1 S →UTa 2 S →Tb 3 T →S 4 T →Sc 5 T →d 6 U →US 7 U →e 由產(chǎn)生式知： First (S ) = {d,e} First (S ) = {d,e} First (U ) = {e} First (T ) = {d,e} Follow(S ) = {#} Follow(S ) = {a,b,c,d,e,#} Follow(U ) = {d,e} Follow(T ) = {a,b} G′的LR(0)項目集族及識別活前綴的DFA 如下圖所示： 在I1 中： S →S.為接受項目，T →S. 為歸約項目，T →S.c 為移進項目，存在接受-歸約和移進-歸約沖突，因此所給文法不是LR(0)文法。 在I1 中： Follow(S) ∩ Follow(T)= { #} ∩{a ，b}=f Follow(T) ∩{ c}= { a ，b} ∩{c}=f 在I8 中： Follow(U) ∩ Follow(T) ∩{ c}={d,e}∩{ a ，b} ∩{c}=f 所以在I1 中的接受-歸約和移進-歸約沖突與I8 中的移進-歸約和歸約-歸約沖突可以由 Follow 集解決，所以G 是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下：