编译原理PDF电子书下载

第1章 绪论 1

1.1 程序设计语言 1

1.2 编译程序 2

1.3 编译程序的工作过程 2

1.3.1 词法分析（lexical analyzer） 2

1.3.2 语法分析（syntax analyzer） 3

1.3.3 语义分析和中间代码生成（intermediate code generator） 4

1.3.4 代码优化（source code optimizer） 5

1.3.5 代码生成（target code generator） 5

1.4 编译程序的逻辑结构 6

1.5 编译程序的生成 6

1.5.1 编译程序的移植 7

1.5.2 编译程序的“自编译方式” 7

1.5.3 LEX和YACC 7

习题 7

第2章 文法和语言 8

2.1 语言的描述 8

2.1.1 字母表和符号串 8

2.1.2 符号串及其运算 8

2.2 文法的形式定义和文法的分类 11

2.2.1 文法的形式定义 13

2.2.2 直接推导和规范推导 14

2.2.3 句型、句子和句柄 15

2.2.4 语言的形式定义 16

2.2.5 Chomsky文法的分类 18

2.2.6 文法之间的关系 20

2.2.7 上下文无关文法 20

2.3 语法树与文法的二义性 22

2.3.1 语法树 22

2.3.2 文法的二义性 24

2.4 文法的限制和文法的变换 26

2.4.1 文法的限制 26

2.4.2 文法的等价变换 27

习题 28

第3章 词法分析与有穷自动机 29

3.1 词法分析的任务和方法 29

3.1.1 单词类型及二元式编码 29

3.1.2 词法分析的任务 30

3.1.3 词法分析程序的实现方法 30

3.2 正规式与正规集 31

3.3 有穷自动机 32

3.3.1 DFA的定义 33

3.3.2 DFA的表示 33

3.3.3 不确定的有穷自动机 34

3.4 正规文法、正规式、有穷自动机的等价转换 35

3.4.1 正规文法与正规式的相互转换 35

3.4.2 正规式与FA的相互转换 37

3.4.3 正规文法与FA的相互转换 40

3.4.4 NFA到DFA的转换 40

3.5 词法分析器的设计 42

3.5.1 词法分析器的数据流图 42

3.5.2 词法分析器的设计技术 44

习题 46

第4章 自顶向下分析 49

4.1 上下文无关文法与语法分析 49

4.1.1 上下文无关文法的定义 49

4.1.2 推导 50

4.2 带回溯的自顶向下分析 52

4.3 左递归的消除 53

4.3.1 消除直接左递归 53

4.3.2 消除间接左递归 54

4.4 不带回溯的自顶向下分析的基本原理 54

4.5 提取左因子和FIRST集 55

4.6 FOLLOW集和SELECT集 56

4.6.1 FOLLOW集 56

4.6.2 SELECT集 58

4.7 递归下降分析法与预测分析法 59

4.7.1 递归下降分析法 59

4.7.2 预测分析法 61

习题 64

第5章 自底向上分析 66

5.1 自底向上分析的分析思想 66

5.2 移进—归约分析 66

5.2.1 归约 66

5.2.2 句柄 67

5.2.3 用栈实现移进—归约分析 68

5.3 算符优先分析 69

5.3.1 算符优先分析法概述 69

5.3.2 算符优先文法 70

5.3.3 算符优先分矩阵 72

5.3.4 算符优先分析的算法 73

5.4 LR分析 75

5.4.1 LR分析器的工作原理和过程 75

5.4.2 LR控制程序算法设计 78

5.5 LR（0）分析与SLR（1）分析 79

5.5.1 LR（0）分析 79

5.5.2 SLR（1）分析 83

习题 85

第6章 语法制导翻译与中间代码的生成 87

6.1 语义分析 87

6.2 语法制导翻译 87

6.3 属性文法 88

6.3.1 综合属性 90

6.3.2 继承属性 90

6.3.3 属性依赖图 91

6.3.4 属性计算次序 92

6.3.5 S属性文法的自下而上计算 93

6.3.6 L属性文法的自上而下计算 97

6.3.7 L属性文法的自下而上计算 100

6.4 常见中间代码的形式 103

6.4.1 逆波兰表示 103

6.4.2 四元式和三元式 104

习题 107

第7章 运行时的存储分配 108

7.1 程序运行时的存储器组织的基本思想 108

7.1.1 数据区 109

7.1.2 静态数据分配方案 109

7.1.3 动态数据分配方案 110

7.2 活动记录 110

7.3 静态存储分配和动态存储分配 111

7.3.1 静态存储分配 111

7.3.2 动态存储分配 113

7.4 过程调用的实现 118

7.4.1 过程调用 119

7.4.2 过程返回 119

7.5 参数传递机制 124

7.5.1 值传递 124

7.5.2 引用传递 124

7.5.3 值结果传递 125

7.5.4 名字传递 126

习题 127

第8章 代码优化和代码生成 128

8.1 代码优化的概念 128

8.2 局部优化 130

8.2.1 常用的局部优化技术 130

8.2.2 基本块的DAG表示 132

8.2.3 使用DAG方法进行局部优化 133

8.3 控制流分析和循环优化 136

8.3.1 控制流分析与循环体的识别 137

8.3.2 以深度为主循环的查找 139

8.3.3 循环优化 141

8.4 数据流分析和全局优化 143

8.4.1 单路径数据流分析 143

8.4.2 全路径数据流分析 147

8.4.3 其他数据流分析实例 149

8.4.4 全局优化 150

8.5 代码生成 153

8.5.1 代码生成要考虑的主要问题 153

8.5.2 基本块的代码生成 155

8.5.3 基于树重写的代码生成 157

习题 160

附录A 实验任务 162

附录B 编译程序源代码 167

参考文献 187