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

一、填空问题(每天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 .正规式M 1和M 2等价是_C_。A. M1和M2状态数相等的B. M1和M2的有向边的条数相等C. M1和M2识别语言集，D. M1和M2的状态数与有向边数相等3 .语法g :用G:SxSx|y识别的语言是_C_。a.xy xrb.(xyx ) * c.xnyxn (n0 ) d.x * yx *4 .如果句法g不是双义的，那么句子_ a _ _ _ _ _ _ _ _ _ _ _ _ _ _ _a .与最左导出和最右导出对应的语法树必定是相同的b .与最左导出和最右导出对应的语法树有可能不同c .最左和最右导出可能总是具有相同的d.2个不同的最左导出，但是其对应的语法树是相同的5 .结构编译器必须把握_D_。a .源程序b .目标语言c .编译方法d .以上三个6 .四元式之间的联系是通过_b_实现的。a .指示器b .临时变量c .符号表d .程序变量7 .式(； ab)(cd )的反波兰是_ _ _ _ _ _ _ _ _ _ _ _ _ _a.222222222222222222000国际航空8 .优化可以生成_D_的目标代码。a .运行时间短b .占用存储容量小c .执行时间短，但使用存储器容量大d .执行时间短，使用存储器容量小9 .以下_ _ _ _ _ _ _ _ _优化方法不是为了循环优化。a .强度变弱的b .删除归纳变量的c .删除多馀的运算的d .代码外出10 .编译器使用区分_B_标识符的范围。a .描述标识符的过程或函数名称b .描述标识符的过程或函数的静态层次c .描述标识符的过程或函数的动态层次d .标识符的行号三、判断问题(正确打，错误打，每小题一分，共十分)2 .有限状态机器人中，唯一的终结状态。 x3 .运算符优先语法的非终结符之间也可能存在优先关系。 x4 .语法分析时，首先要消除语法中的左递归。 x6 .反波兰表示法在表示表达式时无需使用括号。 r9 .两个正规集合相等的必要条件是他们对应的正规式等价。 x1 .编译器执行高级语言程序的编译。 x2 .有限状态机器人中，唯一的初始状态。 r3 .运算符优先语法的非终结符之间没有优先关系。 r4 .在4.LL(1)语法分析中，首先必须消除语法中的左递归。 r5.LR分析法从左到右扫描输入列可以发现错误，但不能正确指出错误的地方。 r6 .在反波兰表达式中表示表达式时，表达式使用括号。 x7 .静态数组的存储区可在编译时确定。 x8 .在进行代码优化时，必须重视循环代码的优化。 这对提高目标代码的效率有更大的作用。 x9 .两个正则集相等的要求是它们生成的符号串是相同的。 r10 .语义子程序描述与语法相对应的翻译工作。 x1 .什么是s属性语法？ 什么是l属性语法？ 有什么关系呢？S-属性语法是只包含统一属性的属性语法。 (2分)L-属性语法要求每个生成表达式ax1x2.xn具有每个语义规则的每个属性或综合属性或Xj的继承属性，该属性仅依赖于(1)生成式Xj的左边符号X1、X2Xj-1的属性(2) A的继承属性。 (2分)s属性语法是l属性语法的特例。 (1分)什么是LL(1)分析器什么是LR(0)分析器所谓LR(0)分析，是从左向右扫描来自底向上进行语法分析，在分析的各个步骤中，只要根据分析堆栈当前移动而预约的全部语法符号，最多向前看0个输入符号，就能够判断针对某个生成式的左部符号的句柄是否形成在分析堆栈的上部五、综合问题(共40分)1.(十分)语法GS :S 1A | 0B | A 0S | 1AA B 1S | 0BB请写一篇关于(三点) GS的三句(4分钟)符号串11A0S是G S的句型吗？ 证明你的结论吧。关于(3点) G S，试制了001B的语法树。答案：(1)3个0和1的数量相等的列(每点)(2) S=1A=11AA=11A 0S(3)2.(10分钟)设置语言l=| 0，1 ，不以0开头，但以00结尾。2 3点)试制记述l的正则表达式(7点)构造识别l的DFA (要求详细的程序，描绘构造过程中的NFA、DFA的状态转移图和最小DFA的状态转移图) 。答案：(1 )(3分钟)正则表达式：1(0|1) * 00(2 )(7分钟)第1步(3分钟):将正则表达式转换为NFA。步骤2(2分钟) :将NFA确定为DFA:(1分钟)状态输入I 0I 1t.t01SA，d，Bq 0q 1A，d，BD，b，CD，B重命名q 1q 2q 3D，b，CD，b，c，ZD，Bq 2q 4q 3D，BD，b，CD，Bq 3q 2q 3D，b，c，ZD，b，c，ZD，Bq 4q 4q 3DFA的状态转移图(1点)步骤3(2分钟) :最小化DFA (1分钟)将状态分为终止状态和非终止状态两个集合： A=q0，q1，q2，q3，E=q4根据a、e集合的情况，分割a集合状态输入I 0I 1q0a.aq1.q1a.aa.aq2ea.aq3.q3a.aa.a将状态集a分为A=q0，q1，q3、B=2两个集根据a、b集合的情况，分割a集合状态输入I 0I 1q0a.aq1.q1乙组联赛a.aq3.q3乙组联赛a.a将状态集a分为A=q0、C=q1、q3两个集根据a、c集合的情况，分割c集合状态输入I 0I 1q1.q1乙组联赛a.aq3.q3乙组联赛a.a最小DFA的状态转移图(1点)3.(20分钟)给定的语法GE :E E T | TT T*F | FF (E) | i这个语法是LL(1)语法吗(要求详细的步骤，如果是LL(1)的话给分析表)a:(1)该语法不是LL(1)语法。 因为有左递归，所以消除左递归的话就能得到LL(1)语法(2点)(2)消除左递归，得到新的语法(3分)eteete|tftt* ft|F (E) | i(3)求出生成式右部的First集(2.5分钟)first (te)=first (t )=first (f )=，ifirst (te)= first (ft)=first (f )= (，ifirst (* 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 (ete)=first (te)= (，iselect (ete)=first (te)= select (e)=follow (e)= $，select (tft)=first (ft)= (，iselect (t* ft=first (* ft)= * select (t)=follow (t)= $，) Select(F (E)=First(E)=(Select(F i)=First(i)=i(6)对于相同左部的所有Select求交叉点(2.5分钟)。select (ete)22222222222222222222select (t* ft)2222222222222222222select(f(e)2222222航空航空航空因此，被改造的语法是LL(1)语法，其分析表如下(7) LL(1)分析表(5点)V N电视*I(中所述情节，对概念设计中的量体体积进行分析美元eeteeteeeteeet.ttfttftttt* ftttf.fF (E )F i1.(十分)关于语法g :SaSbS|aS|d证明这个语法是二义语法。a :语法在某句子中有多个语法解析树时，把这个语法称为二义语法。 (5分)句子aadbd有2棵语法树(5分钟，抽1棵树3分钟)。 下图： (6点)sa.assa.a乙组联赛sd.dd.dd.dssa.a乙组联赛ssa.ad.d(1) (2)由此可知，用SaSbS|aS|d定义的语法是二义语法。3.(20分钟)简单算术语法GE :E E T | TT T*F | FF (E) | i这个语法是SLR(1)语法吗(要求详细的过程，如果是SLR语法的话提示分析表)答案：(1)该语法的扩展语法为(2分)ee (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分钟)中所述情节，对概念设计中的量体体积进行分析(