资源描述：
《编译原理期末大题(含答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《编译原理》期末大题1.设有如下文法G（S），试消除其左递归。G（S）：S—>Ac
2、cA—>Bb
3、bB—>Sa
4、a解：S→abcS′
5、bcS′
6、cS′,S′→abcS′
7、2.试构造与下面G（S）等价的无左递归的文法。G（S）：S—>Sa
8、Nb
9、cN—>Sd
10、Ne
11、f解：S→fN′bS′
12、cS′,S′→aS′
13、dN′bS′
14、,N′→eN′
15、3.设有文法G（S）：S—>aBc
16、bABA—>aAb
17、bB—>b
18、ε①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELEC
19、T集。②构造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
20、(B→)={c,#}因此，所得的LL(1)分析表如表A-4所示。表A-4LL(1)分析表输入VN输入符号abc#SS→aBcS→bABAA→aAbA→bBB→bB→B→（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。图A-16识别串baabbb的过程1.对下列文法G(S)：S—>D(R)R—>R;P
21、PP—>S
22、ID—>i①计算文法G中每个非终结符的FIRSTVT集和LASTVT集。②构造文法G的算符优先关系矩阵。解：（1）FIRSTVT(S)={(,i}，FIRS
23、TVT(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#2.已知文法G(S)：S—>a
24、(T)T—>T,S
25、S①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：（1）最左推导：S(
26、T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))语法树：如图A-16所示。图A-16(a,(a,a))的语法树（2）句型(T,a,(T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。短语：a
27、
28、T,a
29、
30、(T)
31、
32、T,a,(T)
33、
34、(T,a,(T))直接短语：a
35、
36、(T)素短语：a
37、
38、(T)最左素短语：a句柄：a活前缀：
39、
40、(
41、
42、(T
43、
44、(T,
45、
46、(T,a图A-17(T,a,(T))的语法树1.设
47、文法Ｇ（Ｓ）为：Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａＡ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε求①ＬＲ（０）项目集族；②构造识别文法Ｇ（Ｅ）的ＤＦＡ； ③构造文法Ｇ（Ｅ）的SLR（１）的分析表； ④分析句子ａ１１００ｂ的识别过程。解：（1）、（2）LR(0)项目集族和识别活前缀的DFA，如图A-19所示。图A-19LR(0)项目集族和DFA（3）、（4）略。
