编译原理习题.docx

试卷一一、是非题（以下各题，你认为正确的，请在题干的括号内打“，错的打“X”。每题1分，共5分）1、算符优先关系表不一定存在对应的优先函数。2、数组元素的地址计算与数组的存储方式有关。【）3、仅考虑一个根本块，不能确定一个赋值是否真是无用的。4、每个文法都能改写为LL（I）文法。5、对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。二、填空题（每题2分，共20分）1、从功能上说，程序语言的语句大体可分为语句和）语句两大类。2、扫描器的任务是从中识别出一个个L3、所谓最右推导是指：L4、语法分析最常用的两类方法是和分析法。5、一个上下文无关文法所含四个组成局部是L6、所谓语法制导翻译方法是）。7、符号表中的信息栏中登记了每个名字的有关的性质，如等等。8、一个过程相应的DISPLAY表的内容为L9、常用的两种动态存贮分配方法是）动态分配和动态分配。10、产生式是用于定义的一种书写规那么。三、名词解释（每题2分，共10分）1、遍2、无环路有向图（DAG）3、语法分析4>短语5、后缀式四、简述题（每题4分，共24分）1、考虑下面程序Vara：integer；ProcedureS(X)；VarX：integer；Begina：=a+1；X：=a+XEnd；Begina：5；S（八）；Print（八）End.试问：假设参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？2、画出PaSCal中实数(不带正负号，可带指数局部)的状态转换图。3、写出表达式(a+b*c)/(a+b)d的逆波兰表示及三元式序列。4、文法G(三)SaAI(T),SlS写出句子(a,a),a)的标准归约过程及每一步的句柄。5、何谓优化？按所涉及的程序范围可分为哪几级优化？6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？五、计算题(共41分)1、写一个文法，使其语言是奇数集，且每个奇数不以O开头。(5分)2、设文法G(三)：S-(L)aSaLL,SlS(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。3、Whilea>0Vb<0doBeginX：=X+1；ifa>0thena：=a-1elseb：=b+lEnd；翻译成四元式序列。(7分)4、文法G(E)ETE+TTFT*FF-(E)Ii(1)给出句型(T*F+i)的最右推导及画出语法树；(2)给出句型(T*F+i)的短语、素短语。(7分)5、设布尔表达式的文法为E-E(I)VE(2)E-E(I)AE(2)E-i假定它们将用于条件控制语句中，请(1)改写文法，使之适合进行语法制导翻译和实现回填；(2)写出改写后的短个产生式的语义动作。(6分)6、设有根本块T1：=2T2：=10TT3：=S-RT4：=S+RA：=T2*T4B：AT5：=S+RT6：=T3*T5B：=T6(1)画出DAG图；(2)假设根本块出口时只有A,B还被引用，请写出优化后的四元序列。(6分)参考答案一.是非题1.2.3.4.×5.×二.填空题1 .执行性、说明性；2 .源程序、单词符号；3 .任何一步一B都是对中最右非终结符进行替换的；4 .自上而下、自下而上；5 .一组终结符号，一组非终结符号、一个开始符号、一组产生式；6 .为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序；7 .类型、种属、所占单元大小、地址；8 .现行活动记录地址和所有外层最新活动记录的地址；9 .栈式、堆式；10 .语法范畴。三.名词解释1 .遍一一指编译程序对源程序或中间代码程序从头到尾扫描一次。2 .无环路有向图(DAG)如果有向图中任一通路都不是环路，那么称庐有向图为无环路有向图，简称DAGo3 .语法分析一一按文法的产生式识别输入的符号串是否为一个句子的分析过程。4 .短语一一令G是一个文法。S划文法的开始符号，假定B是文法G的一个句型，如果有S-A且AB,那么称B是句型相对非终结符A的短语。5 .后缀式种把运算量写在前面，把算符写在后面的表示表达式的方法。四、1、答：传名：a=12(2分)传值：a=6(2分)3、逆波兰表示：abc*+ab+d-(2分)三元式序列：(*,b,c)(+,a,)(+,a,b)(/,，)(一,，d)（2分）4、答：句型归约规那么句柄(a,a),a)Saa(S,a),a)T-SS(T,a),a)Saa(T,S),a)TT,ST,S(三),a)TSS(T),a)SS(T)(T)(S,a)TSS(T,a)Saa(T,S)TT,ST,SS-(T)(T)S（4分）5、答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。（2分）三种级别：局部优化、循环优化、全局优化。（2分）6、答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。（2分）应着重考虑的问题：（1）如何使生成的目标代码较短；（2）如何充分利用存放器，以减少访问内存次数；（3）如何充分利用指仅系统的的特点。（2分）五、计算题：1、解:文法G(N)：NABBAACDBl3579DB2468COD(5分)2、解：(1)S(L)aS's's£LSL,L,SL,IFIRST)S)=(,aFIRST(S,)=,a,FIRST(L)=(,aFIRST(L,)=,，评分细那么：消除左递归2分，提公共因子2分。FOLLOW(三)=#,)F0LL0W(S,)=#,)FOLLOW(L)=)FOLLOW(L,)=)a,()#SSaS,S(L)s,s,ss,一S'-SS'一£S'-£LLSL,LSL,L,L'一£L'一£(3分)3、解:(j>,a,0,5)(j，一，一，3)(j<,b,0,5)(4)(j，一，一，15)(十,×,1,T1)(6)(：=,Tl，一,×)(j,a,0,9)(8)(j，一，一，12)(1,a,1,'2)(10)(：=,T2，一，a)(11)(j，一，一,1)(12)(十,b,1,T3)(13)(：=,T3，一，b)(14)(j，一，一,1)(15)评分细那么：控制结构4分，其它3分。4、解：(1)最右推导：ETF(E)(E+T)(E+F)(E+i)(T+i)(W+i)语法树：(2分)(2)短语：(T*F+i),T*F+i,T*F,i(2分)素短语：T*F,i(1分)5、解：(1)E0E(1)EEOE(2)EAE(1)EEAE(2)Efi(3分)(2)E-E(1)BACKPATCH(E(1)FC,NXQ)；EOTC：=E(1)TCEEOE(2)EFC：=E(2)FC；ETC：=MERG(EOTC,E(2)TC)EAE(1)BACKPATCH(E(1)TC,NXQ)；EOFC：=E(1)FCEEAE(2)ETC：=E(2)TC；EFC：=MERG(EAFC,E(2)FCEiETC：=NXQ；EFC：=NXQ+1；GEN(jn2,entry(i),O)；GEN(j,-,-,O)(3分)6、解：(l)DAG：略(3分)(2)优化后的四元式T3：=S-RT4：=S+RA：=5*T4B：=T3+T4(3分)东南大学1993编译原理试题一：（15分）判断以下命题的真假,并简述理由：1 .文法G的一个句子对应于多个推导,那么G是二义的.2 .LL（1）分析必须对原有文法提取左因子和消除左递归.3 .算符优先分析法采用移近-归约技术,其归约过程是标准的.4 .文法SaA;AAb;Ab是LR（0）文法（S为文法的开始符号）.5. 一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码并立即执行之,而编译程序需产生中间代码及优化.二：（15分）设计一个最小状态有穷自动机,识别由以下子串组成的任意字符串.GO,GOTO,TOO,ON例如：Gotoongotoogoon是合法字符串.三：（15分）构造一个LL文法G,识别语言L:L=I为0,1上不包括两个相邻的1的非空串并证明你的结论.四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL.1 .写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言：Ai:二EEE+EIE*EI(E)Ii2 .利用加,乘法满足交换率这一性质，改良你的分析程序，以期产生比拟高效的目标代码.五：(15分)C为大家熟知的程序语言.LC的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如Printf).请指出其函数调用语句：f(argl,arg2,.,argn)翻译成的中间代码序列,并简述其含义.2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略.六：(20分)设有一个子程序的四元式序列为：x)z1Xz(×1:=177777777O234567891/(×z(×/(×/(×/(z(×/(/(×/(XifI>20GOTO(16)T1:=2*JT2:=20*1T3:=T1+T2T4:=addr（八）-22T5:=2*IT6:=T5*20T7:=2*JT8:=T6+T7(11) T9:=addr（八）-22(12) T10:=T9T8(13) T4T3:=T10+J(14) 1:=1+1(15) goto(2)(16) ret1 .分划根本块.2 .对代码施行各种可能的优化,并写出优化过程中采用了何种优化策略.东南大学1995编译原理试题一:按算法构造文法Gl:S三ttMf(LIaLM,a)的算符优先矩阵.(即填写以下矩阵)二:将以下Cfg文法修改成正规文法.S-ABAMNPBaBIaMfbMlbNcNcPPI三:文法G2:(1) S'-S(2) SAAA(3) S1A(4) S01 .列出LR(O)工程集族；2 .构造SLR分析表；3 .试给处语句OIlo0#的LR分析过程.四：1 .构造由以下三型文法G3所对应的FA.2 .将构造的FA确定化和最小化.3 .写出该DFA所识别的语言.G3:SaAbSdCAdECaDbCbDbEbEaDbEb五:设有源语句AI+1,J+2:=ABK+2,51 .列出计算两个数组的下标地址(按行存放)AI+1,J+2的地址Dl=?BK+2的地址D2=?2 .按语法制导翻译该语句成四元式序列.(设数组首地址分别为a,b;数组按行存放,每个元素占一字编址.数组说明:A:array1.10,-5.5,B:array-5.5)六:求文法G4:ABCcIgDBBbcDECDabICaDdD£EgAfIc的各非终结符的随符集.七：1 .简述由根本块寻找循环结点的算法.2 .对于如下一段程序,假设参数传递分别采用：传名(b)传结果(C)传地址试问程序执行结果,Y值是什么？procQ(B,C)beginB:=B+2;B:=B*Cend;beginY:=2;Q(Y,2*Y);print(Y)end;3.文法G5:EPtEPPP*QlQQQ+RRR(E)aa一整常数试给出以下表达式计值结果(语法制导).3+2*5t2*2+32+(2t2t3)*2+3东南大学1996编译原理试题试题编号：553试题名称:编译原理1 .试写一正规文法,使其定义的语言是不以0打头的偶整数集合.其中数字可以用简名表示，比方l02416I8,并把1看作是终结符.2 .试写一上下文无关文法,它能产生以下语言：L=Ia,b*,且中a的个数是b的两倍,例如aab等二:请写出由以下文法所确定的语言.1. Gl:S1OSO1S-aAAbAAa2. G2:SaSSSa三:NFA的状态转换图如下,试对它确定化并化简,并写出该FA接受的语言.ba-S>AdIIcIabIb<C>D>E>bIbII四：文法G4:S,SS-ASSbASAAa1 .试求closure(S'-S,#)和GO(closure(S'-S,#),S)2 .文法是LR吗?为什么？五:试将下面语句按语法制导翻译成四元式序列.while(a<c)and(b<d)doifa=lthenc:=c+lelsewhilea<=ddoa:=a+2;六：1 .试对如下四元式序列划分成根本块,并化出程序流图;2 .写出源语句.12345/(/(/(/(/(X1:=1ifI>Mgoto(19)J：=lifJ>Ngoto(17)T1:=I*N(6)T2:=T1+JT3:=addr（八）-C(8)T4:=I*2T5:=J+2(10)T6:=T4*N(11)T7:=T6+T5(12)T8:=addr（八）-C(13)T9:=T8T7(14)T3T2:=T9(15)J：=J+1(16)goto(4)(17)1:=1+1(18)goto(2)(19)七：1 .求文法G7的各非终结符的终结首符集First和随符集Follow.2 .判定该文法是LL(I)吗？G7:ABCcIgDBBbCDEICDaBICaDdDEgAfIc东南大学1998编译原理试题一:文法Gl:SaBI£BbCbDCcBIcDd1 .试构造一个最小DFA,画出状态转换图.2 .由该DFA给出它所识别的语言（用正规式表示）.二：正规式=ab*c*d,1 .试构造一个DFAM,其接受的语言为此（画出图）；2 .由该DFAM写出对应的正规文法（古线性）.三:文法G3:SABABIAaB-a1 .求出各非终结符N的Firstvt（N）和Lastvt（N）,构造包括语句括号在内的算符优先表;2 .给出语句#Wa#的算符优先分析过程,即填写如下格式的表：步骤I栈内I输入串I动作四：文法G4:TWFF-Ii1 .试给出语句（i*i）#的自上而下分析过程（填下表）;2 .画出对应的语法树,指出每一步归纳的句柄.步骤I栈内I输入I动作五:文法G5:O.E'-E1. EE+T2. ET3. Ti列出LR（O）工程集标准族,求出各非终结符N的Follow集合,构造SLR分析表.六:翻译如下语句成四元式序列（由语法制导生成）.whilea>banda<ddoifa=5thenb:=b+lelserepeata:=a+luntila>=d;七:按语法制导翻译下段程序成四元式序列(不要优化)，设数组A:array1.10,1.Wofint;每个下标变量占1字编址,数组按行存放,Z为函数名.beginAi,j:=Ai,j+2;B:=Z(Ai,j)*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除根本归纳变量)，写出优化后的四元式序列.(要求先划分根本块)(1)i：=l(2) ifi>100goto(10)(3) Tl:=20*i(4) M:=J+T1(5) T2:=20*i(6) N:=K+T2(7) 0:=M+N(8) i:=i+l(9) goto(2)(10) .九:如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如以下图所示,数据区从k单元开始编址.programfactoral;函数返回值varnum,fact:int;functionf(n:int):int变量单元ifn>0thenf:=n*f(n-l)elsef:=1;display表beginread(num);形参单元fact:=f(num)end返回地址基SP1999年L10分构造一个DFA,它接受=0,1上0和1的个数都是偶数的字符串。2.5分现有句型5和产生式力-5,分别指出LL1方法和LR1方法在扫描到此句型的什么位置决定用此产生式？3.115分)在PASCAL语言中，简单类型的变量的声明例举如下：m,n:integerp,q,r:real为这样的声明写一个LR1文法为简单起见，变量标识符都用id表示，并根据你的文法写一个语法制导定义或叫做为你的文法加上语义动作，它将变量的类型填入符号表。4 .5分下面的PASCAL程序在VAX机器上运行时，报告存储访问错，为什么？programstrange(output);varp:integer;beginp:=nil;if(pOnil)and(p=10)thenwritein(10)elsewritein(rnothing，)end.5 .10分PASCAL语言和C语言都是栈式分配的语言。它们在语言构造上的哪些区别，使得C语言允许一函数的返回值类型是函数类型实际是函数指针类型)，而PASCAL语言不允许。6 .5分代码优化中的强度削弱是什么意思，举一例加以说明2001年编译原理试题L10分处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。2 .10分为语言L=ambnI0m2n)即a的个数不超过b的个数的两倍)写一个LR1文法，不准超过6个产生式。假设超过6个产生式，不给分。假设所写文法不是LR1文法，最多给5分。3 .10分构造下面文法的LL1分析表。DTLTfintIrealLidRR,idRI4 .15分就下面文法S(L)aLL,SIS给出一个语法制导定义，它输出配对括号的个数。给出一个翻译方案，它输出每个a的嵌套深度。如句子(a,(a,a),第一小题的输出是2,第二小题的输出是122。5 .10分PaSCaI语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。6 .5分一个C语言程序如下：func(il,i2,i3)longil,i2,i3;longjl,j2,j3;printf(zzAddressesofil,i2,i3=%o,%o,%onzz,&il,&i2,&i3);printf(zzAddressesofjl,j2,j3=%o,%o,%onzz,&jl,&j2,&j3);)main()longil,i2,i3;func(il,i2,i3);)该程序在某种机器的Linux上的运行结果如下：Addressesofil,i2,i3=27777775460,27777775464,27777775470Addressesofjl,j2,j3=27777775444,27777775440,27777775434从上面的结果可以看出，func函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。7.115分)一个C语言程序及其在某种机器IinUX操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。staticlongaa=10;shortbb=20;func()staticlongcc=30;shortdd=40;.filestatic.c.version01.01gcc2compiled.:.data.align4.typeaa,©object.sizeaa,4aa:.long10.globlbb.align2.typebb,©object.sizebb,2bb:.value20.align4.typecc.2,©object.sizecc.2,4cc.2:.long30.text.align4.globlfunc.typefunc,©functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp).L1:leaveret.Lfel:.sizefunc,.Lfel-func.identzzGCC:(GNU)egcs-2.91.6619990314/Linux(egcs-release)/z8.10分C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。9.110分)如果在A机器上我们有C语言编译器CQ,也有它的源码S用C语言写成)。如何利用它通过尽量少的工作来得到B机器的C语言编译器CC,O10.5分表达式(x.(yz.(x+y)+Z)3)45和(x.(yz.(x+y)+z)35)4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？2001年编译原理试题参考答案1.2.LR1文法LR文法二义文法SABIaABbSABSAASbIATaaAbAfaaAbabA>aIBBbIBBbI3.intrealid,$DDTLDTLTTintTrealLLidRRRfidRR4.S'fSprint(S.num)S(L)S.num:=L.num+1SaS.num:=0L>Li,SL.num:=Li.num+S.numLSL.num:=S.numSfTS.depth:二0SSTL.depth:=S.depth+1(L)Sfaprint(S.depth)LTL.depth:=L.depthLi,S.depth=L.depth)SLS.depth:=L.depth)S5 .ti:=initialt2:=finalifti>t2gotoLlv:=tiL2:stmtifv=t2gotoLlv:=v+1gotoL2LI:6 .由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。7 .aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区由.data伪指令开始，但是bb由伪指令globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。CC是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于CC在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为防止同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了CC.2。由于CC不是全局的，因此。.2前面没有伪指令.81北1。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。8 .例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。unionUintul;int*u2;u;int*p;u.ul=10;P=u.u2;*p=0;9.修改源码S的代码生成局部，让它产生B机器的代码，称结果程序为将金提交给CQ进行编译，得到一个可执行程序。将金提交给上述可执行程序进行编译，得到所需的编译器CC6。10.第一个表达式在执行yz.(x+p)+Z)3时出现参数个数缺乏的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数缺乏，又把它做成FANVAL的情况。而第二个表达式执行的是(yz.(x+力+z)35,不会出现参数个数缺乏的情况。因此第二个表达式的执行效率比第一个表达式的高。