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

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

1、2014-2015学年第一学期期末考试答案及评分标准编译原理（ A ）卷命题老师：毛静任课老师：毛静 课程代码：适用班级：计本12级 教研室主任审核(签名)：教学主任(签名)：题 号一二三四五总分分 值得 分选择题一、（每小题2分，共20分）1、下述编译过程，依次正确的是： 【 C 】A、词法分析，语义分析，语法分析，代码优化，中间代码生成，目的代码生成B、语法分析，词法分析，语义分析，中间代码生成，代码优化目的代码生成C、词法分析，语法分析，语义分析，中间代码生成，代码优化，目的代码生成D、语法分析，词法分析，语义分析，中间代码生成，目的代码生成，代码优化2、编译程序是对： 【 D】A、高级

2、语言程序的执行 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、可移进工程

3、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、当到根本块的完毕语句时

4、，将变量的值保存在存放器中C、当到根本块的完毕语句时，将变量的值保存在内存中D、应当将一个根本块内的不常运用的的变量占用的存放器尽早释放10、作为目的代码生成的根本单位的是： 【B】A、三地址吗B、根本块C、流图 D、中间代码得 分二、填空题（每空1分，共10分）一、1、编译程序是将_高级语言_写的源程序翻译成_目的语言_的程序，这种翻译过程称为编译。2、NFA识别记号的最大特点是它的_不确定性_。3、在推导过程中，若每次干脆推导均交换句型中最左边的非终结符，则称为_最左推导_。4、规定一个名字在什么样的范围内应当表示什么意义的规则，被称为_名字的作用域规则_。5、活动记录中保存了两类信息，一

5、类是_限制信息_，另一类是_访问信息_6、代码生成器以_中间代码_与_符号表信息_为输入，生成可以执行的 目的代码。7、假设有一个正常数或者负常数C，使得每次X被增值C，则变量X被称为_归纳变量。得 分三、推断题（正确的在题号后括号内填写“V”,错误的填写“X”）（每小题2分，共20分）1. 编译程序与详细的机器有关，与详细的语言无关。 （ X ） 2. 词法分析是整个编译过程中唯一与源程序打交道的阶段。 （ V ） 3. 一个文法G被称为LL(1)文法，当且仅当该文法的意料分析表中不含多重定义的条目。 （V ）4. 假设一个句型中出现了某个产生式的右部，则此右部确定是句柄。 （ X ） 5.

6、 继承属性的计算方法是自上而下，包含兄弟，综合属性的计算方式是自下而上，包含自身。 （ V ）6. 程序是动态的，活动室静态的。 （ X ） 7. 对一个变量的赋值是通过环境映射与值映射两步实现的。 （ V ） 8. 一个变量x在其下次引用链范围内总是活泼的。 （ V ） 9. 目的代码生成是编译器中唯一与目的机器特性相关的阶段。 （ V ） 10. 代码优化既可以在程序的部分范围内进展优化，也可以在全局范围内进展优化。 （ V ） 得分四、简答题（第1小题7分，第2小题6分，第3小题7分，共20分）1、（7分）简述词法分析器的作用。答：词法分析器的作用是：1) 滤掉源程序中的无用成分，如注释

7、、空格、回车等（2分）2) 处理与详细平台有关的输入（如文件完毕符的不同表示等）（1分）3) 识别记号，并交给语法分析器。依据形式识别记号（2分）4) 调用符号表管理器或出错处理器，进展相关处理（2分） 2、(6分)对于文法G(E):ET|E+TTF|T*FF(E)|i1).写出句型 (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）从分析书中可以看出：

8、短语：(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= -（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,

9、T4,T5)(+,T5,c,T6)(=,x,T6,T7)得 分五、阐述题（每小题15分，共30分）1、 （15分）设S=0，1上的正规集S由倒数第二个字符为1的全部字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：（1）构造相应的正规式：(0|1)*1(0|1) -（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

10、 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)=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

11、） 构造文法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分）第 6 页