编译原理期末试题(8套含答案+大题集)(5)

表A-4 LL(1)分析表 输输入符号 入 a b c # VN S S→aBc S→bAB A A→aAb A→b B B→b B→? B→?

（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。

步骤 符号栈 输入串 所用的产生式 1 #S baabbb# S?bAB 2 3 4 5 6 7 #BAb #BA #BbAa #BbA #BbbAa #BbbA baabbb# aabbb# A?aAb aabbb# abbb# A?aAb abbb# bbb# A?b bbb# bb# b# # # B?ε 成功 8 #Bbbb 9 #Bbb 10 #Bb 11 #B 12 #

图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, )}

（2）算符优先矩阵，如表A-5所示。

表A-5 优先矩阵 ( ) ; i ( ) ; i # ?? B ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 第21页共6页

# ?? ?? 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. 设文法Ｇ（Ｓ）为：

Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε

求①ＬＲ（０）项目集族；②构造识别文法Ｇ（Ｅ）的ＤＦＡ； ③构造文法Ｇ（Ｅ）的SLR（１）的分析表； ④分析句子ａ１１００ｂ的识别过程。

解：（1）、（2）LR(0)项目集族和识别活前缀的DFA，如图A-19所示。

图A-19 LR(0)

第22页共6页

I1: S′?S· SaAbI2: S?a· S?a·Ab A?·1A0 A?·? I4: S?aA·b AI8: S?aAb· I9: A?1A·0 01I5: A?1·A0 A?·1A0 A?·? 1I12: A?1A0· I0: S′?·S S?·a S?·aAb S?·b S?·bBa BbI3: S?b· S?b·Ba B?·1B0 B?·? I6: S?bB·a aBI10: S?bBa· I11: B?1B·0 011I7: B?1·B0 B?·1B0 B?·? I13: B?1B0·

项目集族和DFA

（3）、（4）略。

第23页共6页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理期末试题(8套含答案+大题集)(5)在线全文阅读。