编译原理试题库

1、一 填空题1 编译程序首先要识别出源程序中每个 ，然后再分析每个 并翻译其意义。 单词，句子2编译器常用的语法分析方法有 和 两种。自底向上，自顶向下2 通常把编译过程分为分析 与综合 两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。前端，后端4程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 方案和 分配方案。 静态存储分配，动态存储5对编译程序而言，输入数据是 ，输出结果是 。源程序，目标程序6文法G包括四个组成部分：一组终结符号，一组非终结符号，一组 ，以及一个开始符号。产生式7文法按产生式的形式分为四种类

2、型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称 ；3型文法，又称 。上下文无关文法，正规文法8最右推导称为 ，由规范推导产生的句型称为规范句型。规范推导9设G是一个文法，S是它的开始符号，如果 S=*，则称是一个 。仅由终结符号组成的句型是一个 。句型，句子10 对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同 ，那么该文法就称为是二义的。语法树11通常程序设计语言的单词符号分为五种：基本字、 、常数、算符、界限符。标识符12在自底向上分析法中，LR分析法把“可归约串”定义为 。句柄13编译中常用的中间代码形式有逆波兰式、三元式、 和四元式等。树代码

3、14对中间代码优化按涉及的范围分为 ， 和全局优化。局部优化，循环优化15局部优化主要包括 、利用公共子表达式和删除无用赋值等内容。合并已知量16为了构造不带回溯的递归下降分析程序，我们通常要消除 和提取 左递归，左公共因子17.计算机执行用高级语言编写的程序主要有两种途径： 和 。 解释执行，编译执行18.扫描器是词法分析，它接收输入的 ，对源程序进行词法分析并识别出一个个 ，供语法分析器使用。源程序，单词符号19.自下而上分析法采用 ， ， 和 等四种操作。移进、规约、错误处理、接受20.一个LR分析器包括两部分：一个总控程序， 和分析栈。一张分析表21.后缀式abc-/所代表的表达式是

4、。a/(b-c)22.局部优化是在 范围内进行的一种优化。基本块23. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为 和 。栈式动态存储分配，堆式动态存储分配24. 规范规约是 。最左规约25. 编译程序的工作过程一般划分为5个阶段：词法分析、 、语义分析与中间代码生成，代码优化及目标代码生成。另外还有 和出错处理。语法分析，表格管理26表达式x+y*z/(a+b)的后缀式为 。xyz*ab+/+27文法符号的属性有综合属性和 。继承属性28假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a1.15

5、,1.20某个元素ai，j的地址计算公式为 。a+(i-1)*20+j-129局部优化是局限于一个 范围内的一种优化。基本块二 选择题1语言是A句子的集合 B产生式的集合 C符号串的集合 D句型的集合A2编译程序前三个阶段完成的工作是A词法分析、语法分析和代码优化 B代码生成、代码优化和词法分析C词法分析、语法分析、语义分析和中间代码生成 D词法分析、语法分析和代码优化C3一个句型中称为句柄的是该句型的最左 A非终结符号 B短语 C句子 D直接短语D4下推自动机识别的语言是A0型语言 B1型语言 C2型语言 D3型语言C5扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小

6、语法单位即A 字符 B单词 C句子 D句型B6对应Chomsky四种文法的四种语言之间的关系是 A.L0L1L2L3 B.L3L2L1L0 C.L3=L2L1L0 DL0L1L2=L3B7词法分析的任务是 A识别单词 B分析句子的含义 C识别句子 D生成目标代码A8常用的中间代码形式不含 A三元式 B四元式 C逆波兰式 D语法树D9 代码优化的目的是 A节省时间 B节省空间 C节省时间和空间 D把编译程序进行等价交换C10代码生成阶段的主要任务是 A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言C11. 一个上下文无关

7、文法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四元式

8、序列 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:SxSx|y所识别的语言是（）。A.xyx B.(xyx)* C.x yx D.x*yx*C20.如果文法G是二

9、义的，则它的任何句子（）A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导但是他们对应的语法树相同。A21.构造编译程序应掌握（）A.编译程序 B.目标语言 C.编译方法 D.以上三项都是D22.四元式之间的联系是通过（）实现的。A.指示器 B.临时变量 C.符号表 D.程序变量B23.程序的基本块是指（）A.一个子程序 B.一个仅有一个入口和一个出口C.一个没有嵌套的程序段 D.一组顺序执行的程序段，仅有一个入口和一个出口D24.优化可生成（）的目标代码。A.运行时间较短 B.占用存储空间较小C.运

10、行时间短但占用内存空间大 D.运行时间短且占用存储空间小D25.下列（）优化方法不是针对循环优化进行的。A.强度削弱 B.删除归纳变量C.删除多余运算 D.代码外提C26.编译程序使用（）区别标识符的作用域A.说明标识符的过程或者函数名B.说明标识符的过程或函数的静态层次C.说明标识符的过程或函数的动态层次D.标示符的行号B三 名词解释1词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2LL(1)文法 若文法的任何两个产生式A a | b都满足下面两个条件

11、：（1）FIRST(a ) FIRST(b ) = f；（2）若b * e ，那么FIRST(a ) FOLLOW( A ) = f。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合，称为终结符号集合；P是产生式的集合

12、(非空)；S是开始符号(或识别符号)。这里，VNVT=，SVN。V=VNVT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即L(G)=x| S*x，其中S为文法开始符号，且 简单的说，文法描述的语言是该文法一切句子的集合。4简述代码优化的目的和意义。 代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。5.编译过程通常分为哪几个阶段？ 每个过程的主要功能？ 编译过程通常分为词法分析、语法分析

13、、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下：词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式。语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。目标代码生成：把中间代码变换成

14、特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。6. 简述代码优化的原则和目标原则：对中间代码进行等价变换，使代码变换后功能不变。目标：变换后的代码运行速度更快，占用的存储空间更少。7.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。wab+cde10-/+8+*+ 8. 写出表达式ab*(c-d)/e的逆波兰式和三元序列。逆波兰式: abcd-*e/+三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3)四判断题请在括号内，正确的划，错误的划）1. 编译程序是对高级语言程序的解释

15、执行。 （ ）2. 一个有限状态自动机中，有且仅有一个唯一的终态 （ ）3. 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )4. 语法分析时必须先消除文法中的左递归 （ ）自顶向下5. LR分析法在自左至右扫描输入串时就能发现错误，但不能准确的指出出错地点 （ ）6. 逆波兰表示法表示表达式时无需使用括号。 （ ）7. 静态数组的存储空间可以在编译时确定。 （ ）静态链接的情况下, 链接器可以确定, 编译只是把文本文件编译成为obj文件并不确定地址8. 进行代码优化时应该着重考虑循环的代码优化，这对提高代码的效率将起更大作用。（ ）9. 两个正规集相等的必要条件是他们对应的正

16、规式等价。 （ ）应该说正规式等价的必要条件是正规集相等10. 一个语义子程序描述了一个文法所对应的翻译工作。 （ ）1 审查每个语法结构的静态语义，2进行制导翻译11.一个上下文无关文法的开始符，可以是终结符或非终结符。 （ ）12.已经证明文法的二义性是可判定的。 （ ）13.每个基本块可用一个DAG表示。 （ ）14.一个句型一定是句子。 ( )15.算符优先分析法每次都是对句柄进行归约。 ( )16.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ ）17.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题

17、。 ( )19.并不是每个文法都能改写成LL(1)文法。 ( )20.一个LL(1)文法一定是无二义的。 ( )四 简单题1设有文法G1: SSaQ Q QQbR R RcSd e（1）证明句型 QbRae 是规范句型（2）给出句型 QbRae 的语法树和句柄：解答： 证明：（1）因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下：S = SaQ = SaR = Sae = Qae = QbRae所以句型 QbRae 是规范句型（2分）（2）、语法树（1分）SQSaQQRbRe句柄：QbR2.设有非确定的有限自动机NFA M=(A,B,C,0，1,d,A,C)其中：d（A,0

18、）=C,d(A,1)=A,B,d (B，1)=C d (C，1)=C。请画出状态转换矩阵和状态转换图。解答：状态转换距阵为：符号状态01ACA，BBCCC状态转换图为：110113.构造正规式1（0|1）*101相应的DFA.解：1 011YBCAX4.设有基本块：T1：2 T2：10/T1 T3：SR T4：SR A：T2 * T4 B：A T5：SR T6：T3 * T5 B：T6 (1) 画出DAG图(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。4、（1）DAG图BT6BA*T3T4T5-+RS5T22T110（2）优化后的四元式序列：T3:=S-RT4:=S+RA

19、:=5 * T4B:=T4*T35.考虑一下文法：D T V T int | float V id ,V | id（1）在该文法中提取左公共因子。（2）为所得的文法的非终结符构造First集合和Follow集合。（3）说明所得的文法是LL(1)文法。（4）为所得的文法构造LL(1)分析表。解答：（1）文法存在左公因子，提取左公因子后的文法为：D T VT int | floatV id VV ,V | (2)非终结符First集合Follow集合D int , float #T int , float idV id #V , , #（3）(a) First (T int ) First (T

20、float ) =; (b) V=, First(V ,V)Follow(V)= , , # = 根据LL(1)文法的定义判断，此文法是LL(1)文法；LL(1)分析表为：intfloatid,#DD TVD TVTT intTfloatVVidVVV ,VV6. 考虑下面的程序： procedure p(x, y, z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 解答：传值 a=5传地址 a=127证明下述文法G：SaSbS|aS|

21、d 是二义性文法。 证明：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图：SaSSabSdddSSabSSad (1) (2) 8. 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6（1）画出DAG图；（2）设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。解答：（1） DAG如右图：T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7(2)四元式序列：T1:=S+RT4:=S/RA:

22、=T1-T4B: =T1*49. 设文法G(S): S(T) | aS | a TT,S | S（1）消除左递归和提公共左因子；（2）构造相应的FIRST和FOLLOW集合；（3）构造预测分析表。解答：(1) S (T) | aS SS | TST T,ST |(2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(T)=a, ( FIRST(T)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), #FOLLOW(T)= ) FOLLOW(T)= )(3) ( ) a , # SS (T)S aSSSSSSSSSTTSTTSTT,ST TT11.已知文法

23、 GS 为 S aSb|Sb|b ，试证明文法 GS 为二义文法。证明： 由文法GS：SaSb|Sb|b，对句子aabbbb对应的两棵语法树为： 因此，文法GS为二义文法。 12.考虑下面的程序：procedure p(x, y, z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 答案：传值 a=2传地址 a=1513.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。逆波兰式 abc+e*bc+f/+:=三元序列 o

24、p arg1 arg2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 14什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。15.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左递归和提公共左因子。解答：消除左递归SaFS | *aFSS*aFS | F+aF | +a提公共左因子,文法 G(S) SaFS | *aFSS*aFS | F+aFFF |16对于文法GS：SAB，AAa|bB，B

25、a|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。ASBbBSab图:句型baSb的的语法树解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。17.已知文法G(S) SaAcBe AAb| b Bd(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。 解答：(1)S=aAcBe=aAbcBe=abbcBe=abbcde(2) 短语: aAbcde, Ab, d 素短语: Ab, d18

26、.已知文法G(S) EE+T | T TT*F| F F(E)| i (1) 给出句型 (i+i)*i+i的最左推导及画出语法树；(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。解答：(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+T19. 何谓优化？按所涉及的程序范围可分为哪几级优化？优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化20. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。21. 一字母表=a, b，试写出上所有以a为首的字组成的正规集相对应的正规式。解答：正规式 a ( a | b )*。22.设有基本块D:=A-CE: