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

第1页，共8页第2页，共8页………○…………○………装…………○…………订…………○…………线…………○…………-院系：专业班级：学号：姓名：座位号：-2014-2015学年第一学期期末考试答案及评分标准《编译原理》（A）卷题号一二三四五总分分值得分一、选择题（每小题2分，共20分）1、下述编译过程，顺序正确的是：【C】A、词法分析，语义分析，语法分析，代码优化，中间代码生成，目标代码生成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的有向边相同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、下述关于顺序执行的程序的活动树上各节点之间的关系错误的说法是：【D】A、同一层次的活生存期不交B、任何时刻，处于生存期的活动构成一条从根节点到某节点的路径C、路径上各节点的生存期是嵌套的D、某一时刻只有一个活动处于生存期9、关于寄存器的分配原则，下述说法错误的是：【B】A、当生成某变量的目标代码时，让变量的值尽可能保存在寄存器中B、当到基本块的结束语句时，将变量的值保存在寄存器中C、当到基本块的结束语句时，将变量的值保存在内存中D、应该将一个基本块内的不常使用的的变量占用的寄存器尽早释放10、作为目标代码生成的基本单位的是：【B】A、三地址吗B、基本块C、流图D、中间代码教研室主任审核(签名)：教学主任(签名)：课程代码：22801204适用班级：计本12级命题教师：毛静任课教师：毛静第3页，共8页第4页，共8页装订线内不许答题1、编译程序是将_____高级语言________写的源程序翻译成______目标语言_____的程序，这种翻译过程称为编译。2、NFA识别记号的最大特点是它的____不确定性____________。3、在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为_________最左推导___。4、规定一个名字在什么样的范围内应该表示什么意义的规则，被称为_名字的作用域规则___。5、活动记录中保存了两类信息，一类是__控制信息____，另一类是__访问信息________6、代码生成器以____中间代码___和______符号表信息___为输入，生成可以执行的目标代码。7、如果有一个正常数或者负常数C，使得每次X被增值C，则变量X被称为_归纳变量。。1.编译程序与具体的机器有关，与具体的语言无关。（X）2.词法分析是整个编译过程中唯一和源程序打交道的阶段。（V）3.一个文法G被称为LL(1)文法，当且仅当该文法的预测分析表中不含多重定义的条目。（V）4.如果一个句型中出现了某个产生式的右部，则此右部一定是句柄。（X）5.继承属性的计算方法是自上而下，包含兄弟，综合属性的计算方式是自下而上，包含自身。（V）6.程序是动态的，活动室静态的。（X）7.对一个变量的赋值是通过环境映射和值映射两步实现的。（V）8.一个变量x在其下次引用链范围内总是活跃的。（V）9.目标代码生成是编译器中唯一与目标机器特性相关的阶段。（V）10.代码优化既可以在程序的局部范围内进行优化，也可以在全局范围内进行优化。（V）得分四、简答题（第1小题7分，第2小题6分，第3小题7分，共20分）1、（7分）简述词法分析器的作用。答：词法分析器的作用是：1)滤掉源程序中的无用成分，如注释、空格、回车等（2分）2)处理与具体平台有关的输入（如文件结束符的不同表示等）（1分）3)识别记号，并交给语法分析器。根据模式识别记号（2分）4)调用符号表管理器或出错处理器，进行相关处理（2分）2、(6分)对于文法G(E):ET|E+TTF|T*FF(E)|i1).写出句型(T*F+i)的最右推导并画出分析树（3分）。2).写出上述句型的短语，直接短语、句柄（3分）。答：（1）句型(T*F+i)的最右推导：-------------------------------（2分）ETF(E)(E+T)(E+F)(E+i)(T+i)(T*F+i)分析树如右图所示----------------------------------------（1分）。（2）从分析书中可以看出：短语：(T*F+i),-------------------------------（1分）T*F+i,-------------------------------（1分）T*F,------------------------------------（1分）i直接短语：T*F-------------------------------（1分）,i--------------------------------（1分）句柄：T*F-------------------------------------（1分）得分三、判断题（正确的在题号后括号内填写“V”,错误的填写“X”）（每小题2分，共20分）得分二、填空题（每空1分，共10分）一、ETF(E)E+TFiTT*F第5页，共8页第6页，共8页………○…………○………装…………○…………订…………○…………线…………○…………-院系：专业班级：学号：姓名：座位号：-3、（7分）写出表达式x=（a+b*c）*a-b/2+c的后缀式，三元式序列，四元式序列。答：后缀式：bc*a+a*b2/-c+x=------------------------------------（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分）设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：（1）构造相应的正规式：(0|1)*1(0|1)-------------------------------（3分）（2）NFA如下图所示，其中状态0为初始状态，状态4为终态:11100---------------------------------------------------（3分）（3）确定化：I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}0101000111----------------------------------------------------（3分）（4）最小化DFA初始划分结果（{0,1,2}，{3,4}）Move(0,0)=1Move(1,0)=1Move(2,0)=3第二次划分（{0,1}，{2}，{3,4}）Move(0,1)=2Move(1,1)=2所以状态0和状态1不可区分Move(3,0)=1Move(4,0)=3状态3和状态4可区分------------------------------------（3分）第三次划分（{0,1}，{2}，{3}，{4}）用1状态代替{0,1}状态得到最小DFA如0123401234第7页，共8页第8页，共8页装订线内不许答题下图所示0110001-----------------------------------(3分)2、（15分）已知文法G[E]:E→ETE|（E）|iT→*|+（1）将文法G改造成LL（1）文法（5分）；（2）构造文法G中每个非终结符的FIRST集合及FOLLOW集合（5分）；（3）构造LL（1）分析表（5分）。答：（1）文法存在左递归，消除左递归后的文法为：E→(E)E’|iE’------------------------------------------------------------------------（2分）E’→TEE’|ε-----------------------------------------------------------------------（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)E’E→iE’E’E’→εE’→TEE’E’→εE’→TEE’E’→εE’→εTT→*T→+----------------------------------------------------------------------------------------（3分）1234