《編譯原理第六章習(xí)題解答》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理第六章習(xí)題解答（3頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、真誠(chéng)為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正。
第六章 習(xí)題答案
4．文法G： SS;G|G
GG(T)|H
Ha|(S)
TT+S|S
（1）該文法是算符文法，且不包含ε產(chǎn)生式。
計(jì)算每個(gè)非終結(jié)符的FIRSTVT集合：
FIRSTVT(S) = FIRSTVT(S)∪{;}∪FIRSTVT(G) = {;, a, (}
FIRSTVT(G) = FIRSTVT(G)∪{(}∪FIRSTVT(H) = {a, (}
FIRSTVT(H) = {a, (} = {a, (}
FIRSTVT(T) = FIRSTVT(T)∪{+}∪FIRSTVT(S)
2、 = {+, ;, a, (}
計(jì)算每個(gè)非終結(jié)符的LASTVT集合：
LASTVT(S) = {;}∪LASTVT(G) = {;, a, )}
LASTVT(G) = {)}∪LASTVT(H) = {a, )}
LASTVT(H) = {a, )} = {a, )}
LASTVT(T) = {+}∪LASTVT(S) = {+, ;, a, )}
①關(guān)系
由#S#可知： ##
由GG(T)|H可知： ()
②關(guān)系
S#
LASTVT(S)# → {;, a, )}#
S;
LASTVT(S); → {;, a, )};
G(
3、
LASTVT(G)( → {a, )}(
T)
LASTVT(T)) → {+, ;, a, )})
S)
LASTVT(S)) → {;, a, )})
T+
LASTVT(T)+ → {+, ;, a, )}+
③關(guān)系
#S
#FISRTVT(S) → #{;, a, (}
;G
;FISRTVT(G) → ;{a, (}
(T
(FISRTVT(T) → ({+, ;, a, (}
(S
(FISRTVT(S) → ({;, a, (}
+S
+FISRTVT(S)
4、→ +{;, a, (}
構(gòu)造算符優(yōu)先關(guān)系表如下：
+
;
a
(
)
#
+
;
a
(
)
#
由該文法的算符優(yōu)先關(guān)系表可知，該文法是算符優(yōu)先文法。
（2）句型a(T+S);H;(S)的語法樹如右圖所示：
短語：a(T+S);H;(S)，a(T+S);H，a(T+S)，a，T+S ，H，(S)
句柄：a
素短語：a，T+S，(S)
最左素短語：a
（3）
對(duì)a;(a+a)進(jìn)行算符
5、優(yōu)先分析步驟如下：
步驟
符號(hào)棧
當(dāng)前符號(hào)
剩余符號(hào)串
移進(jìn)或歸約
1
#
a
;(a+a)#
移進(jìn)
2
#a
;
(a+a)#
歸約
3
#N
;
(a+a)#
移進(jìn)
4
#N;
(
a+a)#
移進(jìn)
5
#N; (
a
+a)#
移進(jìn)
6
#N; (a
+
a)#
歸約
7
#N; (N
+
a)#
移進(jìn)
8
#N; (N+
a
)#
移進(jìn)
9
#N; (N+a
)
#
歸約
10
#N; (N+N
)
#
歸約
11
#N; (N
)
#
移進(jìn)
12
#N; (N)
6、
#
歸約
13
#N; N
#
歸約
14
#N
#
分析成功
對(duì)(a+a)進(jìn)行算符優(yōu)先分析步驟如下：
步驟
符號(hào)棧
當(dāng)前符號(hào)
剩余符號(hào)串
移進(jìn)或歸約
1
#
(
a
移進(jìn)
2
#(
a
+a)#
移進(jìn)
3
#(a
+
a)#
歸約
4
#(N
+
a)#
移進(jìn)
5
#(N+
a
)#
移進(jìn)
6
#(N+a
)
#
歸約
7
#(N+N
)
#
歸約
8
#(N
)
#
移進(jìn)
9
#(N)
#
歸約
10
#N
#
分析成功
采用算符優(yōu)先分析方法進(jìn)行分析，可知：a;(a+a)和(a+a)均應(yīng)為該文法的句子。
（4）
句子a;(a+a)的最右推導(dǎo)為：
S=>S;G=>S;H=> S;(S)=> …（無法推出句子a;(a+a)）
句子(a+a)的最右推導(dǎo)為：
S=>G=>H=> (S)=>…（無法推出句子(a+a)）
由以上推導(dǎo)過程可知：a;(a+a)和(a+a)均不是該文法的句子。
（5）由（3）和（4）可看出，算符優(yōu)先文法忽略了對(duì)單個(gè)非終結(jié)符的歸約過程，不是規(guī)范歸約，因此無法避免把錯(cuò)誤的句子得到正確的歸約。
（6）算符優(yōu)先分析過程不是最右推導(dǎo)的逆過程，而規(guī)范歸約是最右推導(dǎo)的逆過程。
3 / 3
編譯原理第六章習(xí)題解答
