《编译原理》第三版期末复习.doc

期末复习总结编译原理第一章：绪论一、填空问题由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格管理和出错处理。如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。1-02.若源程序是用高级语言编写的,目标程序是 机器语言程序或汇编程序 ,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于 是否生成目标代码 .1-05.对编译程序而言,输入数据是 源程序 ,输出结果是 目标程序 .1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括 (1)c .其中, (2)b 和代码优化部分不是每个编译程序都必需的.词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d . (1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器 (2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成 (3) a.字符串 b.语句 c.单词 d.标识符 (4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主要区别在于 (3)d . (1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统 (2) a.高级语言程序和低级语言程序 b.解释程序和编译程序 c.编译程序和操作系统 d.系统程序和应用程序 (3) a.单用户与多用户的差别b.对用户程序的查错能力c.机器执行效率 d.是否生成目标代码1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .a.汇编语言程序 b.机器语言程序 c.高级语言程序d. a 或者 b e. a 或者 c f. b 或者 c1-13.下面关于解释程序的描述正确的是 b . (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效. 与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法. (1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化 (2): a.比较简单,可移植性好,执行速度快 b.比较复杂,可移植性好,执行速度快 c.比较简单,可移植性差,执行速度慢 d.比较简单,可移植性好,执行速度慢 (3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行 d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 a 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .a. 源程序 b. 目标程序 c. 函数 d. 过程 e. 机器指令代码 f. 模块 g. 连接程序 h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c , d , f .a. 汇编语言 b. 高级语言 c. 源语言 d. 目标语言e. 程序设计方法 f. 编译方法 g. 测试方法 h. 机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成 (1)d ,诸阶段的工作往往是 (2)d 进行的. (1) a. 过程 b. 程序 c. 批量 d.遍 (2) a. 顺序 b. 并行 c. 成批 d.穿插1-18.编译程序与具体的机器 a , 与具体的语言 a .a. 有关 b.无关1-19.使用解释程序时,在程序未执行完的情况下， a 重新执行已执行过的部分.a. 也能 b.不可能1-20.编译过程中,语法分析器的任务就是 b . (1) 分析单词是怎样构成的 (2)分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4)1-21.编译程序是一种常用的 b 软件.a. 应用 b. 系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步. (1) 编辑 (2) 编译 (3) 连接 (4) 运行a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4)1-23.编译程序必须完成的工作有 a . (1) 词法分析 (2) 语法分析 (3) 语义分析 (4) 代码生成 (5) 之间代码生成 (6) 代码优化a. (1)(2)(3)(4) b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6) d. (1)(2)(3)(4)(6) e. (1)(2)(3)(5)(6)1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法 a .a. 不正确 b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.a. 编译器 b. 汇编器 c. 解释器 d. 预处理器1-26.编译程序生成的目标程序 b 是机器语言的程序.a. 一定 b. 不一定1-27.编译程序生成的目标程序 b 是可执行的程序.a. 一定 b. 不一定1-28编译程序是一种 B 。A. 汇编程序 B. 翻译程序 C. 解释程序 D. 目标程序1-29按逻辑上划分，编译程序第二步工作是 C 。A. 语义分析 B. 词法分析 C. 语法分析 D. 代码优化1-30通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括 C 。A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器1) 把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？解答: 由汇编器（汇编程序）完成的。19）编译程序是一种解释程序吗？还是什么程序？解答:编译程序是一种翻译程序。二、判断问题高级语言程序必须经过编译程序的翻译才被计算机识别和执行。（错）答：对高级语言的翻译，还有解释程序。编译程序的输入是高级语言，输出是机器语言程序。（错）答：输出还有汇编语言程序。具有优化功能的编译程序的工作效率高。（错）答：优化是编译程序的的一部分，优化的目的，是提高目标程序的质量和运行效率。有的编译程序可以没有目标代码生成部分。（错）答：编译程序必须生成目标代码，所以目标代码生成部分是不可缺少的。1-31.计算机高级语言翻译成低级语言只有解释一种方式。 （）1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。 （）第二章：词法分析一、填空题1、编译过程中扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位单词。2、高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符以及界限符。3、确定的有限自动机是一个五元组，通常表示为DFAM=（S，S，d，S0，F）。4、词法分析的任务是输入源程序，输出单词符号。5、确定有限自动机DFA是NFA的一种特例。6、若二个正规式所表示的正规集相同，则认为二者是等价的。8-01.符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占单元大小、地址等等。6-04.终结符只有 综合属性 ，它们由词法分析器提供。二、判断题1、一些语言，它们能被确定的有限自动机识别，但不能用正规表达式表示。（错）答：用正规式表示的语言，都能被确定的有限自动机识别。2、每一个NFAM都对应有唯一的一个最小化的DFAM。（对）答：每一个NFAM都可以构造一个DFAM，而DFAM又可以构造一个最小化的DFAM。3、 一个有限自动机，仅有一个唯一的终态。（错）答：有限自动机的终态可以有多个。4、 确定的有限自动机以及不确定的有限自动机都能正确识别正规集。（对）答：一个有限自动机能识别该正规式，所描述的语言（正规集）。5、 对任意一个正规文法G，都存在一个DFAM，满足L（G）=L（M）。（对）答：对每一个正规文法G，都存在一个DFAM，使得L（G）=L（M）。1、正规文法一定不是二义性的。（错）答：文法的二义性问题是不可避免和不可判定的，正规文法也可能存在二义性的问题。2、文法的二义性和语言的二义性是两个不同的概念。（对）答：可能有两个不同的文法G和G，其中G是二义性的，但是却有L（G）=L（G）。3、一个句型对应的一棵语法树，包括了该句型的所有推导。（错）答：一棵语法树，只能对应一个推导，所以不能包括该句型的所有推导。三、选择题1、在词法分析中能识别出a，c，e。a、关键字b、四元式c、运算符d、逆波兰式e、常数2、令=a，b，则上所有以b开头，后跟若干个ab的字的全体对应的正规式b，d。a、b（ab）*b、b（ab）+c、（ba）*bd、（ba）+be、b（ba）*3、词法分析所依据的是b。a、语义规则b、词法规则c、语法规则d、等价变换规则4、正规式V1和V2等价是指c。a、V1和V2的状态数相等b、V1和V2的有向弧条数相等c、V1和V2所识别的语言集相等d、V1和V2状态数和有向弧条数相等5、 令=a，b，正规式abc代表的正规集b。a、b、，c、d、，6、有限状态自动机能识别 正规文法 。三、简答题1、什么是扫描器？扫描器的功能是什么？扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析使用。2) DFA与NFA有何区别 ? 解答:DFA与NFA的区别表现为两个方面:一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。另一方面，DFA的映象M是从K到K，而NFA的映象M是从K到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3) 词法分析器是用于做什么的？解答:词法分析器是用于识别单词的。15)词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。第3章 ：语法分析6)句柄答：句柄给定句型中的最左简单短语就是句柄。7)句型答：句型设G是一个给定的文法，S是文法的开始符号，如果Sx(其中xV*),则称x是文法的一个句型。*8)句子答：句子设G是一个给定的文法，S是文法的开始符号，如果S x（其中xVT*），则称x是文法的一个句子。9)非终结符答：非终结符出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。10)终结符答：终结符出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。11）属性文法答：一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。二简答题：1) 什么是句子？ 什么是语言?*解答：句子设G是一个给定的文法，S是文法的开始符号，如果S x（其中xVT*），则称x是文法的一个句子。语言语言是句子的集合。或设GS是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)xSx,xVT* 。2) 自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。3) 自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。4) 一个上下文无关文法G包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。5) 在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。6) 在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。7) 若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？解答: 它所产生的语言的句子不是可枚举的，而是无穷多个。17）文法G所描述的语言是什么的集合？解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？解答: 2型文法叫上下文无关文法。25）语法分析的任务是什么？解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。37）写一个文法，使其语言是无符号二进制实数（不含指数）。解答:文法G(N)： NL.L|L LLB|B B0|128）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？解答: 均是终结符集。34）说明下面文法GS是二义性文法：SSaS|SbS|cSd|eS|f解答:fafbf是文法GS的一个句子，并且有两个不同的最右推导。（1）S = SaS = SaSbS = SaSbf= Safbf= fafbf （2）S = SbS = Sbf= SaSbf = Safbf= fafbf因此说明此文法有二义性。27）文法等价的定义是什么？解答: 设G1和G2是给定的文法，如果有L（G1）= L（G2），则称G1与G2等价。5-19.自底向上分析法的原理是什么？答：在采用自左向右扫描，自底向上分析的前提下，该类分析方法是从输入符号串入手，通过反复查找当前句型的句柄（最左简单短语），并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。5-20.简单优先方法基本思想是什么？答：简单优先方法基本思想是首先规定文法符号之间的优先关系和结合性质，然后在利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定句型的“句柄”并进行归约。5-21.三种优先关系的定义是什么？答：三种优先关系的定义是：1. si（1）sisj sj 当且仅当存在形如下面的产生式USiSj2. sisj 当且仅当存在形如下面的产生式USiW的生产式，且有 WSj3. sisj 当且仅当存在形如下面的产生式UVW的生产式,且有 VSi和WSj5-22.如何确定简单优先文法的句柄？答：设S1S2Sn是简单优先文法的规范句型，其子串SiSi+1Sj是满足下列条件的最左子串：Si-1 SiSi Si+1 Sj-1 SjSj Sj+1则SiSi+1Sj定是S1S2Sn的句柄。2-01.所谓最右推导是指： 任何一步都是对中最右非终结符进行替换的 。2-02.一个上下文无关文法所含四个组成部分是 一组终结符号、一组非终结符号、一个开始符号、一组产生式 。2-03.产生式是用于定义 语法成分 的一种书写规则。2-04.设GS是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)xSx,xVT* 。2-05.设G是一个给定的文法，S是文法的开始符号，如果Sx（其中xV*），则称x是文法的一个句型 。2-06.设G是一个给定的文法，S是文法的开始符号，如果Sx(其中xVT*),则称x是文法的一个句子。1、自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。2、自上而下语法分析方法会遇到的主要问题有回溯和左递归。3、在自上而下语法分析中，应先消除文法的间接左递归，再消除文法的直接左递归。4、在语法分析中，最常见的两种方法是自上而下分析法，另一种是自下而上分析法。4-01.语法分析最常用的两类方法是 自上而下 和 自下而上 分析法。4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。4-03.递归下降法不允许任一非终极符是直接 左 递归的。4-04.自顶向下的语法分析方法的关键是 如何选择候选式 的问题。4-05.递归下降分析法是自顶向上 分析方法。4-06.自顶向下的语法分析方法的基本思想是：从文法的 开始符号 开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的 句子 ，使之与给定的输入串匹配。5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的 开始符号 。5-03.简单优先方法每次归约当前句型的 句柄 ，算符优先方法每次归约当前句型的 最左素短语 ，二者都是不断移进输入符号，直到符号栈顶出现 可归约串 的尾，再向前找到 可归约串 的头，然后归约。5-04.在LR（0）分析法的名称中，L的含义是 自左向右的扫描输入串 ，R的含义是 最左归约 ，0 的含义是 每步最多向前检查0个输入符号 。5-05.在SLR（1）分析法的名称中，S的含义是 简单的 。对于一文法，如果能够构造一张分析表，使得它的每一个入口均是唯一确定的，则称该文法为LR文法。自下而上语法分析法的基本思想是：从待输入的符号串开始，利用文法的产生式步步向上进行直接归约，试图归约到文法的开始符号（识别符号）。字的活前缀是指该字的任意首部。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何句型。对LR分析表的构造，有可能存在C、E动作冲突。A、归约B、移进C、移进-归约D、移进-移进E、归约-归约自上而下的语法分析方法A、C、D、E有。A、算符优先分析法B、LL（1）分析法C、LR（0）分析法D、SLR（1）分析法E、LALR（1）分析法每一项ACTIONs，a所规定的动作包括A、C、D、E。A、归约B、比较C、移进D、接受E、报错2-07文法G所描述的语言是 C 的集合。A.文法G的字母表V中所有符号组成的符号串B.文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有终极符串D.由文法的开始符号推出的所有符号串2-08乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是 B 。A. 短语文法（0型） B.正则文法 C.上下文有关文法（1型） D.上下文无关文法（2型）5-06在自底向上的语法分析方法中，分析的关键是 D 。A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。A.句柄 B. 前缀 C. 活前缀 D. LR(0)项目2-10一个句型中的最左 B 称为该句型的句柄。可选项有：A. 短语 B. 简单短语 C. 素短语 D. 终结符号2-11设G是一个给定的文法，S是文法的开始符号，如果Sx(其中xV*),则称x是文法G的一个 B 。A. 候选式 B. 句型 C. 单词 D. 产生式2-15文法的二义性和语言的二义性是两个 A 的概念。A 不同 B 相同 C 无法判断 D 不存在3-02词法分析器用于识别 C 。A. 句子 B. 句型 C. 单词 D. 产生式4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非终极符集 B.终极符集 C. 字母表 D. 状态集4-08.编译程序中语法分析器接收以 A 为单位的输入。A. 单词 B. 表达式 C. 产生式 D. 句子2-13.文法GE：ETETTFTF Fa（E）该文法句型EF(ET)的简单短语是下列符号串中的 B 。（ET） ET F F(ET)可选项有：A) 和 B) 和 C) 和 D) 2-14若一个文法是递归的，则它所产生的语言的句子 A 。A.是无穷多个 B.是有穷多个 C.是可枚举的 D.个数是常量2-15.正则文法其产生式为Aa，ABb, A,BVN，a、bVT。 ）4-09.每个文法都能改写为LL(1)文法。 （）4-10.递归下降法允许任一非终极符是直接左递归的。（）5-08.算符优先关系表不一定存在对应的优先函数。（）5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（）5-13.一个句型的句柄一定是文法某产生式的右部。（）5-09.自底而上语法分析方法的主要问题是候选式的选择。（）5-10.LR法是自顶向下语法分析方法。（）5-11.简单优先文法允许任意两个产生式具有相同右部。 （）三应用题1）消除下列文法GA的左递归。EE-TTTT/FFF( E )i解答：消除文法GE的左递归后得到：ETEE-T ETFTT/FTF( E )i2） 消除下列文法GA的左递归。AAaBBBBbCCCeDDD(A)d解答：消除文法GA的左递归后得到：A BA AaBAB CBBbcBCeDDD(A)d四设计题（1）给定文法GS 及相应翻译方案为：1SS print:“a”2Sr D print:“b”3DD，i print:“c”4Di print:“d”a. 按chomsky分类法，文法G属于哪一型文法？ b. 符号串ri,i,i是不是该文法的一个句型，请证实。 c. 若是句型，写出该句型的所有短语、简单短语，以及句柄。解答：a文法G属于2型(上下文无关)文法。b符号串r i,i,i是该文法的一个句型。证：SSrDrD，i rD，i，i r i，i，i，得证。或证：构造语法树见图4，可知符号串r i,i,i是该文法的一个句型。c句型r i,i,i的短语有：r i,i,i； i,i,i；i,i； 第一个i简单短语有：第一个i 句柄有：第一个i2-20.已知文法GE为：ET|E+T|E-TTF|T*F|T/FF（E）|i 该文法的开始符号（识别符号）是什么？请给出该文法的终结符号集合VT和非终结符号集合VN。 找出句型T+T*F+i的所有短语、简单短语和句柄。解： 该文法的开始符号（识别符号）是E。该文法的终结符号集合VT=+、-、*、/、（、）、i。非终结符号集合VN=E、T、F。句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;简单短语为i、T*F、第一个T;句柄为第一个T。4-14.在LL(1)分析法中,LL分别代表什么含义?答:第一个L代表从左到右的扫描，第二个L代表每次进行最左推导。4-15.自顶向下分析思想是什么？答：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。4-16.自顶向下的缺点是什么？答：在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。4-17.LL（1）文法的定义是什么？答：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A,A；满足SELECT(A )SELECT(A )=。其中，、不能同时。4-18.什么是文法的左递归？答：一个文法含有下列形式的产生式之一时：1)AA，AVN，V*2)AB，BA，A、BVN，、V* 则称该文法是左递归的。4-19.递归下降法的主要思想是什么？答：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。