编译原理-北工大-04年试卷(共5页)

1、精选优质文档-倾情为你奉上北京工业大学 2003-04-2学期 -11 班级编译原理 试卷（A卷）学号_ 姓名 _ 成绩 _题号一二三四五六分数一. （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

2、 X® aYX| Y ® bZ Z ® YcX|二. (15分)考虑文法GS：S ® xSNy| NxN ® zN|1. 求出该文法的每个非终结符的FOLLOW集；2. 构造该文法的预测分析表。 解:1、FIRST(S) = x, z FIRST(N) = z, FOLLOW(S) = #, y, z FOLLOW(N) = x, y 2、预测分析表N® N® N ® zNx y z #SNS®xSNy S®Nx S®Nx三. (20分)符号串xxyyyx是如下文法GS的句子， S &

3、#174; xB | yAA ® xS | yAA | xB ® yS | xBB | y(1)构造该句子的分析树；(2)写出生成该句子的最左推导；(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。解:(1)语法分析树 （6分）SxBxBByySyAx(2) SÞxBÞxxBBÞxxyBÞxxyySÞxxyyyAÞxxyyyx (5分)(3) 规范归约 （9分）xxyyyx Þ xxByyx 句柄为 yxxByyx Þ xxByyA 句柄为 xxxByyA Þ xxByS 句柄

4、为 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 ®

5、; .E + EE ® .E * EE ® .idI4: S ® 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 ®

6、; 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 = L1.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整除的十进制正整数