13-14学年第2学期期末考试《编译原理》B概要.doc

聊城大学计算机学院1—14学年第2学期期末考试《编译原理》试题（闭卷B卷） 题号 一 二 三 四 五 总分 复核人 得分 一、填空题（共10题，每空1分，共15分） 得分 阅卷人 1、语法分析是依据语言的 规则进行的，中间代码产生是依据语言的 紧密联系的。 2、规范归约是 推导的逆过程。 3、表达式a+b/5*(e+f)*3的逆波兰式为 。 4、自顶向下语法分析会遇到的主要问题有 和 。 5、对于文法G，仅含终结符号的句型称为 。 6、LL(K)文法中，第一个L表示 ，第二个L表示 ，K表示 。 7、若两个正规式所表示的 相同，则认为二者是等价的。 8、设有文法G[S]=({b}，{S，B}，S， {S →b|bB，B→bS})，该文法所描述的语言是 。 9、活前缀是指 的一个前缀，这种前缀不包含 之后的任何符号。 10、同心集合并后不会产生移进－归约冲突，但可能产生 冲突。 二、选择题（共10题，每题2分，共20分） 得分 阅卷人 题号 1 2 3 4 5 6 7 8 9 10 答案 设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 个直接短语。 A．1 B． 2 C．3 D．4 如果一个文法满足 ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一 上述描述中的所有正确描述有： A． (1) B． (1)(2) C． (1)(2)(3) D．(1)(2)(3)(4) 算符优先分析法每次都是对 进行归约。 A． 最左短语 B． 句柄 C．素短语 D．最左素短语 若为非终结符，则A→α·β为 项目。 A． 归约 B． 待约 C． 接受 D．移进 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 。 A．单词 B．字符 C．句子 D．句型 文法G[S]：S→b|∧|(T) T→T,S|S 则FIRSTVT(T)= 。 A．{b, ∧,(} B．{b, ∧, )} C． {b, ∧,(, ，} D．{b, ∧, ), ，} 文法G:S→xSx|y所识别的语言是 。 A．xyx B．（xyx）* C．x*yx* D． xnyxn 有限状态自动机能识别 。 A．上下文无关文法 B．上下文有关文法 C． 正规文法 D．短语文法 若项目集IK含有A→α·，则在状态K时，无论面临什么输入符号都采取“A→α·归约”动作的一定是 。 A．LR(0)文法 B．SLR(1)文法 C． LALR(1)文法 D． LR(1)文法 下列 中间代码形式有益于优化处理。 A．三元式 B．四元式 C．逆波兰式 D．树形表示法 三、判断题（共5题，每题1分，共5分） 得分 阅卷人 题号 1 2 3 4 5 答案 1、设r和s分别是正规式，则有L(r|s)=L(r)L(s)。2、3、。4、5、四、简答题（共5题，共35分） 得分 阅卷人 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？已知文法G(S)S→a|∧|(T) 　　T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。 (6分)一个非LR(1)的文法如下： L→MLb|a M→ε 请给出所有移近－归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。 　　 (8分)将a:＝if x0 then x+1 else x＋2 翻译为四元式序列。 五、综合题（共2题，共25