编译原理自测题附答案(有错)

第一章一.填空题编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析与中间代码产生、优化和牛成目标程序等几个基本阶段，同时还伴有符号表管理和出错处理。若源程序是用高级语言编写的，目标程序是汇编或机器语言，则其翻译程序称为编译程序。编译方式与解释方式的根本区别在于运行目标程序时的控制权在解释器而不是目标程序。翻译程序是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。对编译程序而言，输入数据是高级语言（源）程序，输出结果是低级语言（目标）程序。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称且标机。当把编译程序划分成编译前端和编译后端时，前端主要由与源语言有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于中间语言。描述词法规则的有效工具是词法分析器，通常使用语法分析器来描述语法规则，使用语义分析（与中间代码产生）器描述语义规则。二.综合题（该答案仅供参考）1、给出C语言编译程序对下面语句进行编译时从词法分析到目标代码生成5个分析阶段的分析过程。c=a+b*30;（1） 给出每个阶段的输入和输出代码或其它数据形式。（2） 给出符号表，说明在哪些阶段会对符号表进行填写或查找。（3） 编译过程是否进行了代码优化？若有，请指出优化之处，并给出属于哪种优化？答： 词法分析：出入源程序；输出识别出的记号流。c=a+b*30 id1=id2+id3*30语法分析器：输入记号流，构造句子结构；输出语法树。id330语义分析与中间代码生成：出入语法树，输出中间代码变量地址数值注：赋值阶段会对符号表进行填写或査找1.id10c（itr,30， ，t1）2.id24x（*，id3，t1,t2）3.id38y（+，id2，t2,t3）4.t11230（=，t3, ,id1）优化：1.（*，id3,30.0，t1）（+，id2，t1,id1）精简掉多余的复写传播目标代码：movid3，r2mulf#30.0,r2movid2,r1subr1,r2movr2,id1第二章一.填空题上下文无关文法包括以下四个组成部分：一组终结符号，一组韭终结符号，一个开始符号，以及一纟组产牛式。如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是二义文法。消除文法的二义性的方法主要有：改写二义文法为非二义文法；为文法符号规定优先顺序和结合规则。二简答题有文法G：E—E+E|E*E|(E)|id给出(id*id)+id的最左推导；Ef(E)—►(E+E)—►(E*E+E)f(id*E+E)f(id*id+E)—►(id*id+id)并给出该推导过程中的所有句型；见(1),把箭头去掉即可给出该文法的2个句子。1*1+12*2+2第二章一综合题给出书中P48图3.5中所示有限自动机的状态转换矩阵和五元式，并说明该有限自动机可识别可识别相继两个a或相继两个b的字构造与正规式(aIb)*a(aIb)或(011)*0(011)等价的状态最少的确定有限自动机。构造转换系统如下图所示。

正则式(aIb)*a(aIb)的转换系统(2)NFA确定化为DFA的过程如下表所示:IIaIb①[S,A,B]②[A,B,C]③[A,B]②[A,B,C]④[A,B,C,Z]⑤[A,B,Z]③[A,B]②[A,B,C]③[A,B]④[A,B,C,Z]④[A,B,C,Z]⑤[A,B,Z]⑤[A,B,Z]②[A,B,C]③[A,B]相应DFA的状态图如下所示正则式(aIb)*a(aIb)的DFA将DFA最小化：首先得到两个子集K1={1,2,3}和K2={4,5}由于状态1和状态3输入a都到达状态2,输入b都到达状态3,而状态2输入a到达状态4,输入b到达状态5,所以将K1分割成K11={1,3}和K12={2}

又由于状态4输入b到达K2,而状态5输入b到达K11,所以状态4、5是可分的。这样，将原状态集合分割成以下子集：{1,3}，⑵，⑷，{5}所以最小化DFA的状态图如下所示，*(0|1)01*(0|1)01正则式(aIb)*a(aIb)的最小化DFA构造与正规式(a|ba)*等价的状态最少的确定有限自动机。TOC\o"1-5"\h\zi a b(x,1) (1,y) (1,2)(l,y) — —(1,2) (1,y) —4、P64:习题8(1)以01结尾的二进制数串(2)能被5整除的十进制整数(1|2|3H|5|6|7|8|9)(0|12|3|4|5|6|7|8|9)*(0|5)|(0|5)第四章&第五章&第七章一.填空题自上而下语法分析中存在的主要问题是由左递归引起的无限循环问题和左公共因子引起的无法确定产生式后诜项问题。自上而下语法分析的基本思想是，对任何输入串，从文法的开始符号，即根结点出发，自上而下地为输入串建立一颗语法树。递归下降分析器采用的是 语法分析方法。预测分析器模型是由总控程序(表驱动程序)，预测分析表和先进后出的语法分析栈组成,预测分析器是一种下推自动机。自下而上语法分析的基本思想是，从输入串开始，逐步进行归约，直至规约到文法的开始符号，即从语法树的末端开始，步步向上规约，直到叶结点为输入符号串。二、综合题.P81:习题1(1)消去文法中的左递归⑴按照T，S的顺序消除左递归(S)：S—(T)procedureS：beginifsyro二+a'orsym二'卜:thenadvanceelseifsym=J(1thenbeginadvance；T：ifsym二'1'thenadvance;elseerror:endelseerrorendprocedureT：begins；rEndProcedureT:BeginIfSJTD= ’ThenbeginAdvance;s；rEndEnd荘中；sysm7j愉入串扌号针所指的号；advance是把输入指针制至下--输入符号二.画出下面表达式的DAG(1)a+a*(b-c)+(b-c)*da=b*(-c)+b*(-c)状态状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5三.有文法G：E—E+TE—TT—T*FT—FF—(E)F—i书中P101图5.5是LR分析表，以下程序是驱动器算法,loops:=top";a:=ip";caseaction[s,a]isshifts':push(a);push(s');next(ip);reducebyA—p:pop(2*|BI);s':=top";push(A);push(goto(s'.A));accept:return;others:error;endcase;endloop完成表2中LR分析器利用LR分析表和驱动器对输入串i]*i2+i3进行分析的过程：写出栈中的内容和动作类型（移进或归约，若为移进请指出转向状态，若为归约请指出归约采用的产生式）2•若在语法分析同时进行语义分析，请在有语义翻译动作的步骤中标出。

表1文法G的LR分析表表2步骤栈内容当前输入移进-规约动作翻译动作1#i*i+i#移进#2#i*i+i#移进i3#F*i+i#规约F F—iVal[top]=lexval4#T*i+i#规约T T—FVal[top]=lexval5#T*i+i#移进*6#T*i+i#移进i7#T*F+i#规约F F—iVal[top]=lexval8#T+i#规约T T—F9#E+i#规约E E—T10#E+i#移进+11#E+ii#移进i12#E+F#规约F F—iVal[top]=lexval13#E+T#规约T T—FVal[top]二Val[top]+Val[top+2]14#E#规约E E—T•••••••••一.填空题1、属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程，对文法的每个产生式配备的一组属性的计算规则，叫语义规则，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算或其它语义动作（如査填符号表、产生中间代码、发布出错信息）就可进行语法制导翻译得到中间代码，这就是语法制导翻译的基本思想。_继承__属性用于“自上而下”传递信2、属性分为两类，综合属性用于“自下而上”传递信息,_继承__属性用于“自上而下”传递信第八章.填空题1、 线性查找是构造符号表最简单和最容易的办法，但查找效率很低，为了提高查找速度可以采用对折杳找和杂凑杳找杳找。2、 编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息，这些信息通常记录在一张或几张符号表中。第九章一.填空题1、不同的编译程序关于数据空间的存储分配策略会有所不同，静态分配策略在编译是对所有数据对象分配固定的存储单元，且在运行是始终保持不变；另外还可采用的分配策略是栈式动态分配策略和堆式动态分配策略。二简答题（仅供参考）1、 C语言的编译系统应该采用哪种存储分配策略，并简述理由。2、 Pascal语言的编译系统应该采用哪种存储分配策略，并简述理由。像Pascal和C语言，由于它们允许递归过程，在编译时刻无法预先确定哪些递归过程在运行时被激活，更难以确定它们的递归深度，而每次递归调用，都要为该过程中的每个数据对象分配一个新的存储空间。由上可见，它们的编译程序则不能采用静态分配策略，只能采用在程序运行时动态地进行分配（栈式分配）。又如Pascal和C语言，还允许用户动态地申请和释放存储空间，而且申请与释放之间不一定遵守先申请后释放或后申请先释放的原则，因此，需要采用一种更复杂的堆式动态分配策略。第十章一.填空题1、 代码优化可在编译的各阶段进行，其中主要的一类是在目标代码之前生成的，这类优化不依赖于具体的计算机。2、 代码优化可在编译的各阶段进行，有一类是在生成且标代码时进行的，这类优化在很大程度上依赖于具体的计算机。3、 窥孔优化是对目标代码进行局部改进的简单而有效的技术，一般可能需要对目标代码扫描若干次进行窥孔优化。二简答题1、简述编译过程中代码优化必须遵循的原则等价原则：经过优化后不应改变程序运行的结果；有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小；合算原则：应尽可能以较低的代价取得较好的优化效果。2、对中间代码中基本块的优化和循环优化都是与机器无关的代码优化，请各给出2-3种优化方法。代码外提强度消弱删除归纳变量（变换循环控制条件）第十一章二简答题1、 目标代码生成任务是什么？把语法分析后或优化后的中间代码变换成目标代码。2、 目标代码一般有哪几