编译原理试题与解析-北京工业大学-01
- 格式：doc
- 大小：304.00 KB
- 文档页数：7
北京工业大学 2003-04-2学期 010700-11 班级
《编译原理》 试卷
学号_______________ 姓名 ________________ 成绩 ___________
题号 一 二 三 四 五 六
分数
一. （10分）改写以下文法，使其满足采用自顶向下分析方法的要求。
S aXcY| Yd
X XaY| c
Y bYcX| b
解:
(1)消除 X XaY|c 的左递归
X cX’
X’ aYX’| ε
(2)提取 Y bYcX|b 的左因子
Y bY’
Y’ YcX|ε
整理后，原文法变为
S aXcY | Yd
X cX’
X’ aYX’|ε
Y bZ
Z YcX|ε
二. (15分)考虑文法G[S]：
S xSNy| Nx
N zN|ε
1. 求出该文法的每个非终结符的FOLLOW集；
2. 构造该文法的预测分析表。
解:
1、
FIRST(S) = { x, z }
FIRST(N) = { z, ε }
FOLLOW(S) = { #, y, z }
FOLLOW(N) = { x, y }
2、预测分析表
三. (20分)符号串xxyyyx是如下文法G[S]的句子，
S xB | yA
A xS | yAA | x
B yS | xBB | y
(1)构造该句子的分析树；
(2)写出生成该句子的最左推导；
(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。
x y z #
S N SxSNy SNx SNx
Nε Nε N zN
解:
(1)语法分析树 （6分）
(2) SxBxxBBxxyBxxyySxxyyyAxxyyyx (5分)
(3) 规范归约 （9分）
xxyyyx xxByyx 句柄为 y
xxByyx xxByyA 句柄为 x
xxByyA xxByS 句柄为 yA
xxByS xxBB 句柄为 yS
xxBB xB 句柄为 xBB
xB S 句柄为 xB
S
x B
x B B
y
y
S
y
A
x
四. （20分）考虑简单赋值语句的文法G[S]：
S id:= E
E E + E
E E * E
E id
（1） 试构造识别该文法所有规范句型活前缀的有限自动机。
（2） 判断该文法是否为LR(0)文法（必须说明理由）。
解:
(1)
I0: S’ .S
S .id = E
I1: S’ S.
I2: S id. = E
I3: S id = .E
E .E + E
E .E * E
E .id
I4: S id = E.
E E. + E
E E. * E
I5: E id.
I6: E E + .E （2）由于I4、 I8、 I9均有移进—归约冲突，
E .E + E
E .E * E 故该文法不是LR(0)文法。
E .id
I7: E E * E
I
0
I
1
I2I3I4I7I6I
8
I9I7I
5
S
id
ididE
+
id
=E+E
*
+
E .E + E
E .E * E
E .id
I8: E E + E
E E.+ E
E E. * E
I9: E E * E.
E E .+ E
E E .* E
五. （15分）考虑以下语法制导定义
产生式 语义规则
S L1 . L2
Print( + * )
L L1 B
= 2 * +
= + 1
L B =
= 1
B 0 = 0
B 1 = 1
（1） 写出句子的带注释分析树、或属性计算过程。
（2） 给出处理该句子的结果（Print输出结果）。
解：
（1）句子的带注释分析树：
（2）处理该句子的结果（Print输出结果）为
S
L
L
.
L B B L B
1
0 B 1 1
print(3+1*2-2)
=2*+=3 ==1 =1 =1 ==0 =2*+=1
=0
=1
六. （20分）设语言L是“能被5整除的十进制正整数”组成的集合，
（1）试写出描述语言L的正规表达式；
（2）画出识别语言L的状态转移图。
解：
（1）语言L的正规表达式为：
(1|2|……|9)(0|1|……|9)*(0|5)|5
（2）识别语言L的状态转移图为：
012
5
0/5
1-4，6-9
1-4，6-9
0/5
1-4，6-9
