编译原理习题.docx

《编译原理习题.docx》由会员分享，可在线阅读，更多相关《编译原理习题.docx（17页珍藏版）》请在第壹文秘上搜索。

1、试卷一一、是非题（以下各题，你认为正确的，请在题干的括号内打“，错的打“X”。每题1分，共5分）1、算符优先关系表不一定存在对应的优先函数。2、数组元素的地址计算与数组的存储方式有关。【）3、仅考虑一个根本块，不能确定一个赋值是否真是无用的。4、每个文法都能改写为LL（I）文法。5、对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。二、填空题（每题2分，共20分）1、从功能上说，程序语言的语句大体可分为语句和）语句两大类。2、扫描器的任务是从中识别出一个个L3、所谓最右推导是指：L4、语法分析最常用的两类方法是和分析法。5、一个上下文无关文法所含四个组成局部是L6、所谓语法制导翻译方

2、法是）。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、画

3、出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、Whilea0Vb0thena：

4、=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

5、,B还被引用，请写出优化后的四元序列。(6分)参考答案一.是非题1.2.3.4.5.二.填空题1 .执行性、说明性；2 .源程序、单词符号；3 .任何一步一B都是对中最右非终结符进行替换的；4 .自上而下、自下而上；5 .一组终结符号，一组非终结符号、一个开始符号、一组产生式；6 .为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序；7 .类型、种属、所占单元大小、地址；8 .现行活动记录地址和所有外层最新活动记录的地址；9 .栈式、堆式；10 .语法范畴。三.名词解释1 .遍一一指编译程序对源程序或中间代码程序从头到尾扫描一次。2 .无环路有向图(DAG)如果有向图中任一通路都

6、不是环路，那么称庐有向图为无环路有向图，简称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(

7、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

8、(5分)2、解：(1)S(L)aSssLSL,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)(j20GOTO(16)T1:=2*JT2:=20*1T3:=T1+T2T4:=addr（八）-22T5:=2*IT6:=T5*20T7:=2*JT8:=T6+

9、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