编译原理A答案.doc

编译原理A答案.doc: .
编译原理试题答案及评分参考（A卷）
（课程代号：9047 ）
一、单项选择题
题号
1
2
3
4
5
6
7
8
9
10
答案
B
C
A
C
D
C
A
D
B
D
题号
11
12
13
14
15
16
17
18
19
20
答案
A
B
B
A
B
D
B
B
D
C
二、多项选则题
题号
21
22
23
24
25
答案
AD
ABC
CDE
ABCDE
ABC
三、填空题
26. 开始符号（识别符号）
27. 圆括号（），方括号口，花括号{}
28. 单词类别 单词的自身值
29. 上下文无关
30. 局部优化 全局优化
四、计算题。
31. 答:
（1） S=> S+S=> S+ S*S =〉S+S*i=〉S+i*i =>i+i*i 或 S=〉S*S=〉S*i =〉S+S*i=〉S+ i*i =>i+ i*i （2 分）
（2）答1：构造两棵语法树如下:
（2分）
（2分）
所以句子i+ i*i有两棵不同的语法树，所以文法具有二义性。
（1分）
答 2：因为 S=〉 S+S=> S+ S*S => S+ S*i=〉 S+ i*i =>i+ i*i
（2分）
或 S=〉 S*S=〉 S*i => S+S*i=〉 S+ i*i =〉i+ i*i （2 分）
所以句子i+ i*i有两个不同的最右推导过程，所以文法具有二义性。（1分）
答 3：因为 S=〉 S+S=> S+ S => i+ S=> i+S*S =〉i+S*i=〉i+ i*i （2 分）
或 S=〉 S*S=〉S+Si*S => i+S*S=〉i+i*S =〉i+ i*i （2 分）
所以句子i+i*i有两个不同的最左推导过程，所以文法具有二义性。（1分）
32. 答：逆波兰式：（abed-*+）
［评分标准］运算符号正确（2分）运算顺序正确（2分）
三元式序列：
(1)
—
C
d
（1分）
(2)
*
b
(1)
（1分）
(3)
+
a
⑵
（1分）
：
FIRSTV
T(E)={+,
*,(),
i} (2 分)
LASTVT(E)= {+, *, (), i} (1 分)
FIRSTVT(T)= {*, (), i} (1 分)
LASTVT(T)= {*, (), i} (1 分)
FIRSTVT(F)= { (), i} (1 分)
LASTVT(F)= {}, i ) (1 分)
:文法G(S):
S T aaSbb | aaCbb
C T ccB | c
［评分标准］文法的四要素齐全(2分)文法书写正确(1分)
文法含义正确，每个产生式各1分
:
（2分）
确定化：
I
a
b
{0, 1,2}
{1,2,3}
{1,2}
{1,2,3}
{1,2,3}
{1,2,4, 5, 6)