上海大学编译原理试卷秋B.doc

一、选择题（本题共22分，每小题2分）将一个或多个正确答案的编号填入每题题干中的横线上。错选、多选、少选均不得分。

1. 词法分析阶段的任务是__ B__ _.
A. 识别表达式 B. 识别单词 C. 识别语句 D. 识别程序

2. 设A是字母表，则A* = __BCD __ _.
A. A1∪A2∪…∪An∪… B. A0∪A1∪A2∪…∪An∪…
C. {ε}∪A+ D. A0∪A+

3. 设文法G[A]的规则为：A→A1 | A0 | Aa | Ac | a | b | c, 则下列符号串__ BCD__是该文法的句子.
A. ab0 B. a0c01 C. aaa D. bc10

4..如果在推导过程中的任何一步α Þ β都是对α中的最右非终结符进行替换，则称这种推导为
__ BD__ _.
A. 直接推导 B. 最右推导 C. 最左推导 D. 规范推导

5. 程序设计语言的单词符号一般可分为5种，它们是 ACD _ _及运算符和界符.
A. 常数 B. 表达式 C. 基本字 D. 标识符

6. 正规式(a | b)(a | b | 0 | 1 )*对应的文法为 C _ _.
A. S → aA | bA B. S → aA | bA
A → 0A | 1A | ε A → aA | bA | 0A | 1A
C. S → aA | bA D. S → A
A → aA | bA | 0A | 1A | ε A → A | bA |0A | 1A | ε
7. 通常程序设计语言的单词符号都能用 AC _ _描述.
A. 正规文法 B. 上下文无关文法 C. 正规式 D. 上下文有关文法

8. 如果文法G中没有形如A → …BC…的规则，其中A,B,C是非终结符，则文法G是 D _ _.
A. 算法优先文法 B. LL(1)文法 C. LR(0)文法 D. 算法文法

9. 文法G[E]:
E → E + T | T
T → T * F | F
F → (E) | a
则句型T + T * F + a 的素短语是 AB _.
A. a B. T * F C. T D. T + T * F

10. LR(0)分析器的核心部分是一张分析表，它包括两部分，分别是 BC _ _.
A. LL(1)分析表 B. 分析动作表 C. 状态转换表 D. 移进分析表

11. LR(0)项目集规范族的项目类型可分为 ABCD _ _.
A. 移进项目 B. 归约项目 C. 待约项目 D. 接受项目
二、是非判断题（本题共10分，每小题1分）
正确的在题后的括号内填T，错误的填F

1. 在形式语言中，最右推导的逆过程也称为规范过程。 （ T ）
2. 每个直接短语都是某规则的右部。 （ T ）
3. 任何正规文法都是上下文无关文法。 （ T ）
4. 一张状态转换图包含有限个状态，其中一个被认为是初态，最多有一个终态。 （ F ）
5. 无左递归的文法是LL(1)文法。 （ F ）
6. LR分析法是一种规范归约分析法。 （ T ）
7. 文法符号的属性有两种，即继承属性和综合属性。 （ T ）
8. 紧跟在条件转移语句后的语句是基本块的入口语句。 （ T ）
9. PL0程序具有分程序结构、过程可嵌套且支持递归调用。 （ T ）
10. 符号表可以辅助上下文语义正确性检查。 （ T ）
三、（本题满分10分）
为正规式构造一个确定的有穷自动机DFA。

（1）构造NFA如图2.1所示：（4分）

（2）NFA确定化为DFA的过程如下表所示：（4分）

表2：NFA确定为DFA的过程（并换名）
I
Ia
Ib
① [S, A, B]
② [A, B, C]
③ [A, B]
② [A, B, C]
④ [A, B, C, Z]
⑤ [A, B, Z]
③ [A, B]
② [A, B, C]
③ [A, B]
④ [A, B, C, Z]
④ [A, B, C, Z]
⑤ [A, B, Z]
⑤ [A, B, Z]
② [A, B, C]
③ [A, B]

（3）相应的DFA状态土如图2.2所示：（2分）

四、（本题满分18分）
对文法G[S]
S → (L) | a
L → L, S | S
（1） 给出句子(a, ((a, a), (a, a)))的一个最右推导（4分）；
（2） 对文法G，消除左递归，使之成为LL(1)文法，并加以验证（6分）。
（3） 构造这个LL(1)文法的预测分析表（4分）。
（4） 用预测分析器给出输入串(a,(a,a))＃的分析过程，并说明该串是否是G的句子（4分）。

【解答】
（1） 最右推导为：（4分）

（2） 将所给文法消除左递归得G’： （6分）

① 求出能推出ε的非终结符

S
L
L′

否
否
是

② 求First集
FIRST(S) = { ( , a}
FIRST(L) = { ( , a }
FIRST(L′) = { , , ε}

③ 求Follow集
FOLLOW(S) = {FIRST(L′) –{ε}}∪FOLLOW(L)
FOLLOW(L) = {)}
FOLLOW(L′) = FOLLOW(L)
所以有，
FOLLOW(S) = = {＃, , )}
FOLLOW(L) = {)}
FOLLOW(L′) = {)}

④ 求Select集
Select(S→(L)) = {(}
Select(S→a) = {a}
Select(S→(L))∩Select(S→a) = Æ
Select(L→S L′) = {( , a }
Select(L′→,S L′) = {,}
Select(L′→ ε) = FOLLOW(L′) = {)}
Select(L′→,S L′)∩Select(L′→ ε) = Æ
所以，该文法是LL(1)文法。

（3） 构造预测分析表’： （4分）

a
(
)
,
#
S
→a
→(L)

L
→S L′
→S L′

L′

→ε
→,S L′

（4） 对符号串(a,(a,a))＃的分析过程如下：（4分）
步骤
分析栈
剩余输入串
所用产生式
1
#S
(a,(a,a))＃
S→(L)
2
#)L(
(a,(a,a))＃
匹配
3
#)L
a,(a,a))＃
L→S
4
#)S
a,(a,a))＃
S→a
5
#)a
a,(a,a))＃
匹配
6
#)
,(a,a))＃
→,S
7
#)S,
,(a,a))＃
匹配
8
#)S
(a,a))＃
S→(L)
9
#))L(
(a,a))＃
匹配
10
#))L
a,a))＃
L→S
11
#))S
a,a))＃
S→a
12
#))a
a,a))＃
匹配
13
#))
,a))＃
→,S
14
#))S,
,a))＃
匹配
15
#))S
a))＃
S→a
16
#))a
a))＃
匹配
17
#))
))＃
→
18
#))
))＃
匹配
19
#)
)＃
→
20
#)
)＃
匹配
21
#
#
接受

所以符号串(a,(a,a))＃是该文法的句子。
五、（本题满分15分）
证明下面文法不是LR(0)文法，但是SLR(1)文法。
S → A
A → Ab | bBa
B → aAc | a | aAb
【解答】
该文发的拓广文法如下： （8分）
(0) S´→ S
(1) S → A
(2) A → Ab
(3) A → bBa
(4) B → aAc
(5) B → a
(6) B → aAb

构造识别该文法活前缀的有限自动机DFA：

3分）
I2，I6存在移进-归约冲突。
I10存在归约-归约冲突。
∴ 该文法不是LR(0)文法。

（4分）
对于状态I2：
FOLLOW(S) = {#}。FOLLOW(S)∩{b} = Æ，所以此状态的冲突可以通过SLR(1)方法消除。
对于状态I6：
FOLLOW(B) = {a}。FOLLOW(B)∩{b} = Æ，所以此状态的冲突也可以通过SLR(1)方法消除。
对于状态I10：
FOLLOW(B) = {a}。FOLLOW(A) = {b,c,#}。FOLLOW(A)∩FOLLOW(B) = Æ，所以此状态的冲突也可以通过SLR(1)方法消除。
∴ 该文法是SLR(1)文法。

六、（本题满分15分）

已知文法G[S]为：
S → a | Ù | (T)
T → T, S | S
(1) 计算G[S]的FIRSTVT，LASTVT.
(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。
【解答】
(1) （5分）
将文法改写成:
S′→ #S#
S → a |Ù | (T)
S → T, S | S

用简单关系图方法求非终结符号的FIRSTVT，LASTVT如下：
FIRSTVT(S′) = {# }
FIRSTVT(S) = {a, Ù, (}
FIRSTVT(T) = { a, Ù, (, , }

LASTVT(S′) = {# }
LASTVT(S) = {a, Ù, )}
LASTVT(T) = { a, Ù, ), , }
(2) （8分）

算符优先关系表

a
Ù
(
)
,
#
a

·>
·>
·>
Ù

·>
·>
·>
(
<·
<·
<·
=·
<·

)

·>
·>
·>
,
<·
<·
<·
·>
·>

#
<·
<·
<·

=·

因为该文法的任意两个终结符之间最多只有一种优先关系，所以该文法是算符优先文法（2分）。
七、（本题满分10分）

将下面语句翻译成四元式序列（假设四元式起始标号为100）。
While A or B<D do if (x<6) then x := x-1 else y := x+1

【解答】(10分）
100 if A goto 104
101 goto 102
102 if B<D goto 104
103 goto 112
104 if x>6 goto 106
105 goto 109
106 t := x-1
107 x := t
108 goto 100
109 t := x+1
110 y := t
111 goto 100
112