发布时间 : 星期日 文章编译原理期末试题（8套含答案+大题集）更新完毕开始阅读8393a8f60b4c2e3f56276349
A—>aAb|b B—>b|ε
①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 ②构造LL(1)分析表，并分析符号串baabbb是否是。
解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε} FOLLOW(A)={b, #}, FOOLOW(B)={c, #}
SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a}, SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→?)={c, #}
因此，所得的LL(1)分析表如表A-4所示。
表A-4 LL(1)分析表 （2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。
步骤 符号栈 输入串 所用的产生式 1 #S baabbb# S?bAB 2 #BAb baabbb# 3 #BA aabbb# A?aAb 4 #BbAa aabbb# 5 #BbA abbb# A?aAb 6 #BbbAa abbb# 7 #BbbA bbb# A?b 8 #Bbbb 9 #Bbb 10 #Bb 11 #B 12 # bbb# bb# b# # # B?ε 成功
输输入符号 入 a b c # VN S S→aBc S→bAB A A→aAb A→b B B→b B→? B→? 图A-16 识别串baabbb的过程
4. 对下列文法G(S)：
S—>D(R) R—>R;P|P P—>S|I D—>i
①计算文法G中每个非终结符的FIRSTVT集和LASTVT集。 ②构造文法G的算符优先关系矩阵。 解：（1）FIRSTVT(S)={(, i}，FIRSTVT(D) ={i}，FIRSTVT(R)={;, (, i}，FIRSTVT(P)={i, (}，LASTVT(S)={)}，LASTVT(D)={i}，LASTVT(R) = {;, ), i}，LASTVT(P)={i, )}
第49页共6页
（2）算符优先矩阵，如表A-5所示。
表A-5 优先矩阵 ( ) ; i # ( ) ; i # ?? B ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? B 5. 已知文法G(S)： S—>a|(T) T—>T,S|S
①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。
解：（1）最左推导：S?(T)?(T,S)?(S,S) ?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a, S))?(a,(a,a))
语法树：如图A-16所示。
S( T )T , SSa( T )T , SSaa图A-16 (a,(a,a))的语法树
（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。
短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a
活前缀：? || ( || (T || (T , || (T , a
S( T )T , ST , S( T )a 图A-17 (T,a,(T))的语法树
6. 设文法Ｇ（Ｓ）为：
Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε
第50页共6页