《编译原理》学期末试卷及答案 .docx
精品名师归纳总结2021-2021 学年第一学期期末考试答案及评分标准编译原理（ A ）卷课程代码：22801204适 用 班计本 12 级命题老师：毛静任 课 教毛静教研室主任审核 签名 ：教 案 主 任 签名：题 号一二三四五总分分 值得 分一、挑选题（每道题 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、中间代码可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结得 分二、填空题（每空 1 分，共 10 分）1、编译程序是将高级语言写的源程序翻译成目标语言的程序，这种翻译过程称为编译。2、NFA 识别记号的最大特点是它的 不确定性。3、在推导过程中，如每次直接推导均替换句型中最左边的非终结符，就称为 最左推导 。4、规定一个名字在什么样的范畴内应当表示什么意义的规章，被称为_名字的作用域规章 。得 分四、简答题（第 1 小题 7 分，第 2 小题 6 分，第3 小题 7 分，共 20 分）1、（ 7 分）简述词法分析器的作用。答：词法分析器的作用是：1) 滤掉源程序中的无用成分，如注释、空格、回车等（2 分）2) 处理与详细平台有关的输入（如文件终止符的不同表示等）（1 分）3) 识别记号，并交给语法分析器。依据模式识别记号（2 分）4) 调用符号表治理器或出错处理器，进行相关处理（2 分）可编辑资料 - - - 欢迎下载精品名师归纳总结5、活动记录中储存了两类信息，一类是 掌握信息 ，另一类是 拜访信息2、6 分 对于文法 GE: ET|E+T可编辑资料 - - - 欢迎下载精品名师归纳总结6、代码生成器以 中间代码 和符号表信息 为输入，生成可以执行的目标代码。7、假如有一个正常数或者负常数C，使得每次 X 被增值 C，就变量 X 被称为_归纳变量。得 分三、判定题（正确的在题号后括号内填写“V” , 错误的填写“X”）（每道题 2 分，共 20 分）TF|T*FFE|i1). 写出句型 T*F+i的最右推导并画出分析树（ 3 分）。2). 写出上述句型的短语，直接短语、句柄（3 分）。答：（ 1）句型 T*F+i的最右推导：（2 分）ETFEE+TE+FE+iT+iT*F+i分析树如右图所示（1 分）。（2）从分析书中可以看出：短语： T*F+i, -（ 1 分）E可编辑资料 - - - 欢迎下载精品名师归纳总结T*F+i,（1 分）可编辑资料 - - - 欢迎下载精品名师归纳总结1. 编译程序与详细的机器有关，与详细的语言无关。（X ）2. 词法分析是整个编译过程中唯独和源程序打交道的阶段。（V ）3. 一个文法 G 被称为 LL1 文法，当且仅当该文法的猜测分析表中不含多重定义的条目。（ V ）4. 假如一个句型中显现了某个产生式的右部，就此右部肯定是句柄。（X ）5. 继承属性的运算方法是自上而下，包含兄弟，综合属性的运算方式是自下而上，包含自身。（ V ）6. 程序是动态的，活动室静态的。（X ）7. 对一个变量的赋值是通过环境映射和值映射两步实现的。（ V ）8. 一个变量 x 在其下次引用链范畴内总是活跃的。（ V ）9. 目标代码生成是编译器中唯独与目标机器特性相关的阶段。（ V ）10. 代码优化既可以在程序的局部范畴内进行优化，也可以在全局范畴内进行优化。（V）T*F, -（1 分）Ti直接短语： T*F-（ 1 分）F, i（1 分）分）EE+TTFT*Fi句柄： T*F（ 1可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结3、（ 7 分）写出表达式 x=（a+b*c）*a-b/2+c的后缀式，三元式序列，四元式序列。答： 后缀式： bc*a+a*b2/-c+x=（1 分）三元式序列：（3 分）1*,b,c2+,1,a3*,2,a4/,b,2 5-,3,46+,5,c7=,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*10|1（ 3 分）（2）NFA 如下图所示，其中状态 0 为初始状态，状态 4 为终态: 1110123400-（3 分）（ 3）确定化：II 0I 10,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可编辑资料 - - - 欢迎下载精品名师归纳总结0101000123401可编辑资料 - - - 欢迎下载精品名师归纳总结11（ 4）最小化 DFA初始划分结果（ 0,1,2，3,4 ）（3 分）可编辑资料 - - - 欢迎下载精品名师归纳总结Move0,0= 1Move1,0=1Move2,0=3其次次划分（ 0,1 ，2 ，3,4 ）Move0,1=2Move1,1=2所以状态 0 和状态 1 不行区分Move3,0=1Move4,0=3状态 3 和状态 4 可区分可编辑资料 - - - 欢迎下载精品名师归纳总结-（3 分）第三次划分（ 0,1 ，2 ，3 ，4 ）用 1 状态代替 0,1 状态得到最小 DFA如下图所示i*+# EEEEEiE可编辑资料 - - - 欢迎下载精品名师归纳总结01100EEE TEEE ETEEEE可编辑资料 - - - 欢迎下载精品名师归纳总结123401-3分2、（ 15 分）已知文法 GE:E ETE | （E）| i T * | +（1） 将文法 G改造成 LL（1）文法（ 5 分）。（2） 构造文法 G中每个非终结符的 FIRST集合及 FOLLOW集合（ 5 分）。（3） 构造 LL（ 1）分析表（ 5 分）。TT*T+（3 分）可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结答：（1） 文法存在左递归，排除左递归后的文法为：EEE|i EE TEE| T*|+（2） FIRSTE= ，iFIRST E=* ，+, FIRSTT=* ， + FOLLOWE= ，* ，+，# FOWLLOWE = ，* ，+，# FOLLOWT= ，i（2 分）（2 分）（ 1 分）（5 分）可编辑资料 - - - 欢迎下载精品名师归纳总结（3） ）LL1 分析表如下表所示（表结构 1 分，每个空 005 分）：可编辑资料 - - - 欢迎下载
