编译原理期末试题

第1页共6页《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。(×)2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)3．一个算符优先文法可能不存在算符优先函数与之对应。(√)4．语法分析时必须先消除文法中的左递归。(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)6．逆波兰表示法表示表达式时无须使用括号。(√)7．静态数组的存储空间可以在编译时确定。(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)9．两个正规集相等的必要条件是他们对应的正规式等价。(×)10．一个语义子程序描述了一个文法所对应的翻译工作。(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1．词法分析器的输出结果是_____。A．()单词的种别编码B．()单词在符号表中的位置C．()单词的种别编码和自身值D．()单词自身值2．正规式M1和M2等价是指_____。A．()M1和M2的状态数相等B．()M1和M2的有向边条数相等C．()M1和M2所识别的语言集相等D．()M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。第2页共6页A．()xyxB．()(xyx)*C．()xnyxn(n≥0)D．()x*yx*4．如果文法G是无二义的，则它的任何句子α_____。A．()最左推导和最右推导对应的语法树必定相同B．()最左推导和最右推导对应的语法树可能不同C．()最左推导和最右推导必定相同D．()可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。A．()源程序B．()目标语言C．()编译方法D．()以上三项都是6．四元式之间的联系是通过_____实现的。A．()指示器B．()临时变量C．()符号表D．()程序变量7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。A.()┐AB∨∧CD∨B．()A┐B∨CD∨∧C．()AB∨┐CD∨∧D．()A┐B∨∧CD∨8.优化可生成_____的目标代码。A．()运行时间较短B．()占用存储空间较小C．()运行时间短但占用内存空间大D．()运行时间短且占用存储空间小9．下列______优化方法不是针对循环优化进行的。A.()强度削弱B．()删除归纳变量C．()删除多余运算D．()代码外提10．编译程序使用_____区别标识符的作用域。第3页共6页A.()说明标识符的过程或函数名B．()说明标识符的过程或函数的静态层次C．()说明标识符的过程或函数的动态层次D.()标识符的行号三、填空题(每空1分，共101.优化可生成运行时间短且占用存储空间小的目标代码2.LR分析法解决“移进-规约”冲突时，右结合意味着建立联系实行移进3.若B为非终结符，则A→a.Bb为待约项目4.在目标代码生成阶段，符号表用于数据存储分配的依据5.四元式之间的联系是通过临时变量实现的1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。5．后缀式abc-/所代表的表达式是___a/(b-c)__。6．局部优化是在__基本块___范围内进行的一种优化。三、对于文法G(E):(8分)ET|E+TTF|T*FF(E)|i1.写出句型T*F+i1*i2的最右推导并画出语法树。2.写出上述句型的短语，直接短语、句柄、素短语和最左素短语答：1.E=E+T=E+T*F=E+T*i2=E+F*i2=E+i1*i2=T*F+i1*i22.短语：T*F+i1*i2,T*F,i1*i2,i1,i2直接短语：T*F,i1,i2句柄：T*F素短语：T*F,i1,i2最左素短语：T*F第4页共6页3.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。解：wab+cde10-/+8+*+《编译原理》期末试题（二）一、是非题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。()2.一个句型的直接短语是唯一的。（）3.已经证明文法的二义性是可判定的。（）4.每个基本块可用一个DAG表示。（）5.每个过程的活动记录的体积在编译时可静态确定。（）6.2型文法一定是3型文法。（）7.一个句型一定句子。()8.算符优先分析法每次都是对句柄进行归约。X()9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。()11.一个优先表一定存在相应的优先函数。X()12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()13.递归下降分析法是一种自下而上分析法。()14.并不是每个文法都能改写成LL(1)文法。()15.每个基本块只有一个入口和一个出口。()16.一个LL(1)文法一定是无二义的。()17.逆波兰法表示的表达试亦称前缀式。()18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()19.正规文法产生的语言都可以用上下文无关文法来描述。()20.一个优先表一定存在相应的优先函数。()21.3型文法一定是2型文法。()22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。()第5页共6页答案：1.×2.×3.×4.√5.√6.×7.×8.×9.√10.×11.×12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√二、填空题：2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。5.语法分析器的输入是（单词符号），其输出是（语法单位）。6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。29.局限于基本块范围的优化称（局部优化）。31.2型文法又称为（上下文无关）文法；3型文法又称为（正则）文法。33.算符优先分析法每次都是对(最左素短语）进行归约。16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。16.逆波兰式:abcd-*e/+三元序列:oparg1arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)五、计算题：四、设文法G(S)：(12分)(|*)BB|BAAA|SiASA1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和优先函数。(12分)答：(6分)FIRSTVT(S)={i，+，)，(}FIRSTVT(A)={+，)，(}FIRSTVT(B)={)，(}LASTVT(S)={i，+，*，(}LASTVT(A)={+，*，(}LASTVT(B)={*，(}优先关系表:(3分)第6页共6页i+()*i+()*优先函数:(3分)i+()*f26616g14661。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化后的四元序列。6.优化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+209.已知文法G(S)S→aAcBeA→Ab|bB→d(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。9.(1)S=aAcBe=AAbcBe=abbcBe=abbcde(2)短语:aAbcde,Ab,d素短语:Ab,d10.设文法G(S):S→(T)|aS|aT→T,S|S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；第7页共6页⑶构造预测分析表。10.(1)S→(L)|aS’S’→S|εL→SL’L’→,SL’|ε(2)FIRST(S)={a,(}FIRST(S’)={a,(,ε}FIRST(L)={a,(}FIRST(L’)={,,ε}FOLLOW(S)={,,),#}FOLLOW(S’)={,,),#}FOLLOW(L)={)}FOLLOW(L’)={)}(3)()a,#SS→(L)S→aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’L’L’→ε12.已知文法G(S)E→E+T|TT→T*F|FF→(E)|i(1)给出句型(i+i)*i+i的最左推导及画出语法树；(2)给出句型(E+T)*i+F的短语，素短语和最左素短语。12.(1)E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(i+i)*i+F=(i+i)*i+i(2)短语i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F素短语i,E+T最左素短语E+T第8页共6页}《编译原理》期末试题（二）三、设有字母表{a，b}上的正规式R=(ab|a)*。解：（1）（2）将（1）所得的非确定有限自动机确定化εab-01131221+3（3）对（2）得到的DFA化简，合并状态0和2为状态2：（4）令状态1和2分别对应非终结符B和A给定文法G[S]：用子集法将NFA确定化：ab-+013123+12312313+1312312aab-++012aaba-+++0123baaεε-+第9页共6页将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。《编译原理》期末试题（五）一、单项选择题(共10小题，每小题2分，共20分)1．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合2．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语4．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型6．对应Chomsky四种文法的四种语言之间的关系是A．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L37．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码8．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树9．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换10．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体