北京工业大学 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、预测分析表
x y z
S N SxSNy SNx SNx Nε Nε N zN
三. (20分)符号串xxyyyx是如下文法G[S]的句子，
S xB | yA A xS | yAA | x B yS | xBB | y
(1)构造该句子的分析树；
(2)写出生成该句子的最左推导；
(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。
解: (1)语法分析树 （6分）
S
x
x
B B
B
S
y
A x
y y
(2) SxBxxBBxxyBxxyySxxyyyAxxyyyx (5分) (3) 规范归约 （9分） xxyyyx xxByyx 句柄为 y xxByyx xxByyA 句柄为 x xxByyA xxByS 句柄为 yA xxByS xxBB 句柄为 yS xxBB xB 句柄为 xBB xB S 句柄为 xB
四. （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、 E .E + E E .E * E E .id I7: E 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
I1SIidE5I7I9I0ididid+I=E+E*2I3I4I6I8I7+I8、 I9均有移进—归约冲突， 故该文法不是LR(0)文法。 五. （15分）考虑以下语法制导定义 产生式 语义规则 Print( + * ) S L1 . L2 = 2 * + L L1 B = + 1 L B = = 1 B 0 = 0 B 1 = 1 （1） 写出句子的带注释分析树、或属性计算过程。 （2） 给出处理该句子的结果（Print输出结果）。
解： （1）句子的带注释分析树：
print(3+1*2-2)
S =2*+=3 = +1=2 ==1 =1
L =1
L =2*+=1 = +1=2
. ==0 =1
L B L B
=1
=1
B
1
=0
B
1
1 0
（2）处理该句子的结果（Print输出结果）为
六. （20分）设语言L是“能被5整除的十进制正整数”组成的集合，
（1）试写出描述语言L的正规表达式； （2）画出识别语言L的状态转移图。
解： （1）语言L的正规表达式为： (1|2|……|9)(0|1|……|9)*(0|5)|5 （2）识别语言L的状态转移图为：
50/51-4，6-911-4，6-91-4，6-90/520
编译原理试题与解析-北京工业大学-01
