《编译原理试卷(答案)》由会员分享，可在线阅读，更多相关《编译原理试卷(答案)（5页珍藏版）》请在金锄头文库上搜索。
1、 制卷人签名： 制卷日期： 审核人签名： 审核日期： 装 订线 200 9 年 下 学期2007级 编译原理 课程考试试卷（A卷） 适用年级专业 2007级计算机科学与技术专业 考试方式 闭卷 考试时间 120 分钟学院 信息工程学院 专业 计算机科学与技术 班级 学号 姓名 题号一二三四五六七八总分阅卷教师得分得分一、填空题（每小题2 分，共12分）1、一般高级语言的翻译程序有（ 编译程序 ）和（ 解释程序 ）两种。2、有穷自动机接受的语言是（ 正规语言 ）3、令a,b，则上所有以b为首的字符串构成的正规集的正规式为（ b(a|b)* ）。4、下面的语义规则是某L属性文法中的一个语义规则，从
2、中可看出：A.s是（ 综合 ）属性，B.x是( 继承 )属性。 A-BCD A.s=B.x+C.y;D.z=B.i;5、活前缀是指（ 规范句型 ） 的一个前缀，这种前缀不含（ 句柄 ） 之后的任何符号。6、局部优化是在（ 一个基本块 ）范围内进行的一种优化。得分二、简答题（每小题5分，共计20分）1、 请说明什么是算符优先文法？答：（1）在CFG中无空产生式，且右部无相邻的非终极符（2）任意两个相邻的终极符间至多只存在一种关系2、 哪些优化措施是主要针对于循环实现的？可举例说明答：代码外提 强度削弱 归纳变量删除3、 文法GS：SS(S)S|e，请判断GS是否是二义文法，说明理由答：是二义文法
3、 理由：选择一个句子，例如（）（），存在有不同的语法树或者不同的最右推导4、请给出布尔表达式a or b and ef利用规则：E id1 rop id2E.TC = NXQ; E.FC = NXQ + 1; Gen(jrop,Entry(id1), Entry(id2), 0); Gen(j, _, _, 0) 进行翻译后的四元式序列？并以此解释什么是链接与回填？答：(1)(jn,a,-,0)(2)(j,-,-,3) 回填(3)(jn,b,-,5) 回填(4)(j,-,-,0)(5)(,e,f,1) E.TC 链接(6)(j,-,-,4)E.FC在翻译过程中，常常会出现若干转移四元式转向同一
4、目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填这个链。得分三、构造一文法，其产生语言集合为 uawb | u,w a, b* 且| u | = | w | ，并说明你所设计的文法是属于乔姆斯基形式文法中的哪一类文法？（10分）答：设计GS如下: SAb Aa | a Aa | aAb | bAa | bAb 属于CFG，即上下文无关文法得分四、有语言 L=w|w (0,1)+，并且 w 中至少有两个1 ，又在任何两个1之间有偶数个 0 ，试构造接受该语言的确定有限状态自动机（10分）答：得分五、
5、请给对文法GS进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。（15分）S S*aA | aA| *aA A +aA | +a 答：改写文法如下： S*aAS | aAS S*AS | e A+aA AA | eFIRSTFOLLOWS*，a#S*,e#A+*,#A+,e*,#预测分析表：*a+#S*aAS aASS*ASeA+aAAeAe得分六、请构造出文法GS识别文法活前缀的有限自动机，请确定是否是SLR（1）文法，如果是，则构造出其LR分析表。（12分）AaAd |aAb |答：拓广文法（1）SA （2）AaAd （3
6、）AaA （4）AAS.A I0A.aAdA.aAbA.SA. I1dAaAa.Ad I2Aa.AbA.aAdA.aAbA.AaAd. I4AaA.d I3AaA.bbaAaAb. I5在I0和I2，I3中存在有移进归约冲突但是FOLLOW（A）=d,b,# a d,b,#=F,所以文法是SLR（1）文法abd#AI0S2r4r4r41I1accI2S2r4r4r43I3S5S4I4r2r2r2I5r3r3r3得分七、为文法S ( L ) | aL L , S | S写一个属性翻译文法，它输出文法中a的个数。（10分）SS printf(S.a)S ( L ) S.a=L.aS a S.a=1
7、L L , S L.a=L1.a+S.aL S L.a=S.a得分八、考虑下面的三地址语句序列，完成下列任务。（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。（2分）（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（3分）（3）若有循环的话，列出构成每个循环的结点,并指出循环的入口结点。（6分）解：（1） （2）124736b := 1b := 2if w = x goto L3（1）5L1:e := bgoto L3（2）L2:c := 3b := 4c := 6 （3）L3:if y = z goto L4（4）goto L5（5）L4:g := g + 1h := 8goto L1（6）L5:h := 9（7） goto L2（3）回边34，结点5、7、3和4构成一个循环，其中4是入口结点。
