编译原理期末考试试卷及答案

第1页共14页一．填空题（每空2分，共20分）1.不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。2.规范规约是最（3）规约。3.编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。4．表达式x+y*z/(a+b)的后缀式为（7）。5．文法符号的属性有综合属性和（8）。6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。7．局部优化是局限于一个（10）范围内的一种优化。二．选择题（1-6为单选题，7-8为多选题，每问2分，共20分）1.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。A．字符串B．产生式C．开始符号D．文法2.程序的基本块是指（）。A．一个子程序B．一个仅有一个入口和一个出口的语句C．一个没有嵌套的程序段D．一组顺序执行的程序段，仅有一个入口和一个出口3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A．自左向右B．自顶向下C．自底向上D．自右向左4．在通常的语法分析方法中，（）特别适用于表达式的分析。A．算符优先分析法B．LR分析法C．递归下降分析法D．LL（1）分析法5．经过编译所得到的目标程序是（）。A．四元式序列B．间接三元式序列C．二元式序列D．机器语言程序或汇编语言程序6．一个文法所描述的语言是（）；描述一个语言的文法是（）。A．唯一的B．不唯一的C．可能唯一，也可能不唯一7．如果在文法G中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。A．其最左推导和最右推导相同B．该句子有两个不同的最左推导得分得分第2页共14页C．该句子有两个不同的最右推导D．该句子有两棵不同的语法树E．该句子对应的语法树唯一8．下面（）语法制导翻译中，采用拉链—回填技术。A.赋值语句B.布尔表达式的计算C.条件语句D.循环语句三．解答题（共60分）1．（共15分）已知文法G[E]:E→ETE|（E）|iT→*|+（1）将文法G改造成LL（1）文法；（5分）（2）构造文法G中每个非终结符的FIRST集合及FOLLOW集合；（5分）（3）构造LL（1）分析表。（5分）2．（共12分）给定文法G[S]：S→S(S)|ε（1）给出句子(()())()()的规范推导过程；（4分）（2）指出每步推导所得句型的句柄；（4分）（3）画出该句子的语法推导树。（4分）3．（共8分）在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。A→aB{print“0”；}A→c{print“1”；}B→Ab{print“2”；}（1）当分析器的输入为aacbb时，打印的字符串是什么？（3分）（2）写出分析过程。（5分）5．（共15分）设有表格构造文法G[S]：S→a|∧|(T)T→T,S|S(1)计算文法G[S]的FIRSTVT集和LASTVT集。（5分）(2)构造G[S]的优先关系表，并判断G[S]是否为算符优先文法。（5分）(3)计算G[S]的优先函数。（5分）得分第3页共14页二．单项选择题（每题2分，共10分）1.设有文法G[I]：I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（）。①ab0②a0c01③aaa④bc10可选项有：A．①B．②③④C．③④D．①②③④2.程序的基本块是指（）。A．一个子程序B．一个仅有一个入口和一个出口的语句C．一个没有嵌套的程序段D．一组顺序执行的程序段，仅有一个入口和一个出口3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A．自左向右B．自顶向下C．自底向上D．自右向左4．经过编译所得到的目标程序是（）。A．四元式序列B．间接三元式序列C．二元式序列D．机器语言程序或汇编语言程序5．运行阶段的存储组织与管理的目的是（）。①提高编译程序的运行速度②节省编译程序的存储空间③提高目标程序的运行速度④为运行阶段的存储分配做准备可选项有：A.①②B.②③C.③④D.④②2.（10分）已知文法G[S]:S→aBc|bABA→aAb|bB→b|ε（4）构造其LL（1）分析表；（5）判断符号串baabbb是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。答案：：(1)栈式动态存储分配(2)堆式动态存储分配(3)左(4)语法分析得分得分第4页共14页(5)目标代码生成(6)表格管理(7)xyz*ab+/+(8)继承属性(9)a+(i-1)*20+j-1(10)基本块一、选择题（每问2分，共20分）1.CB2.D3.B4.A5.D6.A,C7.BCD,选对一个得1分且不超过满分，选错一个扣一分，扣完为止。8.BCD，选对一个得1分且不超过满分，选错一个扣一分，扣完为止。二、解答题1．（1）文法存在左递归，消除左递归后的文法为：E→(E)E’|iE’（2分）E’→TEE’|ε（2分）T→*|+（1分）（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分FIRST(E)={(,i}FIRST(E’)={*,+,ε}FIRST(T)={*,+}FOLLOW(E)={),*,+,#}FOWLLOW(E’)={),*,+,#}FOLLOW(T)={(,i}（3）每错一个扣0.5分，全错或不写不得分，扣完为止，共5分()i*+#EE→(E)E’E→iE’E’E’→εE’→TEE’E’→εE’→TEE’E’→εE’→εTT→*T→+2．（1）规范推导过程如下。写错推导符号扣0.5分,错写或少写一步推导扣0.5分，扣完为止，最左推导扣2分，共4分。(()())()())())()()(()())()()((())()())(())()()(()()())((()())()()(())()()(SSSSSSSSSSSSSSSSSSSS（2）（1）中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣0.5分，扣完为止，共4分。（3）每少写步扣0.5分，扣完为止，共4分。SS(S))S(S)ε)第5页共14页3．（1）打印的字符串是：12020（错一个扣0.5分，共3分）（2）归约过程中错一步扣0.5分，扣完为止。（共5分）5．（1）少写一个扣1分，全错或不写不得分，共5分。FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={a,∧,),,}三、单项选择题（每题2分，共10分）1.B2.D3.B4.D5.C四、解答题（共70分）1．（1）L(G)={0m1m|M≥1}共2分，≥写成＞扣1分（2）S=0S1=00S11=000111，共3分，=写成-扣1分（3）共3分，错处扣0.5分，扣完为止一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。()2.一个句型的直接短语是唯一的。()3.已经证明文法的二义性是可判定的。（）4.每个基本块可用一个DAG表示。（）5.每个过程的活动记录的体积在编译时可静态确定。（）6.2型文法一定是3型文法。（）7.一个句型一定句子。()8.算符优先分析法每次都是对句柄进行归约。()9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。()11.一个优先表一定存在相应的优先函数。()12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()13.递归下降分析法是一种自下而上分析法。()14.并不是每个文法都能改写成LL(1)文法。()15.每个基本块只有一个入口和一个出口。()16.一个LL(1)文法一定是无二义的。()17.逆波兰法表示的表达试亦称前缀式。()S(S)ε)εS(S))S(S)ε)εε)第6页共14页18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()19.正规文法产生的语言都可以用上下文无关文法来描述。()20.一个优先表一定存在相应的优先函数。()21.3型文法一定是2型文法。()22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。()二、填空题：1.()称为规范推导。2.编译过程可分为（），（），（），（）和（）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。5.语法分析器的输入是（），其输出是（）。6.扫描器的任务是从（）中识别出一个个（）。7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。8.一个过程相应的DISPLAY表的内容为（）。9.一个句型的最左直接短语称为句型的（）。10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。11.一个名字的属性包括()和()。12.常用的参数传递方式有（），（）和（）。13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。15.预测分析程序是使用一张（）和一个（）进行联合控制的。16.常用的参数传递方式有（），（）和（）。17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。20.一个句型的最左直接短语称为句型的（）。21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。22.对于数据空间的存贮分配，FORTRAN采用()策略，PASCAL采用()策略。23.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是()。24.最右推导亦称为（），由此得到的句型称为（）句型。25.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。26.对于文法G，仅含终结符号的句型称为()。27.所谓自上而下分析法是指（）。28.语法分析器的输入是（），其输出是（）。29.局限于基本块范围的优化称（）。30.预测分析程序是使用一张（）和一个（）进行联合控制的。31.2型文法又称为（）文法；3型文法又称为（）文法。32.每条指令的执行代价定义为（）。33.算符优先分析法每次都是对（）进行归约。三、名词解释题：1.局部优化2.二义性文法3.DISPLAY表4.词法分析器5.最左推导6.语法7.文法8.基本块9.语法制导翻译10.短语11.待用信息12.规范句型13.扫描器第7页共14页14.超前搜索15.句柄16.语法制导翻译17.规范句型18.素短语19.语法20.待用信息21.语义四、简答题：1.写一个文法G,使其语言为不以0开头的偶数集。2.已知文法G(S)及相应翻译方案S→aAb{print“1”}S→a{print“2”}A→AS{print“3”}A→c{print“4”}输入acab,输出是什么？3.已知文法G(S)S→bAaA→(B|aB→Aa)写出句子b(aa)b的规范归约过程。4.考虑下面的程序：…procedurep(x,y,z)；beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A,A,B);PrintA,Bend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么?5.文法G(S)S→dABA→aA|aB→Bb|ε描述的语言是什么？6.证明文法G(S)S→SaS|ε是二义性的。7.已知文法G(S)S→BAA→BS|dB→aA|bS|c的预测分析表如下abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→c第8页共14页给出句子adccd的分析