1、第 1 页 共 4 页 第 2 页 共 4 页班级： 姓名： 考号： 学号： .密封线商丘学院 2011-2012 学年第二学期期末考试计算机科学与技术学院 09 级计算机科学与技术专业本科编译原理试卷（A）题号 一 二 三 四 总分 总分人得分说明：本试卷共四页、四道大题，答卷一律在 试卷规定处填写，答在其它 处不得分。一、单项选择题（本题共 15 小题，每小题 2 分，共 30 分。)题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15答案1、 一个程序，它能够把某一种 “高级语言”转换成另一种 “低级语言” ，而且后者和前者在逻辑上是等价的。此定义是下列各项中哪项
2、的定义A 翻译程序 B 编译程序 C 解释程序 D 目标程序2、 仅含终结符的句型称作A 单词 B 句子 C 语言 D 词组3、 下列哪一项不是优化的原则A 等价原则 B 有效原则 C 合算原则 D 恒等原则4、 在算符优先分析中，用来刻画 “可归约串”的是下列哪个选项A 最左素短语 B 句柄 C 句子 D 句型5、 表达式 a*(-b+c)的逆波兰表示法为下列各项中哪一项A a*(-b+c) B a*b-c+ C a-bc+* D ab-c+*6、 乔姆斯基把文法分成四种类型，其中哪种类型被称为上下文无关文法A 0 型 B 1 型 C 2 型 D 3 型7、 与机器无关的优化，是在源程序或中
3、间语言这一级上进行的工作，不包括A 合并常量 B 消除公共子表达式 C 消减运算强度 D 寄存器的优化8、 对于子程序 A，若直接或间接地调用其自身，则称 A 为A 递归子程序 B 简单子程序 C 嵌套子程序 D 子程序9、 对于文法 GS，其每个非终结符号的不同规则具有不相交的 Select 集，则该文法是A LALR(1)文法 B SLR(1)文法 C LL(1)文法 D LR 文法10、 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组A 句子 B 句型 C 单词 D 产生式11、 在语法分析处理中，FIRST 集合和 FOLLOW
4、集合均是A 非终结符集 B 终结符集 C 字母表 D 状态集12、 自下而上的语法分析方法是从语法树的末端开始，步步向上什么，直到根结点A 推导 B 归约 C 预测 D 回溯13、 DFA 的确定性表现在映射 是一个A 多值函数 B 单值函数 C 多态函数 D 重载函数14、 不属于常见的中间语言形式的是A 状态图 B DAG 图 C 后缀式 D 三地址代码15、 文法 G 所描述的语言是什么的集合A G 的字母表 V 中所有符号组成的符号串B G 的字母表 V 的闭包 V*中的所有符号串C 由 G 的开始符号推出的所有终结符串 D 由 G 的开始符号推出的所有符号串二、判断题（本题共 10
5、小题，每小题 1 分，共 10 分。)题号 1 2 3 4 5 6 7 8 9 10答案1、 循环中的不变运算一定可以外提。 2、 综合属性用于自下而上传递信息。3、 文法是用无限的手段刻画有限的句子集合的方法之一。4、 静态分配是指目标程序运行时的进行的分配。5、 自下而上语法分析方法的主要问题是候选式的选择。6、 简单优先文法允许任意两个产生式具有相同右部。7、 算符优先关系表不一定存在对应的优先函数。8、 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。得分 评卷人得分 评卷人第 3 页 共 4 页 09 级计算机科学与技术专业本科编译原理试卷 第 4 页 共 4 页*密封
6、线9、 语法制导翻译法就是由源程序的语法结构所驱动的处理办法。10、 状态转换图是一张有限方向图。三、填空题（本题共 10 空，每空 2 分，共 20 分。)1、 编译程序与解释程序的区别在于是否产生_。2、 文法 G 所产生的句子的全体是 _，将它记为 L(G)。3、 上下文无关文法中文法符号的属性通常分为两类：_和_。4、 优化的目的是为了_。5、 句型的最左简单短语称为该句型的 。6、 编译程序一般可以划分为 、 、 、中间代码生成、 和目标代码生成 6 个阶段。四、综合题（本题共 5 小题，40 分。)1、已知文法 G1 为 ND|ND D0|1|2|3|4|5|6|7|8|9给出句子 2012 的最左推导和最右推导。 （4 分）2、构造正规式 1（0|1） *101 相应的 DFA。只画状态转换图即可。 (10 分)3、对下面的文法 G：ETE E +E| TFT T T| FPFF *F| P(E)|a|b|（1）证明这个文法是 LL(1)文法。 （5 分）（2）构造它的预测分析表。 （5 分）4、文法： EE+T|T TT*F|F F(E)|i给出此文法的一个句型 E+T*F+i 的所有短语，直接短语和句柄。 （6 分)5、文法：EE+T|T TT*F|F F(E)|i构造该文法的 SLR(1)分析表。只画分析表即可。 （10 分）得分 评卷人得分 评卷人
