编译原理期末复习题(含答案)

编译原理期末复习题(含答案)一、选择题（每题2分，共20分）（一）单项选择题1.编译程序是对（）。A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言程序的翻译答案：D2.词法分析器的输出结果是（）。A.单词的种别编码和自身值B.单词在符号表中的位置C.单词的种别编码D.单词自身值答案：A3.文法G[A.xB.(C.yD.y答案：C4.在规范归约中，用（）来刻画可归约串。A.直接短语B.句柄C.最左素短语D.素短语答案：B5.若项目集I含有A→α·，则在状态I时，仅当面临的输入符号aA.LALR文法B.LR(0)文法C.LR(1)文法D.SLR(1)文法答案：D（二）多项选择题6.编译过程中，语法分析器的任务包括（）。A.分析单词的构成B.分析单词串如何构成句子C.分析句子如何构成程序D.对语法错误进行恢复E.生成中间代码答案：B,C,D7.下列选项中，属于编译前端工作的有（）。A.词法分析B.语法分析C.语义分析与中间代码生成D.代码优化E.目标代码生成答案：A,B,C8.一个上下文无关文法G包括的组成部分有（）。A.一组终结符号B.一组非终结符号C.一个开始符号D.一组产生式E.一组语义规则答案：A,B,C,D9.在自下而上的语法分析中，可能发生的冲突类型有（）。A.移进-归约冲突B.归约-归约冲突C.递归-循环冲突D.二义性冲突E.左递归冲突答案：A,B10.常见的中间代码形式有（）。A.三元式B.四元式C.逆波兰表示法D.抽象语法树E.DAG图答案：A,B,C,D,E二、填空题（每空1分，共15分）1.编译过程通常可分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、______和______。答案：代码优化，目标代码生成2.一个名字的属性包括______和______。答案：类型，作用域（或存储地址、值等，任选两个常用属性）3.词法分析中，通常用______理论来描述单词的构成，用______来实现词法分析器。答案：正规式（或正则表达式），有限自动机4.文法符号X的FIRST集是指由X推导出的所有串的______符号的集合。如果X可以推导出空串ϵ，则规定答案：开始（或首）5.在递归下降分析法中，每个非终结符对应一个______。对于含有左递归和公共左因子的文法，需要先进行文法______。答案：子程序（或函数），改造（或消除）6.给定文法G[答案：左7.在语法制导翻译中，为文法符号配备的“属性”可分为______属性和______属性两大类。答案：综合，继承8.在程序流图中，如果从首结点出发到达某个基本块B的每条路径都经过另一个基本块，则称是B的______。答案：必经结点三、简答题（每题5分，共25分）1.简述编译程序与解释程序的主要区别。答案：编译程序将高级语言源程序一次性翻译成等价的目标语言程序（汇编或机器语言），然后执行目标程序。解释程序则边翻译边执行，不生成独立的目标程序。编译程序执行效率高，但移植性依赖于目标机；解释程序交互性好，易于调试，但执行效率较低。2.什么是句柄？在自下而上的语法分析中，句柄的作用是什么？答案：句柄是一个句型的最左直接短语。在自下而上的语法分析中，识别句柄是进行归约的关键步骤。分析器不断移进输入符号，一旦在栈顶形成某个产生式的右部（即句柄），就用该产生式的左部进行归约，逐步规约到文法的开始符号，从而完成语法分析。3.简述活动记录（ActivationRecord）中通常包含哪些主要信息。答案：活动记录是过程（函数）一次执行所需信息的管理单元，通常包含：（1）连接数据：返回地址、动态链（指向调用者活动记录的指针）、静态链（用于访问非局部数据）。（2）形式参数和返回值。（3）局部变量。（4）临时变量。（5）机器状态信息（如寄存器保存区）。4.简述在代码优化中，循环优化主要有哪些技术？答案：循环优化是代码优化的重点，主要技术包括：（1）代码外提：将循环中不变的计算移到循环体外。（2）强度削弱：将循环中耗时的运算（如乘法）转换为等价的廉价运算（如加法）。（3）删除归纳变量：删除循环中只用于控制循环的变量，用与之线性相关的其他变量替代。（4）循环展开：复制循环体多次，减少循环控制开销。（5）循环合并：将多个相同循环合并为一个。5.什么是“悬挂else”问题？文法如何描述可以解决此问题？答案：“悬挂else”问题是指当then子句后跟else子句时，else子句可能与最近的then匹配，也可能与外层的then匹配，导致二义性。例如：`ifE1thenifE2thenS1elseS2`。可以通过改写文法来强制else与最近的then配对，从而消除二义性。例如，将条件语句文法区分为完全条件语句（带else）和不完全条件语句（不带else）：```S->MS1|UM->ifEthenU->ifEthenSelseS```但更常见的是在文法中直接规定“else与最近的then匹配”的消歧规则。四、应用题（共40分）（一）词法与语法分析题（12分）1.为语言L=|n答案：该语言是两种情况的并集：n=m且k≥1；设开始符号为S。```S->AC|DBA->aAb|ab//生成a^nb^n,n>=1B->bBc|bc//生成b^mc^m,m>=1C->cC|c//生成c^k,k>=1D->aD|a//生成a^n,n>=1```评分标准：正确区分两种情况得2分；每种情况对应的产生式正确各得2分（A、C一组，D、B一组）。2.给定文法G[```S->(L)|aL->L,S|S```（1）消除文法的左递归。（3分）（2）为改写后的文法计算FIRS答案：（1）消除左递归后的文法[S```S->(L)|aL->SL'L'->,SL'|ε```（2）计算各非终结符的FIRSFFFFOLLOW(SFOLLOW(LFOLLOW（二）语法制导翻译与中间代码题（14分）1.考虑以下赋值语句的文法片段，其中id表示标识符，E```S->id=EE->E1+E2E->(E1)E->id```为其设计语法制导定义，将赋值语句翻译成三地址代码。假设三地址指令形式为`x=yopz`，`x=y`，并有一个临时变量生成函数`newtemp()`和一个过程`emit(...)`用于生成代码。为S和E设计综合属性`code`（存放已生成的代码串）和`place`（存放存放结果的变量名）。（8分）答案：语法制导定义如下：产生式及语义规则：（1）S`{S.code=E.code||emit(id.lexeme‘=’E.place);}`（2）E`{E.place=newtemp();``E.code=E1.code||E2.code||emit(E.place‘=’E1.place‘+’E2.place);}`（3）E`{E.place=E1.place;E.code=E1.code;}`（4）E`{E.place=id.lexeme;E.code=‘’;}`评分标准：每个产生式的语义规则正确各得2分。2.将语句`x=a+b*(c+d)`翻译成四元式序列。假设运算符优先级和结合性按常规规定。（6分）答案：假设四元式形式为`(op,arg1,arg2,result)`。```(1)(+,c,d,t1)(2)(*,b,t1,t2)(3)(+,a,t2,t3)(4)(=,t3,_,x)```评分标准：顺序和结果正确，每个四元式1.5分。（三）代码优化与目标代码生成题（14分）1.给定以下基本块B的三地址代码序列：```t1=a*bt2=t1+ct3=a*bt4=t2+t3t5=t4-c```（1）画出该基本块的DAG图。（4分）（2）根据DAG图，写出优化后的三地址代码序列。（4分）答案：（1）DAG图构建：结点编号及标记：(leaf,a)(leaf,b)(*,,)//计算a*b，结果记为t1/t3(leaf,c)(+,,)//计算t1+c，结果t2(+,,)//计算t2+t1，结果t4(-,,)//计算t4-c，结果t5（图形结构应为：n1,n2指向n3；n3和n4指向n5；n5和n3指向n6；n6和n4指向n7）（2）优化后的三地址代码序列（假设只有t1,t2,t3,t4,t5是临时变量，a,b,c是给定的）：```t1=a*b//n3t2=t1+c//n5t4=t2+t1//n6，消除了对t3的重复计算t5=t4-c//n7```最终活跃变量若仅为t5，则t2和t4的赋值也可视情况消除，但题目未给活跃信息，故保留计算t5所需的所有赋值。优化主要体现在删除了`t3=a*b`这个冗余计算。评分标准：DAG图结点和边正确得4分；优化后代码正确得4分（删除冗余计算得关键分）。2.简述在简单栈式目标代码生成中，如何翻译`x=y+z`这样的三地址语句？假设变量地址在编译时已知，并采用相对地址。（6分）答案：在栈式目标代码生成模型中，运算对象通常通过压栈和弹栈操作进行。假设变量y和z的地址（相对于活动记录基址的偏移量）分别为offset_y和offset_z，结果存入x(offset_x)。翻译过程如下：（1）生成将变量y的值压入栈顶的指令：`LOADoffset_y(FP)`或`PUSHoffset_y(FP)`（FP为帧指针）。（2）