《编译原理》学期末试卷及答案 2.docx

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

1、精品名师归纳总结2021-2021 学年第一学期期末考试答案及评分标准编译原理（ B）卷课程代码：22801204适用班级：命题老师：毛静任课老师：计本 12 级毛静教研室主任审核 签名 ：教案主任 签名 ：题 号一二三四五总分评卷人分 值得 分得 分一、挑选题（每道题 2 分，共 20 分）1、编译程序和说明程序的区分是：【 B】A、说明程序产生目标程序，编译程序不生成目标代码B、说明程序不产生目标，编译程序生成目标代码C、说明程序和编译程序都生成目标代码D、说明程序和编译程序2、将编译程序分成如干个“遍”是为了：【B】A、提高程序的执行效率 B、使程序的结构更加清楚C、利用有限的机器内存并

2、提高机器的执行效率D、利用有限的机器内存但降低了机器的执行效率3、词法分析器的输出结果是 :【 C】A、单词的种别编码 B、单词在符号表中的位置C、记号流 D、单词自身值4、编译的各个阶段中，与源程序打交道的阶段是A、语法分析 B、语义分析C、词法分析 D、代码优化:【 C】5、语法分析中的立法机构是 :【 B】A、正规式 B、上下文无关文法C、上下文有关文法D、猜测分析器6、移近-归约分析表中指导分局发生变化的动作包括:【 C】A、移近、归约B、移近、归约、接受C、移近、接受、归约、出错D、移近，归约、出错7、中间代码生成时所依据的是 :【 A】A、语义规章 B、词法规章C、语法规章 D、等

3、价变换规章8、程序所需的数据空间在程序运行前就可确定，称为:【 B】A、动态储备 B、静态储备C、栈式储备 D、堆式储备9、代码生成阶段的主要任务是 :【 C】A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言C、把中间代码变换成依靠详细机器的目标代码D、把汇编语言翻译成机器语言10、代码优化的方法中不包含：【D】A、窥孔优化 B、强度减弱 C、构造流图 D、基本块优化可编辑资料 - - - 欢迎下载精品名师归纳总结得 分二、填空题（每空 1 分，共 10 分）1、每个阶段将程序完整分析一遍的工作模式称为 一遍扫描。得 分四、简答题（第 1 小题 7 分，第 2 小题 6 分，第3 小题

4、 7 分，共 20 分）1、（ 7 分）简述怎样从正规式构造词法分析器。答：从正规式构造词法分析器的基本步骤如下：可编辑资料 - - - 欢迎下载精品名师归纳总结2、将高级语言写的源程序翻译成目标语言的程序，这种翻译过程称为编译。3、如有限自动机 M 和 M 识别同一正规集 ，就称 M 和 M是等价的。4、如文法 G 对同一句子产生不止一棵分析树，就称文法G 具有二义性 。5、后缀式 ab+cd+/可用表达式 （a+b）/c+d 来表示。6、程序设计语言的运行时储备治理方案，主要分为两大类，即静态储备安排 和 动态储备安排 方案。7、经过编译所得到的目标程序是 机器语言程序 或者 汇编语言程序

5、。8、局部优化是局限于一个 基本块 范畴内的一种优化。1) 用正规式对模式进行描述（ 1 分）。2) 为每个正规式构造一个 NFA ，它识别正规式所表示的正规集（ 1 分）。3) 将构造出的NFA 转换成等价的DFA ，这一过程也被称为确定化（2分）。4) 优化 DFA，使其状态数最少，这一过程也被称为最小化（2 分）。5) 从优化后的 DFA 构造词法分析器（ 1 分）。可编辑资料 - - - 欢迎下载精品名师归纳总结得 分三、判定题（正确的在题号后括号内填写“V” , 错误的填写“X”）（每道题 2 分，共 20 分）可编辑资料 - - - 欢迎下载精品名师归纳总结1. 编译程序和机器硬件

6、有关，和详细的语言无关。（X ）2. NAF 在识别记号的时候会产生大量的回溯。（V ）3. 每个文法都能改写为 LL1 文法。（ X ）4. LR 分析表是由动作表和转移表两部分组成的。（V ）5. 代码优化的目的是把编译程序进行等价变换。（X ）6. 引用调用中，实参加形参共用同一个内存空间。（ V ）7. 综合属性的运算方式是自上而下包含自身。（ X ）8. 一个完整程序执行的掌握流，是对它的活动树的一次深度优先遍历。（V ）9. 在名字绑定的概念下，对一个常量的赋值包含了两次映射，即环境映射和状态映射 。（X）10. 通过拷贝语句进行值的传递的语句称为复写传播。（V ）2、6 分 下述

7、文法哪些文法是 LL1 文法，哪些不是 LL1 文法，为什么？（1）S-Ra | aR-Sb | b（2）S-aAc | bA-a|b |（3）S-aA | AaA-b |答：（1） 不是 LL1 文法， S=Ra= Sba 含有间接左递归，因此不是不是LL1 文法。-（2 分）（2） 是 LL1 文法，由于满意推论 3.2 的 3 条规章。-（2 分）（3） ）不是 LL1 文法。对于 S-Aa | Aa，求得 First（aA）与 First（Aa）的交集为 a，所以不是 LL1 文法， -（2 分）可编辑资料 - - - 欢迎下载精品名师归纳总结得 分五、论述题（每道题 15 分，共 3

8、0 分）1、（ 15 分）已知某 NFA 的状态转换矩阵如下表 1 所示，将此 NFA 确定化，构造器最小化 DFA ，要求写出详细解题过程。表 1 NFA 的状态转换矩阵abcd答：从上表中可以看出，该 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,23,45 6,71 即是最终划分 ,（2 分）重新命名 , 以 1，3，5，6 代替

9、1,2 3,4 5 6,7得最小化的 DFA 如下表 2 所示a3表 2 最小化后的 DFAb 16cd13563536bcb1a3b6ad53、（ 7 分）写出表达式 x=a-b*c-a+（ b/2+c）的后缀式，三元式序列，四元式序列。答：后缀式： abc*-a-b2/c+x=-（1 分）三元式序列：-（3 分）3-,2,a1324/,b,22425+,4,c6+,3,536357=,x,64735四元式序列：-（3 分）54-,a,T1,T266-,T2,a,T3761*,b,c 2-,a,1*,b,c,T1/,b,2,T4+,T4,c,T5+,T3,T5,T6=,x,T6,T7可编辑资

10、料 - - - 欢迎下载精品名师归纳总结（ 4 分）2、（ 15 分）已知文法 GS:SaBc|bAB AaAb|b Bb|（1） 构造其 LL （1）分析表（ 12 分）。（2） 使用自上而下的分析方法判定字符串baabbb是否为该文法的句子（ 3 分）。答：（ 1）第一运算全部终结符的 FIRST 集合和 FOLLOW 集合。FIRSTB=b, FIRSTA=a,bFIRSTS=a,bFOLLOWS=#FOLLOWA=b,#FOLLOWB=c,#（6 分）猜测分析表如下所示：abSbABc#SS aBcAA aAbAbBBb（6 分）BB（2）自上而下的分析方法是从文法的开头符号开头进行最左推导得到一个终结符序列，这个终结符序列称为该文法的句子。（ 1 分） S=bAB=b aAbB=baaAbbB=baabbbB=baabbb所以 baabbb是该文法的句子。（2 分）可编辑资料 - - - 欢迎下载