编译原理-2015学年期末试卷及答案1.doc

《编译原理-2015学年期末试卷及答案1.doc》由会员分享，可在线阅读，更多相关《编译原理-2015学年期末试卷及答案1.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理2014-2015学年期末试卷及答案1请更改此试卷文件名2014-2015学年第一学期期末考试答案及评分标准编译原理（ A ）卷命题教师：毛静任课教师：毛静 课程代码：22801204适用班级：计本12级 教研室主任审核(签名)：教学主任(签名)：题 号一二三四五总分分 值得 分选择题一、（每小题2分，共20分） 1、下述编译过程，顺序正确的是： 【 C 】A

2、、词法分析，语义分析，语法分析，代码优化，中间代码生成，目标代码生成B、语法分析，词法分析，语义分析，中间代码生成，代码优化目标代码生成C、词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成D、语法分析，词法分析，语义分析，中间代码生成，目标代码生成，代码优化2、编译程序是对： 【 D】A、高级语言程序的执行 B、汇编语言的翻译C、机器语言的执行 D、高级语言的翻译3、词法分析的输入和输出分别是： 【C 】A、汇编指令，目标代码 B、源程序，中间代码C、源程序，记号流 D、源程序，语法树4、正规式M1和M2等价的条件是： 【 C】A、M1和M2的状态数相同 B、M1和M2的有向

3、边相同C、M1和M2所表示的语言集相同D、M1和M2状态数和有向边都相同5、语法分析常用的方法是： 【B】可选项有：(1)自上而下 (2)自左向右 (3)自底向上 (4)自右向左A、（1）（2） B、（1）（3）C、（1）（4） D、（2）（3）6、若b为终结符，则A - B.bC称为： 【 A】A、可移进项目B、可归约项目C、可接受项目D、待约项目7、参数的传递方式主要有： 【 D】可选项：（1）值传递 （2）地址传递 （3）复写恢复 （4）换名调用A、（1）（2） B、（1）（2）（3）C、（2）（3）（4） D、（1）（2）（3）（4）8、下述关于顺序执行的程序的活动树上各节点之间的关系

4、错误的说法是： 【D】A、同一层次的活生存期不交B、任何时刻，处于生存期的活动构成一条从根节点到某节点的路径C、路径上各节点的生存期是嵌套的D、某一时刻只有一个活动处于生存期9、关于寄存器的分配原则，下述说法错误的是： 【B】A、当生成某变量的目标代码时，让变量的值尽可能保存在寄存器中B、当到基本块的结束语句时，将变量的值保存在寄存器中C、当到基本块的结束语句时，将变量的值保存在内存中D、应该将一个基本块内的不常使用的的变量占用的寄存器尽早释放10、作为目标代码生成的基本单位的是： 【B】A、三地址吗B、基本块C、流图 D、中间代码得 分二、填空题（每空1分，共10分）一、1、编译程序是将_高

5、级语言_写的源程序翻译成_目标语言_的程序，这种翻译过程称为编译。2、NFA识别记号的最大特点是它的_不确定性_。3、在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为_最左推导_。4、规定一个名字在什么样的范围内应该表示什么意义的规则，被称为_名字的作用域规则_。5、活动记录中保存了两类信息，一类是_控制信息_，另一类是_访问信息_6、代码生成器以_中间代码_和_符号表信息_为输入，生成可以执行的 目标代码。7、如果有一个正常数或者负常数C，使得每次X被增值C，则变量X被称为_归纳变量。得 分三、判断题（正确的在题号后括号内填写“V”,错误的填写“X”）（每小题2分，共20分）

6、1. 编译程序与具体的机器有关，与具体的语言无关。 （ X ） 2. 词法分析是整个编译过程中唯一和源程序打交道的阶段。 （ V ） 3. 一个文法G被称为LL(1)文法，当且仅当该文法的预测分析表中不含多重定义的条目。 （V ）4. 如果一个句型中出现了某个产生式的右部，则此右部一定是句柄。 （ X ） 5. 继承属性的计算方法是自上而下，包含兄弟，综合属性的计算方式是自下而上，包含自身。 （ V ）6. 程序是动态的，活动室静态的。 （ X ） 7. 对一个变量的赋值是通过环境映射和值映射两步实现的。 （ V ） 8. 一个变量x在其下次引用链范围内总是活跃的。 （ V ） 9. 目标代码

7、生成是编译器中唯一与目标机器特性相关的阶段。 （ V ） 10. 代码优化既可以在程序的局部范围内进行优化，也可以在全局范围内进行优化。 （ V ） 得分四、简答题（第1小题7分，第2小题6分，第3小题7分，共20分）1、（7分）简述词法分析器的作用。答：词法分析器的作用是：1) 滤掉源程序中的无用成分，如注释、空格、回车等（2分）2) 处理与具体平台有关的输入（如文件结束符的不同表示等）（1分）3) 识别记号，并交给语法分析器。根据模式识别记号（2分）4) 调用符号表管理器或出错处理器，进行相关处理（2分） 2、(6分)对于文法G(E):ET|E+TTF|T*FF(E)|i1).写出句型 (

8、T*F+i) 的最右推导并画出分析树（3分）。2).写出上述句型的短语，直接短语、句柄（3分）。答：（1）句型 (T*F+i) 的最右推导：-（2分）ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 分析树如右图所示-（1分）。ETF(E)E+TFiTT*F（2）从分析书中可以看出：短语：(T*F+i), -（1分） T*F+i, -（1分）T*F, -（1分） i直接短语：T*F-（1分）, i-（1分）句柄：T*F-（1分）3、（7分）写出表达式x=（a+b*c）*a-b/2+c的后缀式，三元式序列，四元式序列。答： 后缀式：bc*a+a*b2/-c+x= -（

9、1分）三元式序列： -（3分）(1)(*,b,c)(2)(+,(1),a)(3)(*,(2),a)(4)(/,b,2)(5)(-,(3),(4)(6)(+,(5),c)(7)(=,(6),x)四元式序列： -（3分）(*,b,c,T1)(+,T1,a,T2)(*,T2,a,T3)(/,b,2,T4)(-,T3,T4,T5)(+,T5,c,T6)(=,x,T6,T7)得 分五、论述题（每小题15分，共30分）1、 （15分）设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：（1）构造相应的正规式：(0|1)*1(0|1)

10、-（3分）（2）NFA如下图所示，其中状态0为初始状态，状态4为终态: 1 110432 e e e e 1 0 0 -（3分）（3）确定化：I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1 -（3分）（4）最小化DFA初始划分结果（0,1,2，3,4）Move(0,0)= 1 Move(1,0)=1 Move(2,0)=3第二次划分（0,1，2，3,4）Move(0,1)=2 Move(1,1)=2 所以状态0和状态1不可区分Move(3,0)

11、=1 Move(4,0)=3 状态3和状态4可区分 -（3分）第三次划分（0,1，2，3，4）用1状态代替0,1状态得到最小DFA如下图所示 0 14321 1 0 0 0 1 -(3分)2、（15分）已知文法GE: E ETE |（E）| i T * | +（1） 将文法G改造成LL（1）文法（5分）； （2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合（5分）； （3） 构造LL（1）分析表（5分）。答：（1）文法存在左递归，消除左递归后的文法为：E(E)E | i E -（2分）ETEE | -（2分）T* | + -（1分）（2）FIRST(E)=(，i FIRST( E)=*，+, FIRST(T)=*，+ FOLLOW(E)=)，*，+，# FOWLLOW(E)=)，*，+，# FOLLOW(T)=(，i-（5分）（3）LL(1)分析表如下表所示（表结构1分，每个空005分）：()i*+#EE(E)EEiEEE ETEEE ETEEE E TT*T+ -（3分）-