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