编译原理复习题2017.docx

PAGE PAGE 3 编译原理复习题 一．简答题： 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S * 称 x 是文法的一个句子。 语言——语言是句子的集合。  x（其中x∈V *），则 T 或—— 设 G[S] 是给定文法， 则由文法 G 所定义的语言 L(G) 可描述为： L(G) ＝ {x │ S DFA 与 NFA 有何区别 ? x,x∈V *} 。 T 解答:DFA 与 NFA 的区别表现为两个方面:一是 NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态。另一方面，DFA 的映象M 是从K×∑到 K，而NFA 的映象M 是从K×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 一个上下文无关文法 G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。 在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G 为一个上下文无关文法；V 为属性的有穷集；E 为一组语义规则。9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。语法制导翻译(Syntax-Directed Translations)： – 一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义 属性值。 10）词法分析的主要任务是什么？ 目标代码静态数据栈?? 目标代码静态数据栈 ? ? 堆 11)图示运行时存储空间的划分（分为哪几个区）。解答: 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆区12)常用的中间语言种类有哪几种？ 解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。13）文法 G 所描述的语言是什么的集合？ 解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法叫什么？ 解答: 2 型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。16）语法分析的任务是什么？ 解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。17）局部优化是局限于一个什么范围内的一种优化？ 解答: 是局限于一个基本块范围内的一种优化。18）通常一个编译程序中应包括哪七个部分？ 解答: 通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化， 目标代码生成以及表格处理和出错处理等七个部分。 代码优化的主要目标是什么？ 解答: 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。 20）.符号表的组织方式有哪几种？ 答：一个编译程序对符号表的总体组织可有三种选择： 第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表。这样组织的最大优点是每个符号表的属性个数和结构完全相同。则表项是等长的，并且表项中的每个属性栏都是有效的，对于单个符号表示来说，这样使得管理方便一致，空间效率高。但这样组织的主要缺点是一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度。而且对各类符号共同属性的管理必须设置重复的运行机制。使得符号表的管理显得臃肿。 第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表。这样组织方式的最大优点是总体管理非常集中单一，且不同种类符号的共同属性可一致地管理和处理。这样组织所带来的缺点是，由于属性的不同，为完整表达各类符号的全部属性必将出现不等长的表项，以及表项中属性位置的