《编译原理》2014-2015学年期末试卷及答案2.doc

2014-2015学年第一学期期末考试答案及评分标准编译原理（B）卷命题教师：毛静任课教师：毛静 课程代码：22801204适用班级：计本12级 教研室主任审核(签名)：教学主任(签名)：题 号一二三四五总分评卷人分 值得 分得 分一、（每小题2分，共20分）1、编译程序和解释程序的区别是： 【B】A、解释程序产生目标程序，编译程序不生成目标代码B、解释程序不产生目标，编译程序生成目标代码C、解释程序和编译程序都生成目标代码D、解释程序和编译程序2、将编译程序分成若干个“遍”是为了：【B 】A、提高程序的执行效率B、使程序的结构更加清晰C、利用有限的机器内存并提高机器的执行效率D、利用有限的机器内存但降低了机器的执行效率3、词法分析器的输出结果是:【C】A、单词的种别编码B、单词在符号表中的位置C、记号流D、单词自身值4、编译的各个阶段中，与源程序打交道的阶段是:【C】A、语法分析B、语义分析C、词法分析D、代码优化5、语法分析中的立法机构是:【B】A、正规式B、上下文无关文法C、上下文有关文法D、预测分析器6、移近-归约分析表中指导分局发生变化的动作包括:【C】A、移近、归约B、移近、归约、接受C、移近、接受、归约、出错D、移近，归约、出错7、中间代码生成时所依据的是:【A】A、语义规则B、词法规则C、语法规则D、等价变换规则8、程序所需的数据空间在程序运行前就可确定，称为:【B】A、动态存储B、静态存储C、栈式存储D、堆式存储9、代码生成阶段的主要任务是:【C】A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言C、把中间代码变换成依赖具体机器的目标代码D、把汇编语言翻译成机器语言10、代码优化的方法中不包含：【D】A、窥孔优化B、强度削弱C、构造流图D、基本块优化得 分二、（每空1分，共10分）一、1、每个阶段将程序完整分析一遍的工作模式称为_一遍扫描_。2、将高级语言写的源程序翻译成目标语言的程序，这种翻译过程称为 编译_。3、若有限自动机 M 和 M_识别同一正规集_，则称 M 和 M是等价的。4、若文法G对同一句子产生不止一棵分析树，则称文法G_具有二义性_。5、后缀式ab+cd+/可用表达式_（a+b）/(c+d)_来表示。6、程序设计语言的运行时存储管理方案，主要分为两大类，即_静态存储分配_和_动态存储分配_方案。7、经过编译所得到的目标程序是_机器语言程序_或者_汇编语言程序。8、局部优化是局限于一个_基本块_范围内的一种优化。得 分三、（正确的在题号后括号内填写“V”,错误的填写“X”）（每小题2分，共20分）1.编译程序和机器硬件有关，和具体的语言无关。（ X ）2.NAF在识别记号的时候会产生大量的回溯。（ V ）3.每个文法都能改写为LL(1)文法。（ X ）4.LR分析表是由动作表和转移表两部分组成的。（ V ）5.代码优化的目的是把编译程序进行等价变换。（ X ）6.引用调用中，实参与形参共用同一个内存空间。 （ V ）7.综合属性的计算方式是自上而下包含自身。 （ X ） 8.一个完整程序执行的控制流，是对它的活动树的一次深度优先遍历。（ V ） 9.在名字绑定的概念下，对一个常量的赋值包含了两次映射，即环境映射和状态映射。（X ）10.通过拷贝语句进行值的传递的语句称为复写传播。 （V ）得 分四、（第1小题7分，第2小题6分，第3小题7分，共20分）1、（7分）简述怎样从正规式构造词法分析器。答：从正规式构造词法分析器的基本步骤如下：1) 用正规式对模式进行描述（1分）；2) 为每个正规式构造一个NFA，它识别正规式所表示的正规集（1分）；3) 将构造出的 NFA 转换成等价的 DFA，这一过程也被称为确定化（2分）；4) 优化DFA，使其状态数最少，这一过程也被称为最小化（2分）；5) 从优化后的 DFA 构造词法分析器（1分）。2、(6分)下述文法哪些文法是LL(1)文法，哪些不是LL(1)文法，为什么？（1）S-Ra | a R-Sb | b（2）S-aAc | b A-a|b |（3）S-aA | Aa A-b |答：（1） 不是LL(1)文法，S=Ra= Sba 含有间接左递归，因此不是不是LL(1)文法。-（2分）（2） 是LL(1)文法，因为满足推论3.2的3条规则。-（2分）（3）不是LL(1)文法。对于S-Aa | Aa，求得First（aA）与First（Aa）的交集为a，所以不是LL(1)文法，-（2分）3、（7分）写出表达式x=a-b*c-a+（b/2+c）的后缀式，三元式序列，四元式序列。答：后缀式：abc*-a-b2/c+x= -（1分）三元式序列： -（3分）(1)(*,b,c)(2)(-,a,(1)(3)(-,(2),a)(4)(/,b,2)(5)(+,(4),c)(6)(+,(3),(5)(7)(=,x,(6)四元式序列： -（3分）(*,b,c,T1)(-,a,T1,T2)(-,T2,a,T3)(/,b,2,T4)(+,T4,c,T5)(+,T3,T5,T6)(=,x,T6,T7)得 分五、（每小题15分，共30分）1、（15分）已知某NFA的状态转换矩阵如下表1所示，将此NFA确定化，构造器最小化DFA，要求写出具体解题过程。表1 NFA的状态转换矩阵abcd13224236354735546676答：从上表中可以看出，该NFA已经是DFA，所以直接对其进行最小化（5分）。初始分划0: 终态组6,7，非终态组1,2,3,4,5-（2分）对1,2,3,4,5进行审查：1,2输入b到达2，而3,4输入b到达6,7，5输入b不会有任何动作，故得到新分划1,2 3,4 5 -（2分）1:1,2 3,45 6,71即是最后划分, -（2分）重新命名, 以1，3，5，6代替1,2 3,4 5 6,7 得最小化的DFA如下表2所示表2 最小化后的DFAabcd1313635536636b1abcb5da -（4分）2、（15分）已知文法GS: SaBc|bABAaAb|bBb|（1）构造其LL（1）分析表（12分）；（2）使用自上而下的分析方法判断字符串baabbb是否为该文法的句子（3分）。答：（1）首先计算所有终结符的FIRST集合和FOLLOW集合。FIRST(B)=b, FIRST(A)=a,bFIRST(S)=a,bFOLLOW(S)=#FOLLOW(A)=b,#FOLLOW(B)=c,# -（6分）预测分析表如下所示：abc#SSaBc