1、 1 * 编译原理复习题 一 简答题： 1) 什么是句子？ 什么是语言 ? 解答：句子 设 G 是一个给定的文法， S 是文法的开始符号，如果 S x（其中 x VT*），则称 x 是文法的一个句子。 语言 语言是句子的集合。 或 设 GS是给定文法，则由文法 G 所定义的语言 L(G)可描述为： L(G) x S x,x VT* 。 2) DFA 与 NFA 有何区别 ? 解答 :DFA 与 NFA 的区别表现为两个方面 :一是 NFA 可以有若干个开始状态，而 DFA 仅只有一个开始状态。另一方面， DFA的映象 M是从 K到 K，而 NFA的映象 M是从 K到 K的子集，即映象 M 将产
2、生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么 ? 解答 :从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么 ? 解答 :从给定的输入串（终 结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5) 一个上下文无关文法 G 包括哪四个组成部分？ 解答 :一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答 :关键是寻找句柄。
3、 7) 在自顶向下的语法分析方法中，分析的关键是什么？ 解答 :关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号 (含终结符和非终结符 )配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则 (称为语义规则 )。在语 法分析过程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组 AG， AG=（ G， V， E）。 其中 G 为一 个上下文无关文法； V 为属性的有穷集； E 为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 2 语法制导翻译 (Synta
4、x-Directed Translations)： 一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则 描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。 10）词法分析的主要任务是什么？ 解答 :词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。 11)图示运行时存储空间的划分（分为哪几个区）。 解答 : 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆
5、区 12)常用的中间语言种类有哪几种？ 解答 : 常用的中间语言种类有逆波 兰表示、三元式、四元式和树形表示。 13）文法 G所描述的语言是什么的集合？ 解答 :是 由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即 0型、 1 型、 2 型、 3型。其中 2 型文法叫什么？ 解答 : 2 型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答 :常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？ 解答 :语法分析的任务是识别给定的终结符串是否为给定文法的句子。 17）局部优化是局限于一
6、个什么范围内的一种 优化？ 解答 : 是局限于一个基本块范围内的一种优化。 18）通常一个编译程序中应包括哪七个部分？ 解答 : 通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。 19）代码优化的主要目标是什么？ 解答 : 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。 20） .符号表的组织方式有哪几种？ 答：一个编译程序对符号表的总体组织可有三种选择： 目标代码 静态数据 栈 堆 3 第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为 等长的多个符号表。这样组织
7、的最大优点是每个符号表的属性个数和结构完全相同。则表项是等长的，并且表项中的每个属性栏都是有效的，对于单个符号表示来说，这样使得管理方便一致，空间效率高。但这样组织的主要缺点是一个编译程序将同时管理若干个符号表，增加了总体管理的工作量和复杂度。而且对各类符号共同属性的管理必须设置重复的运行机制。使得符号表的管理显得臃肿。 第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表。这样组织方式的最大优点是总体管理非常集中单一，且不同种类符号的共同属性 可一致地管理和处理。这样组织所带来的缺点是，由于属性的不同，为完整表达各类符号的全部属性必将出现不等长的表项，以及表
8、项中属性位置的交错重叠的复杂情况，这就极大地增加了符号表管理的复杂度。为使表项等长且实现属性位置的唯一性，可以把所有符号的可能属性作为符号表项属性。这种组织方法可能有助于降低符号表管理复杂性，但对某个具体符号，可能增加了无用的属性空间，从而增加了空间开销。 第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。这种折衷的组织方式在管理复杂性及时空效率 方面都取得折衷的效果，并且对复杂性和效率的取舍可由设计者根据自己的经验和要求及目标系统的客观环境和需求进行选择和调整。 21） . 在整个编译期间，对于符号表的操作有哪些？ 答： 在整个编译期间，对于符
9、号表的操作大致可归纳为五类： 对给定名字，查询此名是否已在表中； 往表中填入一个新的名字； 对给定名字，访问它的某些信息； 对给定名字，往表中填写或更新它的某些信息； 删除一个或一组无用的项。 22） .符号表的作用有哪些？ 答：在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中 反映了标识符的语义特征属性。起主要作用是： 收集符号属性； 上下文语义的合法性检查的依据； 作为目标代码生成阶段地址分配的依据。 23） . 简述优化的 原则是什么？ 答：编译程序提供的对代码 优化 必须遵循的原则是： 4 （ 1） 等价原则。经过优化后不应改变程序运行的结果。 （ 2） 有
10、效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。 （ 3） 合算原则。应尽可能以较低的代价取得较好的优化效果。 24）简述 常用的优化技术有哪些？ 答：编译程序中常用的优化技术有： 删除公共子表示式；复写传播；删除无用代码；代码外 提；强度削弱；删除归纳变量；合并常量 。 25 ） . 何 谓 优 化 ？ 按 所 涉 及 的 程 序 范 围 可 分 为 哪 几 级 优 化 ？ 答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化。 26)、编译程序目标代码运行时的存储区通常被划分为几部分？ 答： 目标代码区
11、、静态数据区、栈区、堆区。 27)、 数组的内情向量包含哪些内容？ 在编译程序对数组说明进行语义处理时，须把数组的类型 type、维数 n、各维的上、下界 lk,uk等有关信息记录下来。此外 ,如果数组是常界的 ,还可将各 维的界差 dk 以及计算数组元素地址的常量 C 记录下来。为了便于引用，通常是把上述信息存放于数组相应的 “ 内情向量 ” 之中 .对数组内情向量的访问 ,可通过数组在符号表中相应登记项的 ADDR 域以间接寻址方式进行（即将其ADDR 域作为指针用于存放内情向量的首地址）。 28)、 文法分为几种类型？其分类依据是什么？ 答：分为四类：短语文法（ 0 型文法）、前后文有关
12、文法（ 1 型文法）、前后文无关文法（ 2 型文法）、正规文法（ 3 型文法）。分类依据：对产生式家约束。 29)、一般来说编译程序至少包含哪几部分？各部分的作用是什么？ 答：词法 分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。 各部分的作用参见教材 30）、分程序结构的栈式存储管理中的活动记录包括哪些内容？ 答： 临时工作单元、局部变量、保存机器状态、存取链、控制链、实参，也称形式单元、返回地址，保存该被调过程返回后的地址。 31）、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？为什么？
13、答：不正确 词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量 而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。 二、 应用题 5 1） 写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。 解：文法 G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D 2）写一个文法，使其语言是无符号二进制实数（不含指数）。 解答 :文法 G(N)： N L.L|L L LB|B B 0|1 3）给出上下文无关文法的定义。 一个上下文无关文法 G 是一个四元式 (VT， VN， S， P)，其中： VT是一个非空有限集，它
14、的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符号， VT VN=； S 是一个非终结符号，称为开始符号； P 是一个产生式集合 (有限 )，每个产生式的形式是 P，其中， P VN， (VT VN)*。 开始符号 S 至少必须在某个产生式的左部出现一次。 4）给出正规式与正规集的递归定义。 (1)和都是上的正规式，它们所表示的正规集分 别为 和； (2)任何 a， a 是上的一个正规式，它所表示的正规集为 a； (3)假定 U和 V都是上的正规式，它们所表示的正规集分别记为 L(U)和 L(V)，那么， (U|V)、(U V)和 (U)*也都是正规式，它们所表示的正规
15、集分别为 L(U) L(V)、 L(U)L(V)(连接积 )和(L(U)*(闭包 )。 仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集。 5）设文法 G 为： S aAcB|BdS A BaB|aBc|a 6 B aScA|cAB|b 对于输入串 aacabccb，给出最左推导。 答： S=aAcB=aaBccB=aacABccB=aacaBccB=aacabccB=aacabccb 6） 设文法 G 为： S BA A BS|d B aA|bS|c 对于输入串 adccd，给出最左推导。 答： S=BA=aAA=adA=adBS=adcS=ad
16、cBA=adccA=adccd 7）给定正规文法 G: S aS|bA|b A aS 请构造与之等价的有限自动机。 8）给定正规文法 G: S aA A bA|aB|b B aA 请构造与之等价的有限自动机。 9）对下面给出的 NFA 确定化。 A BD F b b a a S a S FD A a b a b S FD A a b a b a 2 4D 3 a b a a 1 b a 7 10） .将文法 GS 改写为等价的 GS ，使 GS 不含左递归和左公共因子。 GS： SbSAe | bA AAb | d 答 ： 文法 GS 改写为等价的不含左递归和左公共因子的 GS为： SbB B
17、SAe | A Ad A A bA | 11） 消除下列文法 GA的左递归。 A AaB B B BbC C C eD D D (A) d 解答：消除文法 GA的左递归后得到： A BA A aBA B CB B bcB C eD D D (A) d 12） 正规式（ a|b） *a(a|b) 构造一个 等价的 有限自动机。 解答： 13） 将下图的 NFA 确定化为 DFA。 答 ： 用子集法确定化如下表 a,b a a b 0 1 2 8 I Ia Ib 状态 X,1,2 1,2. 1,2,3 1,2,Y 1,2. 1,2. 1,2,Y 1,2. 1,2,3 1,2,3 1,2,3 1,2
18、,3 X 1 2 3 确定化 后如下图： 14） . 已知文法 G(E) E T|E T TF|T *F F (E)|i (1)给出句型 (T *F i)的最右推导 ； (2)给出句型 (T *F i)的短语、简单短语、句柄、素短语、最左素短语。 解 ： (1) 最右推导 ： E -T-F-(E)-(E T)-(E F)-(E i)-(T i)-(T*F i) (2) 短语 ： (T*F i) ， T*F i ， T*F， i 简单短语： T*F,i 句柄： T*F 素短语 ： T*F,i 最左素短语： T*F 15） . 构造正规式 1(0|1)*101 相应的 DFA 。 解 ： 先构造
19、NFA ： 9 确定化 ： 重新命名 ， 令 AB 为 B、 AC 为 C、 ABY 为 D 得 ： 所以 ， 可得 DFA 为 ： 16） . 文法 ： S-MH|a H -LSo| K -dML| L -eHf M-K|bLM 判断 G 是否为 LL(1) 文法 ， 如果是 ， 构造 LL(1) 分析表。 解 ： 各 符号的 FIRST 集和 FOLLOW集为 ： 10 预测分析表 由于预测分析表中无多重入口 ， 所以可判定文法是 LL(1)的 17） . 对下面的文法 G ： E -TE E-+E| T -FT T -T| F- PF F- *F| P-(E)|a|b| (1)计算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 (4 分 ) (2) 证明这个方法是 LL(1) 的。 (4 分 ) (3) 构造它的预测分析表。 (2 分 ) 解：（ 1）计 算这个文法的每个非终结符的 FIRST 集和 FOLLOW 集。 FIRST 集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; FIRST(T)=FIRST(T)U =(,a,b, ; FIRST(F)=FIRST(P)=(,a,b,;
