编译原理试卷答案

1、 制卷人签名： 制卷日期： 审核人签名： 审核日期： 装 订线 200 11 年 下 学期 级 编译原理 课程考试试卷（A卷） 适用年级专业 2009级计算机科学与技术专业 考试方式 闭卷 考试时间 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：SàS(S)S|e，请判断GS是否是二义文法，说明理

3、由答：是二义文法 理由：选择一个句子，例如（）（），存在有不同的语法树或者不同的最右推导4、请给出布尔表达式a or b and e<f利用规则：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如下: SàAb Aàa | a Aa | aAb | bAa | bAb 属于CFG，即上下文无关文法得分四、有语言 L=w|w (0,1)+，并且 w 中至少有两个1 ，又在任何两个1之间有偶

5、数个 0 ，试构造接受该语言的确定有限状态自动机（10分）答：得分五、请给对文法GS进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。（15分）S S*aA | aA| *aA A +aA | +a 答：改写文法如下： Sà*aAS | aAS Sà*AS | e Aà+aA AàA | eFIRSTFOLLOWS*，a#S*,e#A+*,#A+,e*,#预测分析表：*a+#Sà*aASà aASSà*ASàeAà+aAAàe&

6、#224;Aàe得分六、请构造出文法GS识别文法活前缀的有限自动机，请确定是否是SLR（1）文法，如果是，则构造出其LR分析表。（12分）AaAd |aAb |答：拓广文法（1）SàA （2）AàaAd （3）AàaA （4）AàASà.A I0Aà.aAdAà.aAbAà.SàA. I1dAaAàa.Ad I2Aàa.AbAà.aAdAà.aAbAà.AàaAd. I4AàaA.d I3AàaA.bbaAà

7、;aAb. I5在I0和I2，I3中存在有移进归约冲突但是FOLLOW（A）=d,b,# a Çd,b,#=F,所以文法是SLR（1）文法abd#AI0S2r4r4r41I1accI2S2r4r4r43I3S5S4I4r2r2r2I5r3r3r3得分七、为文法S ® ( L ) | aL ® L , S | S写一个属性翻译文法，它输出文法中a的个数。（10分）SàS printf(S.a)S ® ( L ) S.a=L.aSà a S.a=1L ® 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