《編譯原理第七章習(xí)題參考答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理第七章習(xí)題參考答案（7頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、第1 題
已知文法
A→aAd|aAb|ε
判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過程。
答案：
文法：
A→aAd|aAb|ε
拓廣文法為G′，增加產(chǎn)生式S′→A
若產(chǎn)生式排序?yà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)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示
在I0 中：
A →.aAd 和A →.
2、aAb 為移進(jìn)項(xiàng)目，A →.為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法
不是LR(0)文法。
在I0、I2 中：
Follow(A) ∩{a}= {d，b，#} ∩{a}=f
所以在I0、I2 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。
構(gòu)造的SLR(1)分析表如下：
對(duì)輸入串a(chǎn)b#的分析過程:
第2 題
若有定義二進(jìn)制數(shù)的文法如下：
S→LL|L
L→LB|B
B→0|1
(1) 試為該文法構(gòu)造LR 分析表，并說明屬哪類LR 分析表。
(2) 給出輸入串101.110 的分析過程。
答案：
3、
文法：
S→L.L|L
L→LB|B
B→0|1
拓廣文法為G′，增加產(chǎn)生式S′→S
若產(chǎn)生式排序?yà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)項(xiàng)目
4、集族及識(shí)別活前綴的DFA 如下圖所示：
在I2 中：
B →.0 和 B →.1 為移進(jìn)項(xiàng)目，S →L.為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不
是LR(0)文法。
在I2、I8 中：Follow(s) ∩{0，1}= { #} ∩{0，1}=
所以在I2 、I8 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。
構(gòu)造的SLR(1)分析表如下：
對(duì)輸入串101.110#的分析過:
第6 題
文法G=({U,T,S},{a,b,c,d,e},P,S)
其中P 為：
S→UTa|Tb
T
5、→S|Sc|d
U→US|e
(1) 判斷G 是LR(0)，SLR(1)，LALR(1)還是LR(1)，說明理由。
(2) 構(gòu)造相應(yīng)的分析表。
答案：
文法：
S→UTa|Tb
T→S|Sc|d
U→US|e
拓廣文法為G，增加產(chǎn)生式S→S
若產(chǎn)生式排序?yà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}
Foll
6、ow(S ) = {#}
Follow(S ) = {a,b,c,d,e,#}
Follow(U ) = {d,e}
Follow(T ) = {a,b}
G′的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示：
在I1 中：
S →S.為接受項(xiàng)目，T →S. 為歸約項(xiàng)目，T →S.c 為移進(jìn)項(xiàng)目，存在接受-歸約和移進(jìn)-歸約沖突，因此所給文法不是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 中的接受-歸約和移進(jìn)-歸約沖突與I8 中的移進(jìn)-歸約和歸約-歸約沖突可以由
Follow 集解決，所以G 是SLR(1)文法。
構(gòu)造的SLR(1)分析表如下：
編譯原理第七章習(xí)題參考答案
