2022年编译原理期末复习总结 .pdf

《2022年编译原理期末复习总结 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理期末复习总结 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备欢迎下载一、简答题1.什么是编译程序？答： 编译程序是一种将高级语言程序(源程序 )翻译成低级语言 (目标程序 )的程序 。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言 ,机器语言 )程序的翻译程序。2.请写出文法的形式定义？答： 一个文法 G 抽象地表示为四元组 G=（Vn,Vt,P,S） 其中 Vn 表示非终结符号 Vt 表示终结符号， VnVt=(字母表 )，VnVt= S是开始符号， P是产生式，形如： (V+且至少含有一个非终结符号，V*) 3.语法分析阶段的功能是什么？答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、

2、表达式 )。确定整个输入串是否构成语法上正确的程序。4.局部优化有哪些常用的技术？答： 优化技术 1删除公共子表达式优化技术 2复写传播优化技术 3删除无用代码优化技术 4对程序进行代数恒等变换（降低运算强度）优化技术 5代码外提优化技术 6强度削弱优化技术 7删除归纳变量优化技术简介 对程序进行代数恒等变换（代数简化）优化技术简介 对程序进行代数恒等变换（合并已知量）5编译过程分哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6. 什么是文法？答：文法是描述语言的语法结构的形式规则。是一种工具，

3、它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合； 文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。7. 语义分析阶段的功能是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译 (翻译成中间代码 )；并对静态语义进行审查。8.代码优化须遵循哪些原则？答： 等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果9.词法分析阶段的功能是什么？答：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 15 页学习必备欢迎下载逐个读入源程

4、序字符并按照构词规则切分成一系列单词任务：读入源程序，输出单词符号 滤掉空格，跳过注释、换行符 追踪换行标志，指出源程序出错的行列位置 宏展开， 10.什么是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。11.什么是属性文法？答：是在上下文无关文法的基础上， 为每个文法符号 (含终结符和非终结符 )配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义

5、规则 )。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。12.什么是基本块 ? 答： 是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句。13.代码优化阶段的功能是什么？答： 对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间 )。14.文法分哪几类？答： 文法有四种 :设有 G=(Vn,Vt,P,S),不同类型的文法只是对产生式的要求不同：型文法 (短文文法 )： G 的每个产生式 满足：V+且中至少含有一个非终结符 ,V* 型文法 (上下文有关文法 )： 如果 G 的每个产生式 均满足 |=|,仅当

6、除外，但 S不得出现在任何产生式的右部型文法 (上下文无关文法 )：G 的每个产生式为 A, A 是一非终结符， V* 型文法 (正规文法 )：G 的每个产生式的形式都是：AB 或 A，其中 A,B 是非终结符， 是终结符串。 (右线性文法 )。15.循环优化常用的技术有哪些？答： 代码外提；强度削弱；删除归纳变量。16.什么是算符优先文法？答： 算符文法G 的任何终结符a,b 之间要么没有优先关系，若有优先关系,至多有中的一种成立 ,则 G 为一算符优先文法。二、计算题（一）推导、最左推导、最右推导和语法树,复习表达式文法及相关例题。1. 表达式的推导例： G = (E, i, +, *,

7、(, ) , P , E) P： E E+E | E*E | (E) | i 答：表达式 (i)和(i+i)*i 的推导：E (E) (i) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 15 页学习必备欢迎下载(i+i)*i 的最左推导过程：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*

8、i (i+i)*i 的最右推导过程：E E*E E*i (E + E)*i (E+ i)*i (i + i)*i 2语法树例：对文法 G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 答： 句子(i+i)*i 的语法树：例： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 答：句子 ( i * i + i) 的语法树：(1)E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) 精选学习资料 - - -

9、- - - - - - 名师归纳总结 - - - - - - -第 3 页，共 15 页学习必备欢迎下载（二）给定语言求文法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 15 页学习必备欢迎下载（三）逆波兰式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 15 页学习必备欢迎下载（四）将 for 语句和 if 语句翻译成相应的四元式序列1.if 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 15 页学习必备欢迎下载2.

10、for (五) 短语、素短语、最左素短语，FirstVT 集和 LastVT 集的求解方法(复习第四章算符优先文法相关内容)1. 短语、素短语、最左素短语精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 15 页学习必备欢迎下载2.FirstVT 集和 LastVT 集的求解方法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 15 页学习必备欢迎下载例：设文法为：E #E#；TF；EE+T ；FPF | P； ET ；P(E)；TT*F ；Pi；3. 算符优先文法优先关系的定义 :

11、 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 15 页学习必备欢迎下载算符优先文法的定义 : 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 15 页学习必备欢迎下载三、综合题1.NFA 的确定化和最小化(参看课件第三章62页：例 5) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 15 页学习必备欢迎下载2.自顶向下分析(参看课件第四章（ 1）67 页：综合练习 ) 精选学习资料 - - - - - - - -

12、 - 名师归纳总结 - - - - - - -第 12 页，共 15 页学习必备欢迎下载例：求对应于下述文法的预测分析表: E TE E +TE | T FT T *FT | F (E) |i 答：1）首先求 first 集: 2）由于 First(E), First(T), 求 E和 T的 Follow 集: 3）根据集合的值填表，得到: 例:设文法 G(S)：S(L) | aS | a LL，S | S (1) 消除左递归和回溯；(2) 计算每个非终结符的First 和 Follow 集；(3) 构造预测分析表。答：(1) 消除左递归和回溯：(2) (3)构造预测分析表：3.LR 分析方法

13、(参看课件第四章（ 3）28 页及 30 页) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 15 页学习必备欢迎下载(附) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 15 页学习必备欢迎下载1.短语、直接短语、句柄例：考虑如下文法：E =T | E+T T =F | T*F F =i | (E) 求句型i1 * i2 + i3 的短语、直接短语和句柄答：E = F * i2 + i3 E = i1 * F + i3 E = i1 * i2 + F E = T + i

14、3（T =T*F =i1 * i2 ）F=i E = i1 * i2 + i3 因此：短语有： i1, i2, i3, i1*i2, i1*i2+i3 直接短语有： i1, i2 , i3 句柄是：i1 i2 + i3 不是短语，因为 E = i1 * E （E =i2 +i3）2. 什么是语法制导翻译语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。语法制导翻译 (Syntax-Directed Translations) ： 一个句子的语义翻译过程与语法分析过程同时进行。在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息，语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 15 页