编译原理期末考试题目及答案

一、填空题（每空2分，共20分）1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。2．编译器常用的语法分析方法有自底向上和自顶向下两种。3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。5．对编译程序而言，输入数据是源程序，输出结果是目标程序。1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。4．一个LL（1）分析程序需要用到一张分析表和符号栈。5．后缀式abc-/所代表的表达式是a/(b-c)。二、单项选择题（每小题2分，共20分）1．词法分析器的输出结果是__C。A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值2．正规式M1和M2等价是指__C_。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_C____。A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*4．如果文法G是无二义的，则它的任何句子α_A____。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。A．源程序B．目标语言C．编译方法D．以上三项都是6．四元式之间的联系是通过__B___实现的。A．指示器B．临时变量C．符号表D．程序变量7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。A．┐AB∨∧CD∨B．A┐B∨CD∨∧C．AB∨┐CD∨∧D．A┐B∨∧CD∨8.优化可生成__D___的目标代码。A．运行时间较短B．占用存储空间较小C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小9．下列___C___优化方法不是针对循环优化进行的。A.强度削弱B．删除归纳变量C．删除多余运算D．代码外提10．编译程序使用_B_区别标识符的作用域。A.说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次C．说明标识符的过程或函数的动态层次D.标识符的行号三、判断题（对的打√，错的打×，每小题1分，共10分）2．一个有限状态自动机中，有且仅有一个唯一的终态。x3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X4．语法分析时必须先消除文法中的左递归。X6．逆波兰表示法表示表达式时无须使用括号。R9．两个正规集相等的必要条件是他们对应的正规式等价。X1．编译程序是对高级语言程序的编译执行。X2．一个有限状态自动机中，有且仅有一个唯一的初始态。R3．一个算符优先文法的每个非终结符号间都不存在优先关系。R4．LL（1）语法分析时必须先消除文法中的左递归。R5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。R6．逆波兰表示法表示表达式时根据表达式会使用括号。X7．静态数组的存储空间可以在编译时确定。X8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。X9．两个正规集相等的必要条件是他们产生的符号串是相同的。R10．一个语义子程序描述了一个文法所对应的翻译工作。X1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？S-属性文法是只含有综合属性的属性文法。（2分）L-属性文法要求对于每个产生式AX1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2…Xj-1的属性；（2）A的继承属性。（2分）S-属性文法是L-属性文法的特例。（１分）２．什么是LＬ（１）分析器２．什么是LＲ（０）分析器所谓LR(０)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。五、综合题（共40分）1．（10分）对于文法G[S]：S→1A|0B|εA→0S|1AAB→1S|0BB⑴(3分)请写出三个关于G[S]的句子；⑵(4分)符号串11A0S是否为G[S]的句型？试证明你的结论。⑶(3分)试画出001B关于G[S]的语法树。答：（1）三个0和1数量相等的串（每个1分）（2）S=1A=11AA=11A0S（3）2.（10分）设有语言L={α|α∈{0,1}+，且α不以0开头，但以00结尾}。⑵３分）试写出描述L的正规表达式；⑵（７分）构造识别L的DFA（要求给出详细过程，并画出构造过程中的NFA、DFA的状态转换图，以及最小DFA的状态转换图)。答：（1）（３分）正规表达式：1(0|1)*00（2）（７分）第一步（３分）：将正规表达式转换为NFA第二步（２分）：将NFA确定化为DFA：（１分）状态输入I0I1t01[S]—[A,D,B]q0—q1[A,D,B][D,B,C][D,B]重新命名q1q2q3[D,B,C][D,B,C,Z][D,B]q2q4q3[D,B][D,B,C][D,B]q3q2q3[D,B,C,Z][D,B,C,Z][D,B]q4q4q3DFA的状态转换图（１分）第三步（２分）：将DFA最小化：（１分）将状态划分终态与非终态两个集合：Ａ＝｛ｑ０，ｑ１，ｑ２，ｑ３｝，Ｅ＝｛ｑ４｝根据Ａ、Ｅ集合的情况，对Ａ集合进行划分状态输入I0I1ｑ０—Ａｑ１ＡＡｑ２ＥＡｑ３ＡＡ将状态集Ａ划分为两个集合：Ａ＝｛ｑ０，ｑ１，ｑ３｝，Ｂ＝｛２｝根据Ａ、Ｂ集合的情况，对Ａ集合进行划分状态输入I0I1ｑ０—Ａｑ１ＢＡｑ３ＢＡ将状态集Ａ划分为两个集合：Ａ＝｛ｑ０｝，Ｃ＝｛ｑ１，ｑ３｝根据Ａ、Ｃ集合的情况，对Ｃ集合进行划分状态输入I0I1ｑ１ＢＡｑ３ＢＡ最小DFA的状态转换图（１分）３．（20分）给定文法G[E]：E→E+T|TT→T*F|FF→(E)|i该文法是LL(1)文法吗？（要求给出详细过程，如果是LL（1），给出分析表）答：（1）该文法不是LL（1）文法，因为有左递归，消除左递归可获得一个LL（1）文法（2分）（2）消除左递归，得新文法(3分)E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i(3)求产生式右部的First集(2.5分)First(TE’)=First(T)=First(F)={(,i}First(+TE’)={+}First(FT’)=First(F)={(,i}First(*FT’)={*}First((E))={(}First(i)={i}（4）求所有非终结符的Follow集(2.5分)Follow(E)={$,)}Follow(E’)=Follow(E)={$,)}Follow(T)=First(E’)∪Follow(E)={+}∪{$,)}={$,+,)}Follow(T’)=Follow(T)={$,*,)}Follow(F)=First(T’)∪Follow(T)∪Follow(T’)={$,*,)}（5）求所有产生式的Select集(2.5分)Select（E→TE’）=First(TE’)={(,i}Select（E’→+TE’）=First(+TE’)={+}Select（E’→ε）=Follow(E’)={$,)}Select（T→FT’）=First(FT’)={(,i}Select（T’→*FT’）=First(*FT’)={*}Select（T’→ε）=Follow(T’)={$,+,)}Select（F→(E)）=First((E))={(}Select（F→i）=First(i)={i}（6）对相同左部的所有Select即求交集(2.5分)Select（E’→+TE’）∩Select（E’→ε）=ΦSelect（T’→*FT’）∩Select（T’→ε）=ΦSelect（F→(E)）∩Select（F→i）=Φ所以，改造后的文法是LL（1）文法，其分析表如下（7）LL(1)分析表（5分）VNVT+*i()$EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→(E)F→i1．（10分）对于文法G：SaSbS|aS|d证明该文法是二义性文法。答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5分）句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图：（６分）(1)(2)由此可知，SaSbS|aS|d定义的文法是二义性文法。３．（20分）给定一个简单的算术表达式文法G[E]：E→E+T|TT→T*F|FF→(E)|i该文法是SLR(1)文法吗？（要求给出详细过程，如果是SLR文法，给出分析表）答：(1)该文法的拓广文法是：(2分)dSSabSSadSaSSabSddE’→E（1）E→E+T（2）E→T（3）T→T*F（4）T→F（5）F→(E)（6）F→i（7）（2）相应的LR（0）的DFA：（10分）（3）冲突与解决(3分）①I1状态中有移进—规约冲突Follow(E’)={$}不含{+}可解决移进—规约冲突②I2状态中有移进—规约冲突Follow(E)={+，），$}不含{*}可解决移进—规约冲突③I8状态中有移进—规约冲突)(FTI0:E’→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.iI1:E’→E.E→E.+TI2:E→T.T→T.*FEFI3:T→F.TI4:F→(.E)E→.E+TE→.TT→.T*FT→.FF→.(E)F→.i（iI6:E→E+.TT→.T*FT→.FF→.(E)F→.i+*（iiTI8:E→E+T.T→T.*F*I7:T→T*.FF→.(E)F→.iF（iI9:F→(E.)E→E.+TEI10:F→(E).+I5:F→i.FI11:T→T*F.Follow(E)={+，），$}不含{*}可解决移进—规约冲突(4)SLR分析表(5分)ACTIONGOTO+*i（）$ETF0S5S41231S6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、单项选择题（每小题2分，共20分）1．语言是____C_A．终结符与非终结符的符号串的集合B．非终结符符号串的集合C．终结符符号串的集合D．产生式的集合2．编译程序分两阶段工作，前阶段完成的工作是__C___A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左CA．句型B．短语C．直接短语D．最左直接短语4．自动机识别的语言是DA．0型语言B．1型语言C．2型语言D．3型语言5．自动机所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即BA．字符B．单词C．句子D．句型6．对应Chomsky四种文法的四种语言之间的关系是BA．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L37．词法分析的任务是AA．识别单词B．分析句子的含义C．识别句子D．生成目标代码8．常用的中间代码形式不含DA．三元式B．四元式C．逆波兰式D．