编译原理试题与解析北京工业大学

1、北京工业大学 2003-04-2学期 010700-11 班级编译原理 试卷学号_ 姓名 _ 成绩 _题号一二三四五六分数一. （10分）改写以下文法，使其满足采用自顶向下分析方法的要求。S aXcY| YdX 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分)考虑文法GS：S xSNy| NxN zN|1. 求出该文法的每个非终结符的FOLLOW集；2. 构造该文法的预测分析表

2、。 解:1、FIRST(S) = x, z FIRST(N) = z, FOLLOW(S) = #, y, z FOLLOW(N) = x, y 2、预测分析表N N N zNx y z #SNSxSNy SNx SNx三. (20分)符号串xxyyyx是如下文法GS的句子， S xB | yAA xS | yAA | xB yS | xBB | y(1)构造该句子的分析树；(2)写出生成该句子的最左推导；(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。解:(1)语法分析树 （6分）SxBxBByySyAx(2) SxBxxBBxxyBxxyySxxyyyAxxyyyx (5分)(3

3、) 规范归约 （9分）xxyyyx xxByyx 句柄为 yxxByyx xxByyA 句柄为 xxxByyA xxByS 句柄为 yAxxByS xxBB 句柄为 ySxxBB xB 句柄为 xBBxB S 句柄为 xB四. （20分）考虑简单赋值语句的文法GS： S id:= E E E + EE E * EE id（1） 试构造识别该文法所有规范句型活前缀的有限自动机。（2） 判断该文法是否为LR(0)文法（必须说明理由）。解:(1)I0: S .SS .id = EI1: S S.I2: S id. = EI3: S id = .EE .E + EE .E * EE .idI4: S

4、id = E.E E. + EE E. * EI5: E id.I6: E E + .E（2）由于I4、 I8、 I9均有移进归约冲突，E .E + EE .E * E 故该文法不是LR(0)文法。E .idI7: E E * EE .E + EE .E * EE .idI8: E E + EE E.+ EE E. * EI9: E E * E.E E .+ EE E .* E五. （15分）考虑以下语法制导定义产生式语义规则S L1 . L2Print( L1.val + L2.val * 2-L2.num )L L1 BL.val = 2 * L1.val + B.valL.num = L

5、1.num + 1L BL.val = B.valL.num = 1B 0B.val = 0B 1B.val = 1（1） 写出句子11.01的带注释分析树、或属性计算过程。（2） 给出处理该句子的结果（Print输出结果）。解：（1）句子11.01的带注释分析树：S LL.LBBLB10B11print(3+1*2-2)L.val=2*L.val+B.val=3L.num=L.num +1=2L.val=B.val=1L.num=1B.val=1B.val=1L.val=B.val=0L.num=1L.val=2*L.val+B.val=1L.num=L.num +1=2B.val=0B.val=1（2）处理该句子的结果（Print输出结果）为3.25六. （20分）设语言L是“能被5整除的十进制正整数”组成的集合， （1）试写出描述语言