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

1、北京工业大学2003-04-2学期010700-11班级编译原理试卷学号 姓名 成绩题号 一四五7分数（10分）改写以下文法，使其满足采用自顶向下分析方法的要 求。S ? aXcYl YdX ? XaY| cY ? bYcX| b解：（1）消除X ? XaY|c的左递归X?cX * X' ? aYX' | &（2）提取Y ? bYcX|b的左因子Y ?bY 1Y' ? YcX| &整理后，原文法变为S ? aXcY | Yd X ? cX 'X1 ? aYX' |&Y ?bZZ ? YcX| £二.（15分）考虑文法GS

2、：S ? xSNy| NxN ?zN|&1 .求出该文法的每个非终结符的FOLLOW集;2 ,构造该文法的预测分析表。解：FIRST(S) = x, z FIRST(N) = z, & FOLLOW(S) = #, y, z FOLLOW(N) = x, y2预测分析表S?NxS?xSNy S?NxN?S N ? zN(20分)符号串xxyyyx是如下文法GS的句子，S ? xB | yAA ?xS|yAA|xB ?yS|xBB | y(1)构造该句子的分析树；(2)写出生成该句子的最左推导；(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。解：(1)语法分析树(6分)

3、XX句柄为y 句柄为x 句柄为yA 句柄为ys 句柄为xBB 句柄为xB（2） S ?xB?xxBB?xxyB?xxyyS?xxyyyA?xxyyyx （5 分）规范归约（9分）xxyyyx ? xxByyx xxByyx ? xxByyA xxByyA ? xxByS xxByS ? xxBB xxBB ?xB xB ?S四,(20分)考虑简单赋值语句的文法GS：S?id:=E E?E + E E?E*E E?id(1)试构造识别该文法所有规范句型活前缀的有限自动机(2) 判断该文法是否为LR(O)文法(必须说明理由)。解：(1)Io： S 1 ?.S+S ? .id = E L： S &#

4、39; ?S. 12： S?id. = E 13： S ? id = .EE?.E + E E?.E*E E?.id14： S ? id = E.E?E. + EE?E. *E I5： E ? id.16： E ? E +.E (2)由于14、I 8、I 9均有移进一归约冲突，E?.E + EE ?.E E故该文法不是LR(O)文法VE?.id17： E?E*EE?.E + EE?.E*EE?.id1s： E ? E + EE?E.+ EE ? E. * E19： E?E*E.E ? E .+ EE?E.*E产生式语义规则S ? Li. L 2Print( + *)L?LiB=2* +=+ 1L?B=1B ?0=0B ? 1=1（1 ）写出句子的带注释分析树、或属性计算过程 （2）给出处理该句子的结果（Print输出结果）解：（1）句子的带注释分析树:（2）处理该句子的结果（Print输出结果）为六.(20分)设语言L是“能被5整除的十进制正整数”组成的集合, (1)试写出描述语言L的正规表达式；(2