编译原理习题.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
