2023年编译原理期末试卷及答案资料

20２３-202３学年第一学期期末考试答案及评分标准《编译原理》(Ｂ)卷命题教师：毛静命题教师：毛静任课教师：毛静课程代码：22801204合用班级：计本12级教研室主任审核(署名)：教学主任(署名）:题号一二三四五总分评卷人分值得分得分MACROＢUＴＴONAcｃeｐtＡlｌChａngesInDoc选择题(每小题2分,共20分）1、编译程序和解释程序的区别是：【B】A、解释程序产生目的程序,编译程序不生成目的代码B、解释程序不产生目的,编译程序生成目的代码ﻩC、解释程序和编译程序都生成目的代码D、解释程序和编译程序2、将编译程序提成若干个“遍”是为了：ﻩ【B】ﻩA、提高程序的执行效率 B、使程序的结构更加清楚ﻩＣ、运用有限的机器内存并提高机器的执行效率ﻩﻩD、运用有限的机器内存但减少了机器的执行效率3、词法分析器的输出结果是: 【C】A、单词的种别编码 ﻩB、单词在符号表中的位置Ｃ、记号流ﻩ Ｄ、单词自身值4、编译的各个阶段中,与源程序打交道的阶段是:【C】 Ａ、语法分析ﻩ B、语义分析ﻩC、词法分析 Ｄ、代码优化５、语法分析中的立法机构是： 【Ｂ】 A、正规式ﻩ Ｂ、上下文无关文法C、上下文有关文法 ﻩD、预测分析器6、移近-归约分析表中指导分局发生变化的动作涉及:【C】Ａ、移近、归约ﻩ Ｂ、移近、归约、接受C、移近、接受、归约、犯错 ﻩD、移近，归约、犯错7、中间代码生成时所依据的是:ﻩ【Ａ】ﻩA、语义规则 Ｂ、词法规则ﻩＣ、语法规则 D、等价变换规则８、程序所需的数据空间在程序运营前就可拟定,称为：【Ｂ】 A、动态存储ﻩﻩB、静态存储ﻩC、栈式存储 ﻩＤ、堆式存储9、代码生成阶段的重要任务是:【C】 A、把高级语言翻译成汇编语言ﻩB、把高级语言翻译成机器语言 C、把中间代码变换成依赖具体机器的目的代码ﻩ Ｄ、把汇编语言翻译成机器语言10、代码优化的方法中不包含： 【Ｄ】 Ａ、窥孔优化ﻩ B、强度削弱ﻩＣ、构造流图ﻩ D、基本块优化得分得分二、MACROBUTTONAcceptAllChangesInDoc填空题（每空1分，共10分）1、每个阶段将程序完整分析一遍的工作模式称为_＿_＿＿一遍扫描＿＿___。2、将高级语言写的源程序翻译成目的语言的程序，这种翻译过程称为编译_____＿。3、若有限自动机M和Ｍ’_＿__辨认同一正规集＿＿___,则称M和M’是等价的。４、若文法G对同一句子产生不止一棵分析树,则称文法G___具有二义性＿__。5、后缀式aｂ+ｃd+/可用表达式＿__＿（a＋ｂ)／(ｃ+d）_＿__来表达。6、程序设计语言的运营时存储管理方案,重要分为两大类，即_＿静态存储分派___和＿_＿_动态存储分派___方案。7、通过编译所得到的目的程序是__机器语言程序___或者＿＿汇编语言程序。。8、局部优化是局限于一个__基本块___范围内的一种优化。得分得分三、MACROBUTTONAcceptAllChangesInDoc判断题（对的的在题号后括号内填写“V”,错误的填写“X”）（每小题2分，共20分）1.编译程序和机器硬件有关,和具体的语言无关。（X）2.ＮAＦ在辨认记号的时候会产生大量的回溯。(V)3．每个文法都能改写为ＬL(1）文法。(Ｘ）4.LR分析表是由动作表和转移表两部分组成的。（Ｖ）5.代码优化的目的是把编译程序进行等价变换。（X）6．引用调用中,实参与形参共用同一个内存空间。(Ｖ)7．综合属性的计算方式是自上而下包含自身。(X)8.一个完整程序执行的控制流,是对它的活动树的一次深度优先遍历。(Ｖ）9．在名字绑定的概念下，对一个常量的赋值包含了两次映射,即环境映射和状态映射。（X)10.通过拷贝语句进行值的传递的语句称为复写传播。（V）得分四、MＡCROBUTTONAcｃeptＡllChａngｅsIｎDｏｃ简答题(第１小题7分,第2小题６分，第3小题7分,共２０分)1、（７分）简述如何从正规式构造词法分析器。答:从正规式构造词法分析器的基本环节如下:用正规式对模式进行描述(１分）；为每个正规式构造一个ＮFＡ，它辨认正规式所表达的正规集(1分）；将构造出的ＮFＡ转换成等价的DFA，这一过程也被称为拟定化（2分);优化DFA,使其状态数最少,这一过程也被称为最小化(2分）；从优化后的DFA构造词法分析器(1分）。2、(6分）下述文法哪些文法是LL(1)文法,哪些不是LL（１）文法,为什么？（1）S->Rａ｜aR->Sb｜b(２)S->aAc|bA－＞a|b|ε（3）Ｓ->aA|AaA-＞b|ε答：不是ＬL(1）文法,S=>Ra=>Sba具有间接左递归，因此不是不是LL(1)文法。-----－----－---－----------（2分)是LL(1)文法,由于满足推论3.2的3条规则。－-----－-------------－---－（2分)（３)不是LL(1)文法。对于S-＞Aa｜Aａ，求得Firsｔ（aA)与First(Aa）的交集为a,所以不是ＬL(1)文法,----－-----－--－－－－---－----（2分）3、（７分）写出表达式x=a-b＊c-a+（ｂ／2＋ｃ）的后缀式，三元式序列,四元式序列。答:后缀式：aｂｃ＊-a-b2/c++ｘ=－--－--－---－-----－-－－-－---（1分）三元式序列:----－----－----－------－-－-（3分)(１)(＊，b,c)(2)(-,a，（1))（3）（-,(2),a)(4)(/,ｂ,2)(5)（+,(4），ｃ)(6）（+,(3),(5)）(７)(＝,x,(6))四元式序列:－-－-----------－-------－--（3分)(*,b,c,T1)（-,a,T1,T2)(-,Ｔ２,a,T3)(/,b,2,T4)(＋,T4,c,T5)(+,Ｔ３,T５，T6)(=,ｘ,T６,T7)得分五、ＭACROBUTＴＯNAcceｐtAｌlＣhangesInDoc论述题(每小题15分,共30分）1、(15分）已知某NＦA的状态转换矩阵如下表1所示，将此NFA拟定化,构造器最小化DFA，规定写出具体解题过程。表1NFA的状态转换矩阵ａｂcd13２2４2363５47355４6６7６答:从上表中可以看出,该NFＡ已经是DFＡ，所以直接对其进行最小化（5分）。初始分划Π0:终态组｛６,7｝,非终态组{1,２,3，４,5}------－--－--－-----－--（２分)对{1，2,3,4,5}进行审查:{１，２｝输入b到达｛２｝，而{3,４｝输入b到达{６，７}，{５}输入b不会有任何动作，故得到新分划{1,２}{３,4}{５}-－-－-－-----－－-－-－－-----（2分）Π１:{1,2}ﻩ{３，4｝ {5｝｛6,７}Π1即是最后划分,--－--------－--－-------(2分)重新命名,以1，3，5,6代替{1,2｝{3,4}｛５｝{6,７}得最小化的DFA如下表2所示表2最小化后的DFAａｂcd131363553６6336b1abcb5da－－－---－----－－--------－-－---－--－（4分)2、（1５分)已知文法G[S]：Ｓ→ａBｃ｜bABA→aAb|bB→b|ε(1)构造其ＬL（１)分析表（12分);（２)使用自上而下的分析方法判断字符串baabbb是否为该文法的句子（３分)。答：（1）一方面计算所有终结符的FIRST集合和FOLLOＷ集合。FIRST（B)=｛b,ε｝FIＲＳT(A)={a,b}FＩRSＴ（S)={a,b}ＦOＬLOW(S)＝{#}FOLLOW(A)={b，#｝FOLＬOW（B)={c,#}-----－----－-------－---------－----－---(6分)预测分析表如下所示:ａｂc＃SＳ→aＢｃS→bＡBＡA→aAbA→ｂBB→bB→εB→ε－－----－-－-－－--－---------－－－------－---（6分)(2)自上