《编译原理》期末考试复习题

《《编译原理》期末考试复习题》由会员分享，可在线阅读，更多相关《《编译原理》期末考试复习题（29页珍藏版）》请在金锄头文库上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流编译原理期末考试复习题.精品文档.编译原理期末考试复习题一、是非题（请在括号内，正确的划，错误的划）（每个2分，共20分）1计算机高级语言翻译成低级语言只有解释一种方式。()2在编译中进行语法检查的目的是为了发现程序中所有错误。()3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 ()4正则文法其产生式为 A-a ， A-Bb, A,BVN ， a 、 bVT 。 ()5每个文法都能改写为 LL(1) 文法。 ()6递归下降法允许任一非终极符是直接左递归的。 ()7算符优先关系表不一定存在对应的优先函数。

2、()8自底而上语法分析方法的主要问题是候选式的选择。 ()9LR 法是自顶向下语法分析方法。 ()10简单优先文法允许任意两个产生式具有相同右部。 ()三、填空题(每空1分，共10分)1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_ _和 _ _。 表格管理 出错处理_2若源程序是用高级语言编写的,_ _是机器语言程序或汇编程序,则其翻译程序称为 _ _ 。_目标程序 _编译程序3编译方式与解释方式的根本区别在于_ _。是否生成目标代码_4对编译程序而言,输入数据是_ _, 输出结果是_ _。_源程序 目标程序5产生式是用于定

3、义_ _的一种书写规则。 _语法成分6语法分析最常用的两类方法是_ _和_ _分析法。 自上而下 _自下而上四、简答题（20分）1. 什么是句子？ 什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中xVT*),则称x是文法的一个句子。 (2)设GS是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)xS x,xVT* 。参考答案：(每个2分，共4分)答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中xVT*),则称x是文法的一个句子。 (2)设GS是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)xS x,xVT* 。

4、一、是非题（请在括号内，正确的划，错误的划）（每个2分，共20分）1对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。()2甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。()3递归下降分析法是自顶向上分析方法。()4产生式是用于定义词法成分 的一种书写规则。 ()5LR 法是自顶向下语法分析方法。 ()6在 SLR （ 1 ）分析法的名称中，S的含义是简单的。()7综合属性是用于 “ 自上而下 ” 传递信息。()8符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占单元大小、地址等等。 ()9程序语言的语言处理程序是一种应

5、用软件。 ()10解释程序适用于 COBOL 和 FORTRAN 语言。 ()三、填空题(每空1分，共10分)1一个句型中的最左简单短语称为该句型的_句柄_。 2对于文法的每个产生式都配备了一组属性的计算规则，称为 _语义规则_ 。3一个典型的编译程序中，不仅包括_词法分析_、_语法分析_、_中间代码生成_、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。4 从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。5 扫描器的任务是从_源程序_中识别出一个个_单词符号_。 6 产生式是用于定义_语法范畴_的一种书写规则。 一、是非题（请在括号内，正确的划，错误的

6、划）（每个2分，共20分）1编译程序是对高级语言程序的解释执行。()2一个有限状态自动机中，有且仅有一个唯一的终态。() 3一个算符优先文法可能不存在算符优先函数与之对应。 ()4语法分析时必须先消除文法中的左递归 。 ()5LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 ()6逆波兰表示法表示表达式时无须使用括号。 ()7静态数组的存储空间可以在编译时确定。 ()8进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 () 9两个正规集相等的必要条件是他们对应的正规式等价。 ()10一个语义子程序描述了一个文法所对应的翻译工作。 ()三、填空

7、题(每空1分，共10分)1计算机执行用高级语言编写的程序主要有两种途径：_ _和_ _。解释_编译2扫描器是_ _，它接受输入的_ _，对源程序进行_ _并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。词法分析器 源程序 词法分析3自上而下分析法采用_ _、归约、错误处理、_ _等四种操作。移进_接受4一个LR分析器包括两部分：一个总控程序和_ _。一张分析表5后缀式abc-/所代表的表达式是_。 _a/(b-c)6局部优化是在_范围内进行的一种优化。_基本块_一、是非题（请在括号内，正确的划，错误的划）（每个2分，共20分）1设r和s分别是正规式，则有L(r|s)=L(r)L

8、(s)。()2确定的自动机以及不确定的自动机都能正确地识别正规集。()3词法分析作为单独的一遍来处理较好。 ( )4构造LR分析器的任务就是产生LR分析表。 ()5规范归约和规范推导是互逆的两个过程。 ( )6同心集的合并有可能产生新的“移进”/“归约”冲突。 ( )7LR分析技术无法适用二义文法。 ( )8树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 ()9程序中的表达式语句在语义翻译时不需要回填技术。 ()10对中间代码的优化依赖于具体的计算机。 ( )三、填空题(每空1分，共10分)1词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。 2语法分析基于_上下文无关

9、_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。3分析句型时，应用算符优先分析技术时，每步被直接归约的是_最左素短语_，而应用LR分析技术时，每步被直接归约的是_句柄_。4语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰_、_四无式表示_与_三元式表示_等。一、是非题（请在括号内，正确的划，错误的划）（每个2分，共20分）1一个 LL(l)文法一定是无二义的。 ( ) 7LR 法是自顶向下语法分析方法。 ( )2正规文法产生的语言都可以用上下文无关文法来描述。 ( )3一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 ()4目标代码生成时

10、，应考虑如何充分利用计算机的寄存器的问题。 ( )5逆波兰法表示的表达式亦称前缀式 。 ( )6如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 ( )8数组元素的地址计算与数组的存储方式有关。( )9算符优先关系表不一定存在对应的优先函数。 ()10对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 ()三、填空题(每空1分，共10分)1语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规进行的。2语法分析器的输入是_单词符号串_，其输出是_语法单位_。3一个名字的属性包括_类型_和_作用域_。4产生式是用于定义_语法成分_的一种书写规

11、则。5逆波兰式 ab+c+ d*e- 所表达的表达式为_(a+b+c)*d-e_ 。 6语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。 二、填空题（每空2分，共22分）1已知文法GS：S(A)|a ，AAcS|S|b ；该文法的开始符号是 S，非终结符号集合为 S,A，终结符号集合为a,b,c,(,)。2描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。3自上而下的语法分析方法有LL(1)和递归下降方法。4设有文法GS：SSa|a ，构造它的拓广文法，引入一个产生式：SS ；则I。=Closure（SS，）= SS，, SSa，/a, Sa，/a。5在LR（0）项目

12、集规范族中，若有项目：，其中，称该项目为移进项目。6.LL(1)语法分析方法中应解决的主要问题是消除回溯；LR语法分析方法中应解决的主要问题是项目冲突。三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共16分）1一个文法有二义性，则由它描述的语言一定具有二义性。（错 ）2若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（正 ）3若有正规式a*b，则与之等价的文法应该是GA：AaA|b 。（ 正 ）4设有文法GA：AaB ，BbB|b，则该文法是LL(1)文法。（错 ）5由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（ 错 ）6最左素短语是

13、句型最左边的短语。（错 ）7LR语法分析法是一种规范规约的分析方法。（正 ）8存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（ 错 ）1. 文法G的一个句子对应于多个推导，则G是二义性的。（ ）2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（ ）3. 算符优先文法采用“移进规约”技术，其规约过程是规范的。（ ）4. 删除归纳变量是在强度削弱以后进行。（ ）5. 在目标代码生成阶段，符号表用于目标代码生成。（ ）一 填空题（每空2分，共20分）1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储

14、分配方案，而后者又分为（1） 和 （2） 。2. 规范规约是最（3）规约。3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。4表达式x+y*z/(a+b)的后缀式为 （7） 。5文法符号的属性有综合属性和 （8）。6假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a1.15,1.20某个元素ai，j的地址计算公式为（9）。7局部优化是局限于一个（10）范围内的一种优化。答案：(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左(4) 语法分析(5) 目标代码生成(6) 表格管理(7) xyz*ab+/+(8) 继承属性(9) a+(i-1)*20+j-1(10) 基本块一、 填空题（每空2分，共20分）1目标程序 （target code）