编译原理试卷(答案).doc

说明： 本试卷将作为样卷直接制版胶印，请命题教师在试题之间留足答题空间。 （第 PAGE 1 页 共 NUMPAGES 4 页） 制卷人签名： 制卷日期： 审核人签名：： 制卷人签名： 制卷日期： 审核人签名：： 审核日期： ………………………………………………………………………………………………………………………………………………………………………………… ……………………………………………………………装…………………… 订……………………线………………………………………………………………… 《 编译原理 》课程考试试卷 （A卷） 适用年级专业 2009级计算机科学与技术专业 考试方式 闭卷 考试时间 120 分钟 学院 信息工程学院 专业 计算机科学与技术 班级 学号 姓名 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师 得 分 ……………………………………………………………………………………………………………… 得 分 一、填空题（每小题2 分，共12分） 1、一般高级语言的翻译程序有（ 编译程序 ）和（ 解释程序 ）两种。 2、有穷自动机接受的语言是（ 正规语言 ） 3、令Σ＝{a,b}，则Σ上所有以b为首的字符串构成的正规集的正规式为（ b(a|b)* ）。 4、下面的语义规则是某L属性文法中的一个语义规则，从中可看出：A.s是（ 综合 ）属性，B.x是( 继承 )属性。 A--BCD {A.s=B.x+C.y;D.z=B.i;} 5、活前缀是指（ 规范句型 ） 的一个前缀，这种前缀不含（ 句柄 ） 之后的任何符号。 6、局部优化是在（ 一个基本块 ）范围内进行的一种优化。 得 分 二、简答题（每小题5分，共计20分） 请说明什么是算符优先文法？ 答：（1）在CFG中无空产生式，且右部无相邻的非终极符 （2）任意两个相邻的终极符间至多只存在一种关系 哪些优化措施是主要针对于循环实现的？可举例说明 答：代码外提 强度削弱 归纳变量删除 文法G[S]：S?S(S)S|?，请判断G[S]是否是二义文法，说明理由 答：是二义文法 理由：选择一个句子，例如（）（），存在有不同的语法树或者不同的最右推导 4、请给出布尔表达式a or b and ef利用规则： E ? id1 rop id2 {E.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 在翻译过程中，常常会出现若干转移四元式转向同一目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填这个链。 得 分 三、构造一文法，其产生语言集合为{ uawb | u,w ∈{a, b}* 且| u | = | w | }，并说明你所设计的文法是属于乔姆斯基形式文法中的哪一类文法？（10分） 答：设计G[S]如下: S?Ab A?a | a Aa | aAb | bAa | bAb 属于CFG，即上下文无关文法 得 分 四、有语言 L={w|w ∈ (0,1)+，并且 w 中至少有两个1 ，又在任何两个1之间有偶数个 0 }，试构造接受该语言的确定有限状态自动机（10分） ５２ ５ ２ ０答： ０ ０１０００ ０１ ０ ０ ０ １１１４３ １ １ １ ４ ３ １ １ 得 分 五、请给对文法G[S]进行改写成LL（1）文法，并给出改写后文法的预测分