编译原理B答案.doc

文档介绍：编译原理试题答案及评分参考(B卷)
(课程代号: 9047 )
一、单项选择题
题号
1
2
3
4
5
6
7
8
9
10
答案
D
D
D
A
C
A
D
A
题号
11
12
13
14
15
16
17
18
19
20
答案
C
A
B
A
D
A
二、多项选则题
题号
1
2
3
4
5
答案
BCE
BCDE
BCD
AE
BD
三、填空题
,目标程序
、1型、2型,3型文法
,句柄
,最左归约
30. 非终结
四、计算题
:
S
S d A
S
( A )
S d A E )
句型(SdSdS)的语法树如下所示:

(1分)
其所有短语:①(SdSdS)② SdSdS③SdS④S(2分)
简单短语:S(1分)
句柄:S(1分)
素短语:SdS(1分)
最左素短语:SdS(1分)
:
G[A]:A→aB
B→bC
C→aD
D→bD|aE
E→aE|bD|ε
:对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)
[评分标准]文法四元组完整1分;每个非终结符对应的产生式正确各2分
:
n9
n10
n1
n2
n3
T1
A
B
n4
5
T2
n5
20
M
n6
n7
n8
T3
D
C
-
+
T4
L
*
,N
,T4
+
答34图
:
将非终结符按A,B,C排序,有
已知文法的产生集为:{ A→BaC|CbB,B→AC|c,C→Bb|c} ,试消除G的左递归。
当i=1 j=0,无替换,不存在直接左递归
当i=2,j=1,存在替换,将A的产生式代入到B的产生式右部,得:
B→(BaC|CbB)C|c
即B→|CbBC|c,存在直接左递归,改写如下:
B→CbBC B′|cB′
B′→aCCB′|ε
当i=3,j=1,无替换,不存在直接左递归
当i=3,j=2, 存在替换,将B的产生式代入到C的产生式右部,得:
C→(CbBC B′|cB′)b|c
即C→CbBC B′b|cB′b|c,存在直接左递归,改写如下:
C→cB′bC′|cC′
C′→bBC B′bC′|ε
最后得到消除后左递归的的文法如下:
A→BaC|CbB
B→CbBC B′|cB′
B′→aCCB′|ε
C→cB′bC′|cC′
C′→bBC B′bC′|ε
六、设计分析题。
: FIRSTVT(S)={a,∧,()}
LASTVT(S)={a,∧,()}
FIRSTVT(T)={a,∧,,,()}
LASTVT(T)={a,∧,,,()}
所以可以求得所