编译原理要点整理

编译原理要点整理

//红色字体标注的是重点中的重点，大题的归宿 第一章 引论

1. 翻译器，编译器的定义 2. 编译器工作步骤和流程

3. 编译器前端后端的概念，理解为什么要有前端后端 4. “遍”的概念

第二章 词法分析

1. 词法分析器的定义

2. 词法分析器所要完成的任务 3. 记号，模式，词法单元概念区分

4. 串的运算（和，连接，指数，闭包，正闭包） 5. 正规定义

6. 转换图（注意开始状态和结束状态以及需要将指针回退的状态） 7. 不确定的有限自动机（NFA）定义 8. 确定的有限自动机（DFA）定义 9. 从正规式到NFA（明确通过正规式如何构造连接运算，和运算，闭包运算的NFA） 10. 此方法产生的NFA的性质 11. 从NFA到DFA（子集构造法） 12. DFA的化简（合并不可区别状态） 13. 从语言描述直接到DFA 14. 了解Lex

学完本章：能语言描述改写成正规定义，能将正规定义转化为语言描述，给出一个正规式，能转换成相应的NFA，DFA并化简。

第三章 语法分析

1. 上下文无关文法定义 2. 区分句子和句型

3. 最左推导 && 最右推导 4. 分析树 5. 文法二义性

6. 消除左递归 && 提左因子

7. 了解语言鸟瞰（0型文法：短语文法；1型文法：上下文有关文法；2型文法：

上下文无关文法；3型文法：正规式）

8. FIRST集合 && FOLLOW集合定义及计算方法 9. LL（1）文法定义

10. 了解自上而下的递归下降的预测分析

11. 自上而下非递归的预测分析（详细明确预测分析器接受某一输入串时的具体过

程，明确栈如何变化，输入输出如何变化） 12. 预测分析表的构造 13. 句柄的概念

14. 自下而上的分析方法：用栈实现移近-归约分析（详细明确预测分析器接受某一

输入串时的具体过程，明确栈如何变化，输入输出如何变化） 15. LR文法和LR分析算法

16. 构造SLR分析表（从文法构造识别活前缀的DFA（LR（0）项目集规范族），从

DFA构造SLR分析表）

17. 构造规范的LR分析表（从文法构造识别活前缀的DFA（LR（1）项目集规范族），

从DFA构造规范的LR分析表）

18. 构造LALR分析表（从文法构造识别活前缀的DFA（合并同心的LR（1）项目集），

从DFA构造规范的LR分析表）（合并同心项目集可能会引起归约-归约冲突，不会引起新的移进-归约冲突）

学完本章：能计算FIRST集合和FOLLOW集合；给定一个文法，能判断是否是LL(1)文法，并为其构造分析表；能构造LR(1)文法的三种预测分析表；明确移近归约分析中的每一个步骤，明确栈如何变化。

第四章 语法制导的翻译

1. 语法制导的定义

2. 综合属性（S属性定义）

3. 注释分析树（S属性定义可以自下而上的完成） 4. 继承属性 5. 语法树

6. S属性的自下而上计算（将LR分析器增加一个域来保存综合属性值）（一定要明

确每一步移近-归约时属性栈如何变化）

7. L属性定义（例：变量类型声明的语法制导定义）

8. 翻译方案（能根据文法以及需要计算的属性写出一个翻译方案） 9. L属性定义的自上而下的计算 10. L属性定义的自下而上的计算

学完本章：要能根据要求设计简单问题的语法制导定义和翻译方案。 例：为文法 S—> ( L ) | a L—> L , S | S

写一个语法制导定义，它输出括号的对数。

第五章 （不要求）

第六章 运行时存储空间的组织和管理

1. 过程定义、过程调用、形式参数、实在参数、活动的生存期 2. 名字的作用域和绑定

3. 活动记录（运行程序时存储区布局，活动记录的一般布局） 4. 局部数据的安排（内存对齐问题） 5. 局部存储分配策略

6. 全局存储分配策略（静态，栈式，堆式） 7. 运行栈 && 活动树 8. 访问链 && 控制链

9. 非局部名字的访问（静态作用域，动态作用域的区别）

10. 四种参数传递方式的区别（值调用，引用调用，复写-恢复调用，换名调用）

学完本章：能判断一个变量的作用域；熟悉静态分配与动态栈式分配的区别；明确非局部数据访问的实现方法；各种参数传递方式的区别；会处理内存对齐问题；会画活动树。

例：指出下面程序中各个变量对应的分配策略？ int a;

void p(int b){ int c;

int *d = malloc(sizeof(int)*b); }

void main(){p(3);}

第七章 中间代码生成

1. 中间语言（能将表达式转化为后缀表示，图形表示，三地址代码形式） 2. 区分图形表示中的语法树和有向无环图

学完本章：能将表达式转化为后缀表达式，语法树，有向无环图，三地址代码形式。 例：将表达式a := (b + c*d ) + c*d转化为后缀表达式，有向无环图，三地址代码形式

第八章 代码生成

1. 指令的代价

学完本章：会计算指令的代价 例：指令 代价 MOV R0，R1 1