编译原理期末试题及答案

编译原理期末试题及答案一、选择题（共15小题，每小题2分，共30分。1-10为单选题，11-15为多选题）1.编译程序各阶段的工作都涉及到（）。A.表格管理B.语法分析C.出错处理D.语义分析答案：A2.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。A.产生式B.句子C.句型D.词素答案：A3.词法分析器的输出是（）。A.源程序B.单词符号序列（Token流）C.语法树D.目标代码答案：B4.在规范归约中，用（）来刻画可归约串。A.句柄B.前缀C.活前缀D.项目答案：A5.若项目集规范族中存在一个项目集I包含冲突项目：A→α·和B→β·aγ，其中a∈VT，则此冲突属于（）冲突。A.移进-归约B.归约-归约C.移进-移进D.无法确定答案：B6.四元式是一种普遍采用的中间代码形式，它的四个组成部分是（）。A.(运算符，运算对象1，运算对象2，结果)B.(运算对象1，运算符，运算对象2，结果)C.(结果，运算符，运算对象1，运算对象2)D.(运算对象1，运算对象2，运算符，结果)答案：A7.在程序流图中，我们称具有下述性质的结点序列为一个循环：1.它们是强连通的；2.它们中间有且只有一个是入口结点。这个入口结点支配循环中的所有结点。这个定义是（）。A.正确的B.错误的，因为循环中所有结点应相互支配C.错误的，因为循环可以有多个入口D.错误的，因为入口结点不一定支配所有结点答案：A8.算符优先分析法是一种自底向上的分析方法，它特别适用于分析（）。A.任何上下文无关文法B.正规文法C.算符优先文法（表达式文法）D.任何二义性文法答案：C9.在编译过程中，符号表的主要作用是（）。A.生成中间代码B.检查语法错误C.存储各类标识符的属性信息D.优化目标代码答案：C10.对基本块进行优化时，删除公共子表达式的优化属于（）。A.局部优化B.循环优化C.全局优化D.窥孔优化答案：A11.（多选题）编译程序前端通常包括以下哪些阶段？（）A.词法分析B.语法分析C.语义分析与中间代码生成D.代码优化E.目标代码生成答案：A,B,C12.（多选题）下列哪些文法属于LL(1)文法？（假设经过消除左递归和提取左公因子后）（）A.无二义性的文法B.无左递归的文法C.对任一非终结符，其各个产生式的SELECT集两两不相交的文法D.任何算符优先文法答案：B,C13.（多选题）在语法制导翻译中，综合属性用于（）。A.自底向上传递信息B.自顶向下传递信息C.根据子结点的属性值计算父结点的属性值D.根据父结点和兄弟结点的属性值计算当前结点的属性值答案：A,C14.（多选题）以下哪些优化技术属于循环优化？（）A.代码外提B.强度削弱C.删除归纳变量D.删除公共子表达式答案：A,B,C15.（多选题）关于活动记录，下列说法正确的是（）。A.它用于管理过程/函数的一次执行所需的信息B.它通常包括连接数据、形式参数、局部变量、临时变量等域C.静态链用于访问非局部数据，动态链用于实现过程返回D.活动记录的建立和撤销发生在编译时刻答案：A,B,C二、填空题（共10小题，每空1分，共20分）1.编译程序是指将__________语言编写的源程序翻译成等价的__________语言的目标程序的程序。答案：高级，低级（或机器）2.词法分析的任务是从左到右扫描源程序的字符流，将其转换为有意义的__________序列，并报告其中的__________错误。答案：单词（或Token），词法3.最左推导是指任何一步推导α⇒β都是对答案：最左，规范（或最左）4.在LR分析中，ACTION[s，a]规定了当状态s面临输入符号a时应采取的动作，可能的动作为：__________、__________、接受和报错。答案：移进，归约5.描述词法规则的有效工具是__________式和__________自动机。答案：正规（或正则），有限6.在属性文法中，属性分为__________属性和__________属性。答案：综合，继承7.中间代码有多种形式，常见的有__________式、__________式、逆波兰表示和三元式。答案：四元，间接三元8.基本块是指程序中一个__________的语句序列，控制流从它的__________进入，从其__________离开。答案：顺序执行，入口，出口9.常用的代码优化技术中，__________是指把循环中不变的计算移到循环外执行；__________是指用代价较低的操作替换代价较高的操作。答案：代码外提，强度削弱10.运行时存储分配策略主要有__________分配、__________分配和堆式分配三种。答案：静态，栈式三、简答题（共5小题，每小题6分，共30分）1.简述编译过程的六个主要逻辑阶段及其主要任务。答案：1)词法分析：扫描源程序字符流，识别单词（Token），输出Token流。2)语法分析：根据文法规则，分析Token流的结构，建立语法树（或推导/归约过程）。3)语义分析：审查语法树，进行语义检查（如类型检查），并收集标识符的类型等属性信息。4)中间代码生成：将语法树转换为一种与机器无关的中间表示形式（如四元式）。5)代码优化：对中间代码进行等价变换，以提高目标代码的时空效率。6)目标代码生成：将优化后的中间代码转换为特定目标机的机器代码或汇编代码。2.什么是文法的二义性？试举一个二义性文法的简单例子，并说明其如何导致二义性。答案：如果一个文法存在某个句子，其对应的语法树（或最左/最右推导）不唯一，则称该文法是二义性的。例子：文法G:对于句子id树1：根为E，左子树推导出E+E（最终为id+i树2：根为E，左子树推导出E（最终为id），右子树为E*E这两棵不同的语法树意味着句子有两种不同的解释（运算顺序），这导致了语义上的不确定性，即二义性。3.简述在自底向上的语法分析中，LR分析法的基本思想。LR(0)、SLR(1)、LR(1)、LALR(1)分析表在构造方法和分析能力上有何主要区别？答案：LR分析法的基本思想：根据当前分析栈中的内容和剩余的输入符号，确定是移进、归约、接受还是报错。它基于一个DFA，其状态是“项目集”，通过构造LR分析表（ACTION表和GOTO表）来驱动分析过程。主要区别：LR(0)：仅根据项目集本身决定动作，不考虑向前看符号。分析能力最弱，容易产生冲突。SLR(1)：在LR(0)基础上，使用FOLLOW集来简化解决归约-归约和移进-归约冲突。分析能力稍强于LR(0)，但仍可能产生冲突。LR(1)：在构造项目集时，精确计算每个项目的“向前搜索符”（Lookahead），能更精确地确定归约时机。分析能力最强，能分析所有能用LR分析器分析的文法，但状态数可能很多。LALR(1)：对LR(1)项目集进行合并（若核心项目相同则合并），合并后可能引入冲突，但若无冲突，则分析表大小与LR(0)/SLR相当。分析能力介于SLR(1)和LR(1)之间，是实践中常用的折中方案。4.什么是语法制导翻译？简述在自底向上分析（如LR分析）中实现语法制导翻译的基本方法。答案：语法制导翻译是一种在语法分析过程中，随着分析的步步展开，执行与文法规则相关联的语义动作（或计算语义规则），从而完成翻译任务的方法。在自底向上分析（如LR分析）中的基本实现方法：1)将文法进行扩充，为每个产生式附加一个语义动作（或一段语义子程序）。2)语义动作通常用花括号`{}`括起来，插入在产生式右部的合适位置。3)在自底向上的归约过程中，当使用一个产生式进行归约时，就执行附着在该产生式上的语义动作。4)为了传递属性值，通常需要一个与语法分析栈同步的语义栈。当进行移进或归约时，相应的属性值也被压入或弹出语义栈，语义动作通过访问语义栈中的属性值进行计算，并将结果属性值压入栈中。5.简述代码优化中“基本块内公共子表达式删除”和“循环不变代码外提”两种优化技术的基本思想。答案：基本块内公共子表达式删除：在一个基本块内，如果一个表达式E先前已被计算过，并且从先前计算点到当前点之间E的运算分量值没有改变，则E的这次出现称为公共子表达式。对于公共子表达式，可以删除当前的计算，直接用先前计算的结果值替换当前对E的引用。循环不变代码外提：在循环体内，如果某些表达式的值在循环的每次迭代中都不改变（即其运算分量在循环内是常量，或其定值点位于循环外且在循环内未被重新定值），则称这些表达式为循环不变计算。优化时，可以将这些计算移到循环的入口结点之前（即循环外）执行，从而避免在循环的每次迭代中都重复计算它们。四、应用题（共4小题，第1题10分，第2题15分，第3题15分，第4题20分，共60分）1.（词法分析/正规式与有限自动机，10分）请为下列语言设计相应的正规式，并构造一个识别该语言的确定有限自动机（DFA）。语言：所有由字母`a`和`b`组成，且不包含连续两个`a`的字符串（即不存在子串`aa`）。答案：正规式：`(b|ab)(a|ε)`或`(b+ab)(a+ε)`构造DFA：首先构造NFA，状态集假设为`{S,A,B}`，其中`S`为初态，`A`表示上一个字符是`a`，`B`为终态（表示接受状态，实际上S和A也可以是接受态，因为允许以a或空结束）。更清晰的方法是：状态定义：`S0`:初态，表示当前可以接受`a`或`b`，且上一个字符不是`a`（或初始状态）。`S1`:表示上一个字符是`a`。接受状态：`S0`和`S1`都是接受状态（因为字符串可以以任何字符结束，只要不出现`aa`）。转移函数：`δ(S0,a)=S1`//读入a，进入“上一个字符是a”状态`δ(S0,b)=S0`//读入b，仍保持在“安全”状态`δ(S1,a)=无`或进入死状态（因为出现连续a，拒绝）。实际上，为了构造完整的DFA，我们引入一个死状态（错误状态/非接受态）`D`。`δ(S1,b)=S0`//读入b，清除了上一个a的影响，回到安全状态`δ(D,a)=D`，`δ(D,b)=D`因此，DFA的状态为`{S0,S1,D}`，字母表`{a,b}`，初态`S0`，终态`{S0,S1}`。（可配状态转换图或状态转换表）2.（语法分析/LL(1)文法与预测分析表，15分）给定文法G[SAB(1)计算每个非终结符的FIRST集和FOLLOW集。(2)判断该文法是否是LL(1)文法，并说明理由。(3)若是LL(1)文法，请构造其预测分析表。答案：(1)FIRST(S)={a,b}FIRST(A)={a,b}FIRST(B)={a,b}FOLLOW(S)：由开始符号，S出现在A和B的产生式中。由A→由B→由S→aB因此需要先求FOLLOW(A)和FOLLOW(B)。对于A：出现在S→bA，所以FOLLOW(A)包含FOLLOW(S)。同时，A→b对于B：出现在S→aB现在有：FOLLOW(S)={#}∪FOLLOW(A)∪FOLLOW(B)FOLLOW(A)={a,b}∪FOLLOW(S)FOLLOW(B)={a,b}∪FOLLOW(S)这是一个相互包含的方程组。通过迭代求解：初始：FOLLOW(S)={#}，FOLLOW(A)={a,b}，FOLLOW(B)={a,b}。第一轮：FOLLOW(S)={#}∪{a,b}∪{a,b}={#,a,b}FOLLOW(A)={a,b}∪{#,a,b}={#,a,b}FOLLOW(B)={a,b}∪{#,a,b}={#,a,b}第二轮：FOLLOW(S)={#,a,b}∪{#,a,b}∪{#,a,b}={#,a,b}(不变)所以，最终：FOLLOW(S)={#,a,b}FOLLOW(A)={#,a,b}FOLLOW(B)={#,a,b}(2)判断是否为LL(1)文法：需要检查每个非终结符的各个产生式的SELECT集是否两两不相交。对于S→SELECT(S→aB)=FIRST(aB)={a}SELECT(S→bA)=FIRST(bA)={b}不相交。对于A→SELECT(A→a)=FIRST(a)={a}SELECT(A→aS)=FIRST(aS)={a}SELECT(A→bAA)=FIRST(bAA)={b}由于SELECT(A→a)与SELECT(A→aS)相交（都包含a），所以该文法不是LL(1)文法。(3)因为不是LL(1)文法，所以无法构造无冲突的预测分析表。若要求构造，表中对于`(A,a)`格子会有两个产生式`A→a`和`A→aS`，产生冲突。3.（语法制导翻译与中间代码生成，15分）考虑以下赋值语句的文法片段，其中`id`表示标识符，`E`表示表达式：SETF假设语义规则中已定义了`E.place`（存放E值的变量名）、`E.code`（计算E值的中间代码序列）等属性。请给出为赋值语句S→答案：为简化，我们假设`lookup()`返回一个操作数，可以是变量名或临时地址。我们使用四元式形式`(op,arg1,arg2,result)`。为S→```S→id=E;{addr=lookup();//查询id的符号表入口地址emit(‘=‘,E.place,‘_‘,addr);//生成赋值四元式，如(:=,E.place,_,addr)S.code=E.code||上述赋值四元式;//S的代码是E的代码后接赋值语句}```更详细地，嵌入到产生式中：```S→id=E;{//假设id.lexeme存储了标识符的字符串char*id_addr=lookup(id.lexeme);//获得标识符的地址（或名字）//生成赋值四元式gen(‘assign‘,E.place,‘_‘,id_addr);//假设S有一个综合属性code，这里可以赋值，但通常我们只生成代码，不一定要返回}```（注：实际语法制导定义中，`E`的`place`属性在归约`E`时已经计算好，可能是一个临时变量名或常量。这里重点在于赋值语句的翻译动作是生成一个将`E.place`的值存入`id`对应地址的指令。）4.（代码优化与数据流分析，20分）考虑以下基本块P：```t1=a+bt2=c*dt3=e-ft4=t1+t2t5=t2*t3t6=t4+t5t7=t1+t2t8=t6+t7```(1)画出该基本块的DAG图。(2)假设只有`t8`在基本块外是活跃的（即基本块出口处只有`t8`活跃），请根据DAG图对基本块P进行优化，写出优化后的四元式序列。(3)对于优化后的代码，若进一步进行“常量传播”和“死代码删除”优化，是否还有优化空间？请简要说明。答案：(1)DAG图构建过程（节点编号n，节点值）：n1(`a`),n2(`b`),n3(`+`):父节点n1,n2，结果标记`t1`。n4(`c`),n5(`d`),n6(`*`):父节点n4,n5，结果标记`t2`。n7(`e`),n8(`f`),n9(`-`):父节点n7,n8，结果标记`t3`。n10(`+`):父节点n3,n6，结果标记`t4`（后来也有`t7`）。n11(`*`):父节点n6,n9，结果标记`t5`。n12(`+`):父节点n10,n11，结果标记`t6`。n13(`+`):父节点n12,n10，结果标记`t8`。（注意：n10已有标记`t4`，且`t7`是`t1+t2`，与`t4`相同，所以`t7`也标记在n10上）。最终，节点n10有标记`t4`和`t7`。(2)优化后代码（只有`t8`活跃）：根据DAG，可以按节点生成计算顺序（需要先计算父节点）。同时，由于只有`t8`活跃，我们只需要计算最终`t8`的值，中间结果如果只用于计算`t8`且不被标记为活跃变量，则可以用临时变量而不必保留原名字。计算顺序（拓扑序）：先计算叶子：`a,b,c,d,e,f`，然后n3(`t1=a+b`),n6(`t2=c*d`),n9(`t3=e-f`),n10(`t4=t1+t2`)，注意`t7`与`t4`相同，所以`t7`