资源描述:
《编译原理期末大题(含答案).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、文法G(S)为:S—>a|aAb S—>b|bBaA—>1A0|ε B—>1B0|ε求①LR(0)项目集族;②构造识别文法G(E)的DFA; ③构造文法G(E)的SLR(1)的分析表; ④分析句子a1100b的识别过程。解:(1)、(2)LR(0)项目集族和识别活前缀的DFA,如图A-19所示。图A-19LR(0)项目集族和DFA(3)、(4)略。