编译原理试题库

一填空题1．编译程序首先要识别出源程序中每个，然后再分析每个并翻译其意义。单词，句子2．编译器常用的语法分析方法有和两种。自底向上，自顶向下2．通常把编译过程分为分析与综合两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。前端，后端4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即方案和分配方案。静态存储分配，动态存储5．对编译程序而言，输入数据是，输出结果是。源程序，目标程序6．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组，以及一个开始符号。产生式7．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称；3型文法，又称。上下文无关文法，正规文法8．最右推导称为，由规范推导产生的句型称为规范句型。规范推导9．设G是一个文法，S是它的开始符号，如果S=*α，则称α是一个。仅由终结符号组成的句型是一个。句型，句子10对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同，那么该文法就称为是二义的。语法树11．通常程序设计语言的单词符号分为五种：基本字、、常数、算符、界限符。标识符12．在自底向上分析法中，LR分析法把“可归约串”定义为。句柄13．编译中常用的中间代码形式有逆波兰式、三元式、和四元式等。树代码14．对中间代码优化按涉及的范围分为，和全局优化。局部优化，循环优化15．局部优化主要包括、利用公共子表达式和删除无用赋值等内容。合并已知量16．为了构造不带回溯的递归下降分析程序，我们通常要消除和提取左递归，左公共因子17.计算机执行用高级语言编写的程序主要有两种途径：和。解释执行，编译执行18.扫描器是词法分析，它接收输入的，对源程序进行词法分析并识别出一个个，供语法分析器使用。源程序，单词符号19.自下而上分析法采用，，和等四种操作。移进、规约、错误处理、接受20.一个LR分析器包括两部分：一个总控程序，和分析栈。一张分析表21.后缀式abc-/所代表的表达式是。a/(b-c)22.局部优化是在范围内进行的一种优化。基本块23.不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为和。栈式动态存储分配，堆式动态存储分配24.规范规约是。最左规约25.编译程序的工作过程一般划分为5个阶段：词法分析、、语义分析与中间代码生成，代码优化及目标代码生成。另外还有和出错处理。语法分析，表格管理26．表达式x+y*z/(a+b)的后缀式为。xyz*ab+/+27．文法符号的属性有综合属性和。继承属性28．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为。a+(i-1)*20+j-129．局部优化是局限于一个范围内的一种优化。基本块二选择题1．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合A2．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化C3．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语D4．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言C5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型B6．对应Chomsky四种文法的四种语言之间的关系是A.L0L1L2L3B.L3L2L1L0C.L3=L2L1L0D．L0L1L2=L3B7．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码A8．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树D9．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换C10．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言C11.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。A．字符串B．产生式C．开始符号D．文法C,B12.程序的基本块是指（）。A．一个子程序B．一个仅有一个入口和一个出口的语句C．一个没有嵌套的程序段D．一组顺序执行的程序段，仅有一个入口和一个出口D13.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A．自左向右B．自顶向下C．自底向上D．自右向左C14．在通常的语法分析方法中，（）特别适用于表达式的分析。A．算符优先分析法B.LR分析法C．递归下降分析法D.LL（1）分析法A15．经过编译所得到的目标程序是（）。A．四元式序列B．间接三元式序列C．二元式序列D．机器语言程序或汇编语言程序D16．一个文法所描述的语言是（）；描述一个语言的文法是（）。A．唯一的B．不唯一的C．可能唯一，也可能不唯一A,C17.词法分析器的输出结果是（）。A.单词的种别,编码B.单词在符号表的位置C.单词的种别编码和自身值D.单词自身值C18.正规式M1和M2等价是指（）。A.M1和M2的状态相等B.M1和M2的有向边条数相等C.M1和M2所识别的语言集相等D.M1和M2状态数和有向边条数相等C19.文法G:S→xSx|y所识别的语言是（）。A.xyxB.(xyx)*C.xnyxnD.x*yx*C20.如果文法G是二义的，则它的任何句子α（）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导但是他们对应的语法树相同。A21.构造编译程序应掌握（）A.编译程序B.目标语言C.编译方法D.以上三项都是D22.四元式之间的联系是通过（）实现的。A.指示器B.临时变量C.符号表D.程序变量B23.程序的基本块是指（）A.一个子程序B.一个仅有一个入口和一个出口C.一个没有嵌套的程序段D.一组顺序执行的程序段，仅有一个入口和一个出口D24.优化可生成（）的目标代码。A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小D25.下列（）优化方法不是针对循环优化进行的。A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提C26.编译程序使用（）区别标识符的作用域A.说明标识符的过程或者函数名B.说明标识符的过程或函数的静态层次C.说明标识符的过程或函数的动态层次D.标示符的行号B三名词解释1．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2．LL(1)文法若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3．语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN是非空有穷集合，称为非终结符号集合；VT是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VN∩VT=，SVN。V=VN∪VT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)={x|S*x，其中S为文法开始符号，且TVx}简单的说，文法描述的语言是该文法一切句子的集合。4．简述代码优化的目的和意义。代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。5.编译过程通常分为哪几个阶段？每个过程的主要功能？编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下：词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式。语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。6.简述代码优化的原则和目标原则：对中间代码进行等价变换，使代码变换后功能不变。目标：变换后的代码运行速度更快，占用的存储空间更少。7.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。wab+cde10-/+8+*+8.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。逆波兰式:abcd-*e/+三元序列:oparg1arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)四．判断题请在括号内，正确的划√，错误的划×）1.编译程序是对高级语言程序的解释执行。（）×2.一个有限状态自动机中，有且仅有一个唯一的终态（）×3.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()√4.语法分析时必须先消除文法中的左递归（）×自顶向下5.LR分析法在自左至右扫描输入串时就能发现错误，但不能准确的指出出错地点（）√6.逆波兰表示法表示表达式时无需使用括号。（）√7.静态数组的存储空间可以在编译时确定。（）×静态链接的情况下,链接器可以确定,编译只是把文本文件编译成为obj文件并不确定地址8.进行代码优化时应该着重考虑循环的代码优化，这对提高代码的效率将起更大作用。（）×9.两个正规集相等的必要条件是他们对应的正规式等价。（）×应该说正规式等价的必要条件是正规集相等10.一个语义子程序描述了一个文法所对应的翻译工作。（）×1审查每个语法结构的静态语义，2进行制导翻译11.一个上下文无关文法的开始符，可以是终结符或非终结符。（）×12.已经证明文法的二义性是可判定的。（）×13.每个基本块可用一个DAG表示。（）√14.一个句型一定是句子。()×15.算符优先分析法每次都是对句柄进行归约。()√16.采用三元式实现三地址代码时，不利于对中间代码进行优化。（）√17.编译过程中，语法分析器的任务是分析单词是怎样构成的。()×18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()√19.并不是每个文法都能改写成LL(1)文法。()√20.一个LL(1)文法一定是无二义的。()√四简单题1．设有文法G1:S→SaQ∣QQ→QbR∣RR→cSd∣e（1）证明句型QbRae是规范句型（2）给出句型QbRae的语法树和句柄：解答：证明：（1）因为句型QbRae可由文法开始符S经过规范推导产生，推导过程如下：S=SaQ=SaR=Sae=Qae=QbRae所以句型QbRae是规范句型（2分）（2）、语法树（1分）句柄：QbR2.设有非确定的有限自动机NFAM=({A,B,C},{0，1},,{A},{C})其中：（A,0）={C},(A,1)={A,