山东交通学院成人本科学历《编译原理》复习导学资料

《编译原理》（A）复习题一、填空题（每小题5分，共计45分）1．如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：编译，和运行。2．对编译程序而言，输入数据是源程序，输出结果是目标代码。3．一个上下文无关文法G包括四个组成部分，依次为：一组非终结符，一组终结符，一个开始符，以及一组产生式。4．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法又称为正规文法。5．算符优先分析法每次都是对最左素短语进行规约。6.不同的编译程序，有不同的存储组织方式与分配方案。在大部分的现有编译程序中采用的方案主要有以下两种：静态存储方案和动态存储方案。二、选择题（每个选项2分，共计20分）题号12345678答案BCCADC(1)B(2)A(3)CD1．一个语言的文法是B。A．惟一的B．不惟一的C．个数有限的2．如果一个正规表达式所代表的集合是无穷的，则它必含有的运算是C。A．连接运算“•”B．或运算“|”C．闭包运算“*”D．括号“（”和“）”3．一个句型中的最左C称为该句型的句柄。A．短语B．素短语C．简单短语D．终结符号4．在递归子程序方法中，如果文法存在左公因子，则会使分析过程产生A。A．回溯B．非法调用C．有限次调用D．无限循环5．表达式-a+b*(-c+d)的逆波兰式是D。A．ab+-cd+-*B．a-b+c-d+*C．a-b+c-d+*D．a-bc-d+*+6．动态存储分配时，可以采用的分配方法有C。（1）以过程为单位的栈式动态存储分配（2）堆存储分配（3）最佳分配方法A．（1）B．（2）C．（1）（2）D．（1）（2）（3）7．对于下面的程序：procedurep(x,y,z);beginy:=y+2;z:=z+xend;begina:=4;b:=5;p(a+b,a,a);printaend;若参数传递的办法分别为：（1）传名，（2）传地址，（3）传值，那么程序执行时所输出的a分别是（1）B（2）A（3）C。A．15B．17C．4D．138．优化的目的是生成D的目标代码。A．运行速度较快B．运行速度快但占用内存空间大C．占用存储空间较少D．运行速度快且占用存储空间少三、（7分）现有文法G(E)：EET＋|TTTF*|FFF↑|a其中E是文法的开始符号。求出句型FF↑↑*的短语、简单短语和句柄。解答：短语有：F,F↑,F↑↑,FF↑↑*简单短语有：F,F↑句柄为F四、（7分）有文法G(A)=（{a,d,e},{A,B},A,P），其中P：AaABe|BaBdB|ε试计算文法的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)文法。解答：FIRST(A)={a,d}FIRST(B)={d,ε}FOLLOW(A)={$,d}FOLLOW(B)={a,e}因为FIRST(aABe)∩FIRST(Ba)=φFIRST(dB)∩FIRST(ε)=φFIRST(dB)∩FOLLOW(B)=φ符合LL(1)文法条件，所以该文法是LL(1)文法。五、（7分）将下面的NFA确定化后画出状态转换图。解答：由子集法构造DFA如表所示：IIaIb{S,3,1}{3,1,5}{3,1,6}{3,1,5}{3,5,2,1,4,Z}{3,1,6}{3,1,6}{3,1,5}{3,6,2,1,4,Z}{3,5,2,1,4,Z}{3,5,2,1,4,Z}{3,6,4,1,Z}{3,6,2,1,4,Z}{3,5,4,1,Z}{3,6,2,1,4,Z}{3,6,4,1,Z}{3,5,4,1,Z}{3,6,2,1,4,Z}{3,5,4,1,Z}{3,5,2,1,4,Z}{3,6,4,1,Z}换名后DFA的映像：IIaIb012132214335464564635所构造的DFA相应的状态图如下：六、（7分）设有文法G(S)：SS（S）Sε（1）构造识别文法规范句型可归前缀的DFA。（2）这个文法是LR（0）的吗？请说明理由。解答：（1）先构造增广文法：S’S0SS(S)1Sε2文法的识别规范句型可归前缀的DFA如图（2）该文法是LR(0)文法。这是因为，在识别可归前缀DFA的状态中，只有一个状态I1有移进－归约“冲突”，但是此状态中的归约项目实际上是接受项目，在构造分析表时不会产生冲突。所以，该文法是LR(0)项目。（7分）写出语句

ifx+1>ytheny:=x+1elsewhilex<y+1dox:=x+1的四元式序列。解答：100（+,x,1,t1）101(j>,t1,y,103)102(j,_,_,106)103(+,x,1,t2)104(:=,t2,_,y)105(j,_,_,112)106(+,y,1,t3)107(j<,x,t3,109)108(j,_,_,112)109(+,x,1,t4)110(:=,t4,_,106)111(j,_,_,106)112《编译原理》（B）复习题一、填空题（每小题2分，共计20分）1．若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。2．文法G产生的句子的全体是该文法描述的语言。3．编译过程中词法分析所完成的任务是从源程序中识别出一个个具有独立意义的单词。4．基本块内可以进行的优化是合并已知量，找出公共表达式和去除无用赋值。5．一个句型中的最左简单短语称为该句型的句柄。二、选择题（每小题3分，共24分）题号12345678答案ACACCBCB1．编译程序必须完成的工作有A。（1）词法分析（2）语法分析（3）语义分析（4）代码生成（5）中间代码生成（6）代码优化A．(1)(2)(3)(4)B．(1)(2)(3)(4)(5)C．(1)(2)(3)(4)(5)(6)D．(1)(2)(3)(4)(6)2．LL（1）文法的条件是C。A．对形如Ux1|x2|……|xn的规则，要求FIRST(xi)∩FIRST(xj)≠φ(i≠j)B．对形如Ux1|x2|……|xn的规则，若xiε，则要求FIRST(xj)∩FOLLOW(U)=φC．a和bD．都不是3．若a为终结符，则Aα·aβ为A项目。A．移入B．待约C．规约D．接受4．动态存储分配时，可以采用的分配方法有C。（1）以过程为单位的栈式动态存储分配（2）堆存储分配（3）最佳分配方法A．（1）B．（2）C．（1）（2）D．（1）（2）（3）5．运行阶段的存储组织与管理的目的是C。（1）提高编译程序的运行速度（2）提高目标程序的运行速度（3）为运行阶段的存储分配作准备A．（1）（2）B．（1）（3）C．（2）（3）D．（1）（2）（3）三、（14分）对文法G=(VT,VN,S,P)：VT＝{a,b}，VN＝{S,A,B}，开始符号为SP：SaB|bAAaS|bAA|aBbS|aBB|b给出串aaabbabbba的（1）最左推导；（2）最右推导；（3）推导树。解答：（1）最左推导为：S==>aB=>aaBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB=>aaabbabbS=>aaabbabbbA=>aaabbabbba（2）最右推导为：S==>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>aaabbabbba（3）推导树为：四、（14分）给出文法G（S）={（a,b,c），（S,P,Q），S，P}，P：SaSb|PPbPc|bQcQQa|a文法消除左递归、提取公因子后是不是LL（1）文法？请证实之。解答：文法消除左递归、提取公因子后变为SaSb|PPbRRPc|QcQaQ’Q’aQ’|ε因为对规则SaSb|P，有FIRST(aSb)∩FIRST(P)=φ对规则RPc|Qc，有FIRST(Pc)∩FIRST(Qc)=φ对规则Q’aQ’|ε，有FIRST(aQ’)∩FOLLOW(Q)=φ所以文法消除左递归、提取公因子后是LL（1）文法。五、（14分）设有文法G(S)：SAAaAbAaAdAε（1）构造识别文法规范句型可归前缀的DFA。（2）说明文法G是否为SLR（1）文法，为什么？解答：（1）先构造增广文法：S’S0SA1SaAb2SaAd3Aε4文法的识别规范句型可归前缀的DFA如图：（2）该文法是SLR(1)文法。这是因为既不存在“移进-规约”冲突，也不存在“规约-规约”冲突。六、（14分）把下面语句翻译成四元式序列。if(x>0)and(y>1)thenz:=x+yelsebeginx:=x+2;y:=y+3;end;解答：100(j>,x,0,102)101(j,_,_,107)102(