大学编译原理课程复习试题及答案

1、编译原理复习材料选择题1.文法s0s | s1 | 0的语言是( )。a. 0 m1m| m =0 b. 0 m1m| m =1 c. 0 m1n | m=1,n=0 d. 0 m1n | m=0,n=1 2.描述程序语言所采用的型文法是 ( )。a. 短语文法 b.正规文法c.上下文无关文法d.上下文有关文法3.状态转换图实现的简单方法是使每个状态结对应( )。a.一个终结符b.一个非终结符c.一段小程序d.一个函数4.规范归约的关键问题是寻找( )。a. 最左素短语 b.句柄c.直接短语d.短语5.一个算符文法的任何产生式的右部都不含有两个相继的( )。a.终结符b.非终结符c.终结符和非

2、终结符d.空字6.算符优先分析法的关键在于规定( )。a.算符优先顺序和结合性质b.算符优先顺序c.结合性质d.终结符和非终结符之间关系7.优先函数的优点是( )。a.形象直观b.便于进行比较运算c.语法分析速度快d.语法分析方法简单8.文法符号的属性通常分为( )两类。a. 共用属性和私有属性 b.固有属性和可变属性c.语法属性和语义属性d.综合属性和继承属性9.在程序流图中，组成循环的结点序列应满足( )a. 它们是强连通的 b.它们中间有唯一的入口结点c.它们中间有一条回边d.它们是强连通的且有唯一的入口结点10.在利用寄存器r生成t1:=c/b的目标代码同时,还应记录信息( )。a.

3、c/b在t1中 b. t1在c/b中c. r含有t1, t1在r中d. r含有c/b, c/b在r中1.d2.b3.c4.b5.b6.a7.b8.d9.d10.c1.编译方式与解释方式的根本区别在于( )a.是否生成目标代码b.是否生成中间代码c.是否生成汇编代码d.是否生成优化代码2.编译程序生成的目标程序( )a.一定是机器语言的程序b.不一定是机器语言的程序c.一定不是机器语言的程序d.一定是汇编语言的程序3.设字母表=0,1,x,y, 则上的正规式所对应的正规集为( )a.b. 0,1,x,y c. d.4. *假设g是一个文法，s是文法的开始符号，如果s= x,则称x是( )a.短语

4、b.句柄c.句子d.句型5.一个算符文法的任何产生式的右部都不含有两个相继的( )a.终结符b.非终结符c.终结符和非终结符d.字6.设有文法ga：a ax|ay|aa|ac|a|b|c，下列哪些是该文法的句子( )(1) aby(2) aycyx(3) aaa(4) bcxya.(1) (2) (3)b. (1) (2) (4)c.(2) (3) (4)d.全部7.分析器的核心部分是( )a.带先进后出存贮器的dfa b.一张动作表c.一张goto表d.一张分析表8.在程序流图中，组成循环的结点序列应满足( )a.它们是强连通的且有唯一的入口结点b.它们中间有唯一的入口结点c.它们中间有一条

5、回边d.它们是强连通的9.表达式abcadabe的后缀式式为( )。a.abcadabeb.abcdaabec.abcadabed.abcadabe10.程序基本块是指 ( )a.一个子程序b.一个仅有一个入口和一个出口的语句c. 一个没有嵌套的程序段d.一组顺序执行的程序段，仅有一个入口和一个出口1.a2.b3.c4.d5.b6.c7.d8.a9.c10.d1.bnf是一种用于 ( )的工具。a. 描述句型 b.描述句子c.描述语言d.描述文法2.设字母表=0,1,x,y, 则上的正规式所对应的正规集为( )a.b. c. 0,1,x,y d.3.规范推导也称为( )a. 最右推导 b.最左

6、推导c.一般推导d.自左向右推导4.在规范归约中, 任何可归约串的出现必在( )a.栈的内部b.栈顶c.剩余的输入串中d.在先进后出栈中5.一个算符文法的任何产生式的右部都不含有两个相继的( )a.终结符b.非终结符c.终结符和非终结符d.字6.分析器的核心部分是( )a.一张分析表b.一张动作表c.一张goto表d.带先进后出存贮器的dfa7.算符优先分析的关键问题是寻找( )。a.句柄b.最左素短语c.短语d.直接短语8.四元式之间的联系是通过( )a.指示器b.临时变量c.四元式的编号d.中间运算结果9.表达式abcadabe的逆波兰式为( )。a.abcadabe b.abcdaabe

7、c.abcadabed.abcadabe10.代码外提时要求该不变运算所在的结点是循环的( )。a.某个出口的必经结点b.至少是一个入口的必经结点c.入口的必经结点d.所有出口的必经结点1.d2.b3.a4.b5.b6.a7.b8.b9.a10.d填空题1.一个状态转换图可用于一定的字符串。2.设a , b , c，则*中最短的符号串为。3.若由文法的开始符号可以推导出串 ，且，则为原文法的一个句子。4.若文法的某非终结符p满足，称文法含有左递归。5.表达式-(a+b)/(c*d)-e的逆波兰式为_。6.后序遍历一棵表达式树，可得到它的。7.中间代码是一种面向语法，易于翻译成的代码。8.四元式

8、序列中各四元式出现的顺序与是一致的。9.若每个程序对应一个流图，则流图中的结点对应一个。10.若从流图首结点出发, 到达nj的任一通路必须经过ni，则称的必经结点。1.识别或接受2.3. vt*4.=5.ab+cd*/e-6.逆波兰式7.目标代码8.运算顺序9.基本块10.ni为nj1.一个非确定的有限自动机可以表示为一个元式。2.若文法的某非终结符p满足，称文法含有左递归。3.设1 , 2, 3，则*中最短的符号串为。4.用+表示上所有的集合。5.三地址代码的一般形式为。6.递归下降法对每个构造一个相应的子程序。7.在算符优先分析中，用作为可归约串。8.在形式语言中，最推导被称为规范推导。9

9、.语法树中，一个结点的属性由此结点的父结点和/或兄弟结点的属性确定。10.如果循环中对变量i只有唯一的形如i=ic的赋值，则称i为循环中的变量。1. 2.五=3.4.长度不为0的串5.x:=y op z6.非终结符7.最左素短语8.右9.继承10.基本归纳1.终态与非终态的区别在于。2.用+表示上所有的集合。3.一个状态转换图可用于一定的字符串。4.用于词法分析的扫描缓冲区可将两个半区使用。5.一个句型的称为该句型的句柄。6.递归下降法对每个构造一个相应的子程序。7.算符优先法尤其适用于的分析。8.规范归约的关键在于如何确定。9.文法符号的属性值可自底向上应用语义规则计算出来。10.dag代表

10、。1.终态可接受空串2.长度不为0的串3.识别4.互补5.最左简单短语6.非终结符7.表达式8.句柄9.综合10.有向无环图判断题1.若一个文法是递归的，则由它产生的语言的句子个数是有限的。（ ）2.用于词法分析的扫描缓冲区可将两个半区重叠使用。（ ）3.一个lr分析器实质上是一个带有后进先出存储器的dfa。（ ）4.符号表的每一项一般包含入口栏和信息栏两大部分。（ ）5.dag是对循环进行优化的有效工具。（ ）6.代码外提时要求该不变运算所在的结点是循环的某个出口的必经结点。（ ）1.无限2.互补3.4.名字5.基本块6.所有1.描述程序语言所采用的型文法是上下文无关文法。（ ）2.状态转换

11、图实现的简单方法是使每个状态结点对应一个非终结符（ ）3.欲构造行之有效的自下而上分析器，则必须清除文法中含有的左递归。（ ）4.在规范归约中, 任何可归约串的出现必在栈的内部。（ ）5.循环优化中的强度削弱主要是指将循环中的乘法变成加法。（ ）6.符号表的信息栏中的内容称为关键字。（ ）1. 正规文法2. 一段小程序3. 自上而下4. 栈顶5.递归加法6.名字1.设是某句型的一个子串，若它能被一次直接归约为一个非终结符，则是该句型的一个直接短语。（ ）2.语法分析过程可用一棵树表示出来,这棵树叫做语法树。（ ）3.欲构造行之有效的自下而上分析器，则必须清除文法中含有的左递归。（ ）4.四元式

12、作为中间语言，用于翻译除表达式外的其他语句代码。（ ）5.循环优化中的强度削弱主要是指将循环中的乘法变成加法。（ ）6.流图中有向边ab为回边的条件是a dom b。（ ）1. 要求这个非终结符取代后，原句型还可继续向开始符方向归约。2.分析树3. 自上而下4. 各种5.递归加法6.b dom a简答题1.简述正规式与有限自动机的关系。2.已知文法g: s ises | is | i该文法是否具有二义性？请根据句子iiiei构造语法树予以说明。3.何谓递归下降分析法？应用此种分析法的文法应满足什么条件？4简述代码优化所依据的原则与优化的级别，并列举三种常用的优化技术。1.正规式用来描述正规集，

13、而有限自动机用来识别正规集，在正规集的意义上它们存在等价关系。 即：对每一个正规式所代表的正规文法g，都存在一个有限自动机m，使得l(m)=l(g)，m所能识别的字的全体恰为这个正规文法g的语言集合； 对每一个有限自动机m，都存在一个可以用正规式表示的正规文法g，使得l(g)=l(m)，这个正规文法g的语言集合中的任一个字可以由m识别。 2.对于句子iiiei，该文法具有两棵不同的语法树与之对应，故为二义性文法。 s s / / / i s e s i s / | / / i s ii s e s| | |iii3.当文法满足ll(1)条件时，可以为它构造一个不带回溯的自上而下分析程序。它由一

14、组递归过程（函数）组成，每个过程（函数）对应文法的一个非终极符，这样的分析程序称为递归下降分析器。 利用这种分析程序进行语法分析的方法称为递归下降分析法。 4.代码优化所依据的原则是：等价原则、有效原则和合算原则。代码优化所依据的级别是：局部优化、循环优化与全局优化。常用的代码优化技术有：删除公共子表达式、删除无用赋值、合并已知量、代码外提、强度削弱、删除归纳变量等。 1.什么是编译器的前端和后端，通常两者之间用什么作为接口？2.简述nfa和dfa的联系与区别。3.语法分析方法如何分类？它们面对的主要问题是什么？4.何谓中间语言？简述它的作用。1.前端主要由与源语言有关但与目标机无关的那些部分

15、组成，通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。（2分）后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。（2分）通常，前端和后端以中间语言作为接口（1分）2.联系：nfa和dfa都是有限自动机，都用于接收、识别一定的字符串。nfa是dfa的推广，dfa是nfa的特例。 （2分）区别：nfa多值函数，dfa是单值函数。 nfa可以有多个初态，dfa只有一个初态。 nfa的每条弧允许用*上的一个字作标记，dfa的每条弧只允许用上的一个字符作标记。 （3分）3.按照语法分析树的建立方法，可以把语法分析方法分为两类：自上而下

16、分析法与自下而上分析法。 （2分）自上而下分析法面对的主要问题是：如何消除文法的左递归，以及在由文法的开始符出发推导句子的过程中如何避免回溯。 （2分）自下而上分析法面对的主要问题是：在由输入串出发向文法的开始符归约的过程中，如何确定可归约子串（句柄或最左素短语）。 （1分）4.中间语言是一种面向语法，复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间，是一种易于翻译成目标代码的代码形式。 （3分）中间语言的作用在于：利用它作为中间环节，不仅可以较快地实现源程序翻译过程，而且可在此基础上应用优化方法，将源程序翻译成为运行时间短、占用内存少的目标程序。 （2分）1.何谓上下文无关文法

17、? 它是由哪几部分组成的?2.简述nfa和dfa的联系与区别。3.语法分析方法如何分类？它们面对的主要问题是什么？4.何谓中间语言？简述它的作用。1.上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴所处的环境的。 （3分）上下文无关文法由四部分所组成：一组终极符号，一组非终极符号，一个开始符号以及一组产生式。 （2分）2.联系：nfa和dfa都是有限自动机，都用于接收、识别一定的字符串。nfa是dfa的推广，dfa是nfa的特例。 （2分）区别：nfa多值函数，dfa是单值函数。 nfa可以有多个初态，dfa只有一个初态。 nfa的每条弧允许用*上的一个字作标

18、记，dfa的每条弧只允许用上的一个字符作标记。 （3分）3.按照语法分析树的建立方法，可以把语法分析方法分为两类：自上而下分析法与自下而上分析法。 （2分）自上而下分析法面对的主要问题是：如何消除文法的左递归，以及在由文法的开始符出发推导句子的过程中如何避免回溯。 （2分）自下而上分析法面对的主要问题是：在由输入串出发向文法的开始符归约的过程中，如何确定可归约子串（句柄或最左素短语）。 （1分）4.中间语言是一种面向语法，复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间，是一种易于翻译成目标代码的代码形式。 （3分）中间语言的作用在于：利用它作为中间环节，不仅可以较快地实现源程序

19、翻译过程，而且可在此基础上应用优化方法，将源程序翻译成为运行时间短、占用内存少的目标程序。 （2分）综合题1.构造一个dfa，它接受=a，b上所有包含ab的字符串。2.对文法g（s）：s （l） | as | al l,s | s1、消除左递归和回朔；2、构造各非终结符的first和follow集合；3、构造预测分析表。3.给出文法g（p）p bqbq crq ar qad该文法是不是算符优先文法，请构造算符优先关系表证实之。4.（1）有如下三地址码： read(n) i:=1fen:=1l1: if i=n goto l2goto l3l2: t1:=fen*i fen:=t1 i:=i+1

20、goto l1l3: write (fen)将该代码段划分为基本块；并构造相应的程序流图。（2）对下列四元式序列生成目标代码：a:=b*cd:=e+fg:=a+dh:=g*2其中，h在基本块出口之后是活跃变量，r0和r1是可用寄存器。1构造一个dfa，它接受=a，b上所有包含ab的字符串。2对文法g（s）：s （l） | as | al l,s | s1、消除左递归和回朔；2、构造各非终结符的first和follow集合；3、构造预测分析表。答：3给出文法g（p）p bqbq crq ar qad该文法是不是算符优先文法，请构造算符优先关系表证实之。答：对于文法g，计算它的每个非终结符的fir

21、stvt和lastvt集合：4（1）有如下三地址码：read(n)i:=1fen:=1l1: if i60 goto (10)(8) j:=j+1(9) goto (3)(10) write b(11) halt(1)划分基本块，画出流图(2)对其中循环进行优化，画出优化后流图1构造一个最简的dfa，它接受=a，b上所有满足如下条件的字符串：所有b都有a直接跟在后面。答：(1)由以上正规式构造相应的nfa m(4分)(2)用子集法对m进行确定化，得到dfa m (4分)iia =_closure(j)ib =_closure(j)x,1,y1,y21,y1,y1,y22-状态ab0121112

22、2-(3)把dfa m进行化简 (4分)把m状态集分为两组:终态结点0，1；非终态结点2考察0，1，因为，0，1a =1包含于0,1；0，1b=2包含于2；所以，0，1不可再分所以，最终把m分割为0，1，2。状态1代替状态0，把引向状态0的箭弧都引向状态1，把0消去，得到一个dfa m2设有文法g(x)，该文法产生式为：x b | & | (y)y y；x| x其中x为文法开始符号，b & ； ( )为终结符号(1)消除左递归(2)计算每个非终结符号的first集和follow集(3)构造它的预测分析表答：(1)消除左递归(4分)x b | & | (y)y xyy ；xy|(2)计算每个非终

23、结符号的first集和follow集(4分)first( x )= b , & ,( ;first( y )= b , & ,( ;first( y)=； , ;follow(t)= ) ; follow (y)= ) ;follow (x)= #, ； ;(3)构造它的预测分析表(4分)b&()；#xx bx &x (y)yyxyyxyyxyyy y,xy3设文法g（s）：s sia | aa a+b | bb ）a* | （1、构造各非终结符的firstvt和lastvt集合；2、构造优先关系表和优先函数答：（4分）（4分）（4分）4对以下程序(1) read b(2) j:=1(3) a:=i+2(4) e:=i*j(5) d:=a+e(6) b:=d+b(7) if j60 goto (10)(8) j:=j+1(9) goto (3)(10) write b(11) halt(1)划分基本块，画出流图(2)对其中循环进行优化，画出优化后流图(1)划分基本块，画出流图(6分)(10) write b(11) halt(8) j:=j+1(9) goto (3)(3) a:=i+2(4) e:=i*j(5) d:=a+e(6) b:=d+b(7) if j60 goto (10)(1) read b(2)