2022年大学编译原理课程复习试题及答案 .pdf

《2022年大学编译原理课程复习试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年大学编译原理课程复习试题及答案 .pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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.非终结符

2、C.终结符和非终结符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 的目标代码同时

3、,还应记录信息( )。A. C/B 在 T1中B. T1在 C/B 中C. R含有 T1, T1在 R中D. R含有 C/B, C/B 在 R中1.D 2.B 3.C 4.B 5.B 6.A 7.B 8.D 9.D 10.C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 25 页 - - - - - - - - - 1. 编译方式与解释方式的根本区别在于( ) A.是否生成目标代码B.是否生成中间代码C.是否生成汇编代码D.是否生成优化代码2. 编译程序生成的目标程序(

4、 ) A.一定是机器语言的程序B.不一定是机器语言的程序C.一定不是机器语言的程序D.一定是汇编语言的程序3. 设字母表 =0,1,x,y, 则上的正规式所对应的正规集为( )A.B. 0,1,x,y C. D.4. * 假设 G是一个文法， S是文法的开始符号， 如果 S= x, 则称 x 是( ) A.短语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) bcx

5、y A.(1) (2) (3) B. (1) (2) (4) C.(2) (3) (4) D.全部7. 分析器的核心部分是( )A.带先进后出存贮器的DFA B.一张动作表C.一张 GOTO表D.一张分析表8. 在程序流图中，组成循环的结点序列应满足( )A.它们是强连通的且有唯一的入口结点B.它们中间有唯一的入口结点C.它们中间有一条回边D.它们是强连通的9. 表达式 abcadabe 的后缀式式为( )。A.abc ad abeB.abc daabeC.abc ad ab eD.abc adab e10. 程序基本块是指 ( ) A.一个子程序B.一个仅有一个入口和一个出口的语句C. 一个

6、没有嵌套的程序段D.一组顺序执行的程序段，仅有一个入口和一个出口1.A 2.B 3.C 4.D 5.B 6.C 7.D 8.A 9.C 10.D 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - 1. BNF是一种用于( )的工具。A. 描述句型B. 描述句子C.描述语言D.描述文法2. 设字母表 =0,1,x,y, 则上的正规式所对应的正规集为( )A.B. C. 0,1,x,y D.3. 规范推导也称为( )A. 最右推导B

7、.最左推导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.abc ad

8、 abeB.abc daabeC.abcad ab eD.abc adab e10. 代码外提时要求该不变运算所在的结点是循环的( )。A.某个出口的必经结点B.至少是一个入口的必经结点C.入口的必经结点D.所有出口的必经结点1.D 2.B 3.A 4.B 5.B 6.A 7.B 8.B 9.A 10.D 填空题1. 一个状态转换图可用于一定的字符串。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 25 页 - - - - - - - - - 2. 设a , b , c

9、，则 *中最短的符号串为。3. 若由文法的开始符号可以推导出串 ， 且， 则 为原文法的一个句子。4. 若文法的某非终结符P 满足，称文法含有左递归。5. 表达式-(a+b)/(c*d)-e的逆波兰式为_。6. 后序遍历一棵表达式树，可得到它的。7. 中间代码是一种面向语法，易于翻译成的代码。8. 四元式序列中各四元式出现的顺序与是一致的。9. 若每个程序对应一个流图，则流图中的结点对应一个。10. 若从流图首结点出发, 到达nj的任一通路必须经过ni，则称的必经结点。1. 识别或接受2. 3. ? VT*4. = 5. ab+cd*/e- 6. 逆波兰式7. 目标代码8. 运算顺序9. 基本

10、块10. ni 为 nj 1. 一个非确定的有限自动机可以表示为一个元式。2. 若文法的某非终结符P 满足，称文法含有左递归。3. 设1 , 2, 3 ，则 *中最短的符号串为。4. 用+表示上所有的集合。5. 三地址代码的一般形式为。6. 递归下降法对每个构造一个相应的子程序。7. 在算符优先分析中，用作为可归约串。8. 在形式语言中，最推导被称为规范推导。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 25 页 - - - - - - - - - 9. 语法树中，一个

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

12、上应用语义规则计算出来。10. DAG 代表。1. 终态可接受空串2. 长度不为 0 的串3. 识别名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - 4. 互补5. 最左简单短语6. 非终结符7. 表达式8. 句柄9. 综合10. 有向无环图判断题1. 若一个文法是递归的，则由它产生的语言的句子个数是有限的。（）2. 用于词法分析的扫描缓冲区可将两个半区重叠使用。（）3. 一个LR 分析器实质上是一个带有后进先出存储器的DFA。

13、（）4. 符号表的每一项一般包含入口栏和信息栏两大部分。（）5. DAG 是对循环进行优化的有效工具。（）6. 代码外提时要求该不变运算所在的结点是循环的某个出口的必经结点。（）1. 无限2. 互补3. 4. 名字5. 基本块6. 所有1. 描述程序语言所采用的型文法是上下文无关文法。（）2. 状态转换图实现的简单方法是使每个状态结点对应一个非终结符（）3. 欲构造行之有效的自下而上分析器，则必须清除文法中含（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 -

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

15、强度削弱主要是指将循环中的乘法变成加法。（）6. 流图中有向边ab 为回边的条件是a DOM b。（）1. 要求这个非终结符取代后，原句型还可继续向开始符方向归约。2. 分析树3. 自上而下名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 25 页 - - - - - - - - - 4. 各种5. 递归加法6. b DOM a 简答题1. 简述正规式与有限自动机的关系。2. 已知文法 G: S iSeS | iS | i该文法是否具有二义性？请根据句子iiiei 构造语法

16、树予以说明。3. 何谓递归下降分析法？应用此种分析法的文法应满足什么条件？4简述代码优化所依据的原则与优化的级别，并列举三种常用的优化技术。1. 正规式用来描述正规集，而有限自动机用来识别正规集，在正规集的意义上它们存在等价关系。即：对每一个正规式所代表的正规文法G ，都存在一个有限自动机M ，使得 L(M)=L(G) ，M所能识别的字的全体恰为这个正规文法G 的语言集合；对每一个有限自动机M ，都存在一个可以用正规式表示的正规文法 G ，使得 L(G)=L(M) ，这个正规文法G 的语言集合中的任一个字可以由 M识别。2. 对于句子 iiiei，该文法具有两棵不同的语法树与之对应，故为二义性

17、文法。 S S / / / i S e S i S / | / / i S ii S e S | | | Iii 3. 当文法满足LL(1) 条件时，可以为它构造一个不带回溯的自上而下分析程序。它由一组递归过程（函数）组成，每个过程（函数）对应文法的一个非终极符，这样的分析程序称为递归下降分析器。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 25 页 - - - - - - - - - 利用这种分析程序进行语法分析的方法称为递归下降分析法。4. 代码优化所依据的原则是：

18、等价原则、有效原则和合算原则。代码优化所依据的级别是：局部优化、循环优化与全局优化。常用的代码优化技术有：删除公共子表达式、删除无用赋值、合并已知量、代码外提、强度削弱、删除归纳变量等。1. 什么是编译器的前端和后端，通常两者之间用什么作为接口？2. 简述 NFA 和 DFA 的联系与区别。3. 语法分析方法如何分类？它们面对的主要问题是什么？4. 何谓中间语言？简述它的作用。1. 前端主要由与源语言有关但与目标机无关的那些部分组成，通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。 （2 分）后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化

19、和目标代码生成等。 （2 分）通常，前端和后端以中间语言作为接口（1 分）2. 联系： NFA和 DFA都是有限自动机，都用于接收、识别一定的字符串。NFA是DFA的推广，DFA是NFA的特例。（2 分）区别： NFA多值函数， DFA是单值函数。 NFA可以有多个初态，DFA只有一个初态。 NFA的每条弧允许用*上的一个字作标记，DFA的每条弧只 允 许 用 上 的 一 个 字 符 作 标 记 。（3 分）3. 按照语法分析树的建立方法，可以把语法分析方法分为两类：自上而下分析法与自下而上分析法。（2 分）自上而下分析法面对的主要问题是：如何消除文法的左递归，以及在由文法的开始符出发推导句子

20、的过程中如何避免回溯。（2 分）自下而上分析法面对的主要问题是：在由输入串出发向文法的开始符归约的过程中，如何确定可归约子串（句柄或最左素短语）。（1 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 25 页 - - - - - - - - - 4. 中间语言是一种面向语法，复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间，是一种易于翻译成目标代码的代码形式。（3 分）中间语言的作用在于：利用它作为中间环节，不仅可以较快地实现源程序翻译过程，而且可在此基

21、础上应用优化方法，将源程序翻译成为运行时间短、占用内存少的目标程序。（2 分）1. 何谓上下文无关文法? 它是由哪几部分组成的? 2. 简述 NFA 和 DFA 的联系与区别。3. 语法分析方法如何分类？它们面对的主要问题是什么？4. 何谓中间语言？简述它的作用。1. 上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴所处的环境的。（3 分）上下文无关文法由四部分所组成：一组终极符号， 一组非终极符号， 一个开始符号以及一组产生式。（2 分）2. 联系： NFA和 DFA都是有限自动机，都用于接收、识别一定的字符串。NFA是DFA的推广，DFA是NFA的特例。（

22、2 分）区别： NFA多值函数， DFA是单值函数。 NFA可以有多个初态，DFA只有一个初态。 NFA的每条弧允许用*上的一个字作标记，DFA的每条弧只 允 许 用 上 的 一 个 字 符 作 标 记 。（3 分）3. 按照语法分析树的建立方法，可以把语法分析方法分为两类：自上而下分析法与自下而上分析法。（2 分）自上而下分析法面对的主要问题是：如何消除文法的左递归，以及在由文法的开始符出发推导句子的过程中如何避免回溯。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共

23、25 页 - - - - - - - - - （2 分）自下而上分析法面对的主要问题是：在由输入串出发向文法的开始符归约的过程中，如何确定可归约子串（句柄或最左素短语）。（1 分）4. 中间语言是一种面向语法，复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间，是一种易于翻译成目标代码的代码形式。（3 分）中间语言的作用在于：利用它作为中间环节，不仅可以较快地实现源程序翻译过程，而且可在此基础上应用优化方法，将源程序翻译成为运行时间短、占用内存少的目标程序。（2 分）综合题1. 构造一个 DFA，它接受 =a， b上所有包含ab 的字符串。2. 对文法 G（ S） ：S （ L）

24、| aS | a L L,S | S 1 、消除左递归和回朔；2、构造各非终结符的FIRST 和 FOLLOW 集合；3、构造预测分析表。3. 给出文法G（P）P bQb Q cR Q a R Qad 该文法是不是算符优先文法，请构造算符优先关系表证实之。4. （1）有如下三地址码：read(n) i:=1 fen:=1 L1: if i=n goto L2 Goto L3 L2: t1:=fen*i 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 25 页 - - -

25、 - - - - - - fen:=t1 i:=i+1 goto L1 L3: write (fen) 将该代码段划分为基本块；并构造相应的程序流图。（2）对下列四元式序列生成目标代码：A:=B*C D:=E+F G:=A+D H:=G*2 其中， H 在基本块出口之后是活跃变量，R0 和 R1 是可用寄存器。1构造一个DFA ，它接受 =a ，b上所有包含ab的字符串。2对文法 G（S） ：S （ L） | aS | a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共

26、 25 页 - - - - - - - - - L L,S | S 1 、消除左递归和回朔；2、构造各非终结符的FIRST 和 FOLLOW 集合；3、构造预测分析表。答：3给出文法G（P）P bQb Q cR Q a R Qad 该文法是不是算符优先文法，请构造算符优先关系表证实之。答：对于文法G，计算它的每个非终结符的FIRSTVT 和 LASTVT 集合：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 25 页 - - - - - - - - - fen:=1 L

27、1: if i60 goto (10) (8) J:=J+1 (9) goto (3) (10) WRITE B (11) halt (1) 划分基本块，画出流图(2) 对其中循环进行优化，画出优化后流图1构造一个最简的DFA ，它接受 =a ，b上所有满足如下条件的字符串：所有b 都有 a名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 25 页 - - - - - - - - - 直接跟在后面。答： (1) 由以上正规式构造相应的NFA M(4 分) XY1ba2a(

28、2) 用子集法对M进行确定化，得到DFA M (4 分) I Ia = _CLOSURE(J) Ib = _CLOSURE(J) x,1,y 1,y 2 1,y 1,y 1,y 2 2 - 状态a b 0 1 2 1 1 1 2 2 - 0aba21ba(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 消去，得到一个DF

29、A M 12baa2设有文法G(X)，该文法产生式为：X b | & | (Y) Y Y；X| X 其中 X为文法开始符号，b & ； ( )为终结符号(1) 消除左递归(2) 计算每个非终结符号的FIRST集和 FOLLOW 集(3) 构造它的预测分析表答：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 25 页 - - - - - - - - - (1)消除左递归 (4 分)X b | & | (Y) Y XYY ；XY | (2)计算每个非终结符号的FIRST 集

30、和 FOLLOW 集(4 分) FIRST( X )= b , & ,( ; FIRST( Y )= b , & ,( ; FIRST( Y )= ； , ; FOLLOW(T)= ) ; FOLLOW (Y )= ) ; FOLLOW (X)= #, ； ; (3) 构造它的预测分析表(4 分) b & ( ) ；# X X b X & X (Y) Y YXY YXY YXY YY Y,XY3设文法 G（S） ：S SiA | A A A+B | B B ）A* | （1、构造各非终结符的FIRSTVT 和 LASTVT集合；2、构造优先关系表和优先函数名师资料总结 - - -精品资料欢迎下

31、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 25 页 - - - - - - - - - 答：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 （4 分）（4 分）（4 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

32、 - 名师精心整理 - - - - - - - 第 19 页，共 25 页 - - - - - - - - - (1) 划分基本块，画出流图(2) 对其中循环进行优化，画出优化后流图(1) 划分基本块，画出流图(6 分) (2) 对其中循环进行优化，画出优化后流图(6 分) 1. 构造一个DFA ，它接受 =0 ，1上所有倒数第二个字符为1 的字符串。(10) WRITE B (11) halt (4) E:=E+I (5) D:=D+I (9) goto (5) (6) B:=D+B (7) If ER goto (10) (1) READ B (2) J:=1 B1B2B3B4(3) A:

33、=I+2 (4) E:=I*J (5) D:=A+E (7) R:=I*60 B(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) J:=1 B1B2B3B4名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 25 页 - - - - - - - - - 2. 给出文法 G1（

34、S）S aSb | P P bPc | bQc Q Qa | a 消除文法的左递归，提取左公共因子后是不是LL（1）文法？请证实。3. 设文法 G（ S） ：S SiA | A A A+B | B B ） A* | （1、构造各非终结符的FIRSTVT 和 LASTVT集合；2、构造优先关系表和优先函数4. 设有基本块如下：T1:=3 T2:=A*B T3:=9+T1 M:=A*B T4:=C-D L:=T3*T4 T2:=C+D N:=T2 1、 画出 DAG 图2、 设 L，M， N 在基本块出口之后是活跃变量，给出优化后的四元式序列。得分1构造一个DFA ，它接受 =0 ，1上所有倒数第

35、二个字符为1 的字符串。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 25 页 - - - - - - - - - 2给出文法G1（S）（4 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 25 页 - - - - - - - - - S aSb | P P bPc | bQc Q Qa | a 消除文法的左递归，提取左公共因子后是不是LL

36、 （1）文法？请证实。解答：消除文法的左递归，得到名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 25 页 - - - - - - - - - 3设文法 G（S） ：S SiA | A A A+B | B B ）A* | （1、构造各非终结符的FIRSTVT 和 LASTVT集合；2、构造优先关系表和优先函数答：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 25 页 - - - - - - - - - 4设有基本块如下：T1:=3 T2:=A*B T3:=9+T1 M:=A*B T4:=C-D L:=T3*T4 T2:=C+D N:=T2 （1）画出 DAG 图（2）设 L， M，N 在基本块出口之后是活跃变量，给出优化后的四元式序列。答： （1）（2）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 25 页 - - - - - - - - -