编译原理期末考试题目及答案

编译原理期末考试题目及答案一、选择题（每题2分，共20分）1.编译程序是对（）。A.汇编语言的翻译B.高级语言的翻译C.机器语言的执行D.高级语言程序的解释执行答案：B。编译程序是将高级语言源程序翻译成目标机器的机器语言或汇编语言的程序。2.词法分析器的输出结果是（）。A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值答案：C。词法分析器从源程序中识别出一个个单词，并输出单词的种别编码和自身值。3.一个句型中的最左（）称为该句型的句柄。A.短语B.简单短语C.素短语D.终结符号答案：B。句柄是一个句型中的最左简单短语。4.算符优先分析法每次都是对（）进行归约。A.句柄B.最左素短语C.素短语D.简单短语答案：B。算符优先分析法每次归约的是最左素短语。5.四元式之间的联系是通过（）实现的。A.指示器B.临时变量C.符号表D.程序变量答案：B。四元式之间的联系通常通过临时变量来实现。6.代码优化的目的是（）。A.节省时间B.节省空间C.节省时间和空间D.把编译程序进行等价变换答案：C。代码优化的目的是提高目标程序的执行效率，即节省时间和空间。7.编译程序使用（）区别标识符的作用域。A.语法树B.符号表C.控制流图D.三元式答案：B。符号表用于记录标识符的各种信息，包括作用域等。8.若文法G定义的语言是无限集，则文法必然是（）。A.递归的B.前后文无关的C.二义性的D.无二义性的答案：A。只有递归的文法才能产生无限集的语言。9.（）不是编译程序的组成部分。A.词法分析程序B.代码提供程序C.设备管理程序D.语法分析程序答案：C。编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码提供程序、代码优化程序和代码提供程序等组成，设备管理程序不属于编译程序的组成部分。10.设有文法G[S]：S→a|(T)，T→T,S|S，该文法（）。A.是LL(1)文法B.是算符优先文法C.是SLR(1)文法D.不是算符优先文法答案：B。通过对该文法的算符优先关系的分析，可以判断它是算符优先文法。二、填空题（每空2分，共20分）1.编译过程可分为词法分析、语法分析、语义分析、中间代码提供、代码优化和代码提供六个阶段。2.一个上下文无关文法包含四个组成部分，即一组终结符号、一组非终结符号、一个开始符号和一组产生式。3.自顶向下语法分析方法会遇到的主要问题有左递归和回溯。4.常用的两种动态存储分配策略是栈式存储分配和堆式存储分配。三、判断题（每题2分，共10分）1.编译程序提供的目标程序一定是可执行的程序。（×）编译程序提供的目标程序可能是汇编语言程序或机器语言程序，不一定是可执行的，还需要经过链接等操作。2.一个文法所有句型的集合就是该文法所定义的语言。（×）一个文法所有句子的集合才是该文法所定义的语言，句型包含句子和含非终结符的形式。3.算符优先分析法只能分析算符优先文法。（√）算符优先分析法是针对算符优先文法设计的分析方法。4.代码优化是对中间代码或目标代码进行等价变换，以提高程序的执行效率。（√）代码优化的本质就是进行等价变换来提高效率。5.词法分析和语法分析本质上都是对源程序的扫描，所以可以合并成一个阶段。（×）词法分析和语法分析虽然都有扫描操作，但它们的任务和处理对象不同，不能简单合并。四、简答题（每题10分，共30分）1.简述编译程序和解释程序的区别。编译程序是将高级语言源程序一次性翻译成目标机器的机器语言或汇编语言程序，然后再执行该目标程序。编译过程完成后，源程序就不再参与执行过程，执行速度相对较快，适合处理大型程序。例如，C语言程序通过编译程序提供可执行文件后，后续直接执行该可执行文件。解释程序则是对高级语言源程序逐句进行解释执行，即每读入一句源程序，就对其进行解释并执行，不提供目标程序。解释程序的执行效率相对较低，但是具有较好的交互性和可移植性，适合快速开发和调试程序，如Python语言通常使用解释程序来执行。2.什么是LL(1)文法？判断一个文法是否为LL(1)文法的步骤有哪些？LL(1)文法是一种自顶向下的分析文法。第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示在分析过程中只需要向前看一个输入符号。判断一个文法是否为LL(1)文法的步骤如下：（1）计算每个非终结符的FIRST集。FIRST(α)是由符号串α所能推导出的所有可能的终结符串的首终结符组成的集合，如果α能推导出ε，则ε也属于FIRST(α)。（2）计算每个非终结符的FOLLOW集。FOLLOW(A)是指在所有句型中紧跟在非终结符A后面的终结符的集合，对于开始符号，要在其FOLLOW集中加入结束符。（3）对于文法中的每个非终结符A的产生式A→α1|α2|…|αn，计算SELECT(A→αi)集。SELECT(A→αi)=FIRST(αi)（如果αi不能推导出ε）；SELECT(A→αi)=(FIRST(αi){ε})∪FOLLOW(A)（如果αi能推导出ε）。（4）检查对于每个非终结符A的任意两个不同的产生式A→α和A→β，是否有SELECT(A→α)∩SELECT(A→β)=∅。如果所有非终结符的产生式都满足这个条件，则该文法是LL(1)文法。3.简述代码优化的主要类型。代码优化主要有以下几种类型：（1）局部优化：是在基本块内进行的优化。基本块是指程序中顺序执行的语句序列，其中只有一个入口和一个出口。局部优化包括删除公共子表达式、复写传播、删除无用代码等。例如，在一个基本块内，如果有多次计算相同的表达式，就可以删除重复的计算，只保留一次计算结果。（2）循环优化：针对程序中的循环结构进行的优化。常见的循环优化技术有代码外提、强度削弱、删除归纳变量等。代码外提是将循环中不变的代码提到循环外面，减少循环内的计算量；强度削弱是将强度大的运算替换为强度小的运算，如将乘法替换为加法；删除归纳变量是消除循环中不必要的变量。（3）全局优化：在整个程序范围内进行的优化。它考虑程序中不同基本块之间的关系，例如公共子表达式的删除可以跨越多个基本块进行。全局优化还包括数据流分析，通过分析程序中数据的流动情况来进行优化。五、综合题（每题10分，共20分）1.已知文法G[S]：S→aABeA→b|AbB→d（1）构造该文法的FIRST集和FOLLOW集。FIRST集：FIRST(S)={a}FIRST(A)={b}FIRST(B)={d}FOLLOW集：FOLLOW(S)={}FOLLOW(A)={d}FOLLOW(B)={e}（2）判断该文法是否为LL(1)文法。对于非终结符A，其产生式为A→b|Ab。SELECT(A→b)=FIRST(b)={b}SELECT(A→Ab)=FIRST(Ab)={b}因为SELECT(A→b)∩SELECT(A→Ab)={b}≠∅，所以该文法不是LL(1)文法。2.给出表达式(a+b)c