本书源于笔者多年来对编译器的学习和教学经验，并以在该学科领域与学生的交流以及他们的反馈和研究作为依据。

本书全面介绍了编译器设计中的原理和技术，阐述了编译领域中的难点，并详细描述了编译器设计的各个阶段。

　　本书主要用于计算机科学专业的本科生和研究生一个学期的教材，该书也可供专业人员作为参考书。

本书是作者多年来在编译器领域中钻研、教学的成果，并以在该学科领域与学生的交流以及他们的反馈和研究作为依据。本书全面介绍了编译器设计中的原理和技术，阐述了编译领域中的难点，并详细描述了编译器设计的各个阶段。　　因为编译器的设计过程是将自动机理论、数据结构、算法、计算机体系结构和操作系统等领域知识进行综合的过程，所以编译器设计者必须要有较好的计算机科学理论的背景。本书详细描述了各种类型的解析器，从最简单的递归下降和LL解析器到复杂的LR、规范LR和LALR解析器，尤其强调了LR解析器。　　本书主要用于计算机科学专业的本科生和研究生一个学期的教材，该书也可供专业人员作为参考书。

第1章 引言 1

 1.1 编译器的定义 1

 1.2 编译器应用 2

 1.3 编译器的各个阶段 3

 1.4 编译器设计的难点 7

 1.5 编译过程—— 示例 9

 1.6 小结 11

 练习 11

第2章 词法分析 13

 2.1 词法分析器的任务 13

 2.2 记号的规范 14

 2.3 记号识别 15

2.3.1 不确定的有限自动机 17

2.3.2 确定的有限自动机 17

2.3.3 NFA到DFA的转换 20

 2.4 NFA的正则表达式 22

 2.5 词法分析的工具—— Lex 25

 2.6 小结 33

 练习 33

第3章 语法分析 35

 3.1 解析器的功能 35

 3.2 错误处理 36

 3.3 文法 37

3.3.1 符号约定 38

3.3.2 推导 39

3.3.3 二义性 40

3.3.4 左递归 42

 3.4 自上而下的分析 43

3.4.1 递归下降分析 43

3.4.2 递归的预测分析 46

3.4.3 非递归的预测分析—— LL(k)分析 49

 3.5 自下而上的分析 53

3.5.1 算符优先的分析 56

3.5.2 建立优先关系 57

3.5.3 错误恢复 60

 3.6 LR分析 60

3.6.1 LR分析方法 60

3.6.2 LR分析算法 61

3.6.3 构造LR分析表 62

3.6.4 处理LR分析的二义性 74

3.6.5 LR分析中的错误恢复 77

 3.7 LALR解析器的生成器

—— yacc 78

 3.8 语法制导翻译 81

 3.9 小结 82

 练习 82

第4章 类型检查 85

 4.1 静态和动态检查的比较 85

 4.2 类型表达式 86

 4.3 类型检查 87

 4.4 类型等价 88

 4.5 类型转换 91

 4.6 小结 91

 练习 91

第5章 符号表 93

 5.1 符号表中的信息 93

 5.2 符号表的功能 94

 5.3 简单的符号表 95

5.3.1 线性表 95

5.3.2 有序列表 96

5.3.3 树 97

5.3.4 哈希表 97

 5.4 作用域的符号表 98

5.4.1 嵌套的词法作用域 99

5.4.2 每个作用域对应一张表 100

5.4.3 所有作用域都在一张表中 101

 5.5 小结 102

 练习 103

第6章 运行时环境管理 105

 6.1 引言 105

 6.2 活动记录 106

6.2.1 不含局部过程的环境 107

6.2.2 含有局部过程的环境 109

 6.3 display 112

 6.4 小结 113

 练习 113

第7章 中间代码生成 115

 7.1 中间语言 115

 7.2 中间语言设计问题 116

 7.3 中间表示技术 116

7.3.1 高级表示 116

7.3.2 低级表示 118

 7.4 三地址代码中的语句 118

 7.5 三地址指令的实现 120

 7.6 三地址代码生成 121

7.6.1 数组的代码生成 123

7.6.2 布尔表达式的翻译 126

7.6.3 控制流(程)语句的翻译 132

7.6.4 case语句的翻译 136

7.6.5 函数调用 137

 7.7 小结 139

 练习 139

第8章 目标代码生成 141

 8.1 影响代码生成的因素 141

 8.2 基本块 142

 8.3 树的代码生成 145

 8.4 寄存器分配 148

 8.5 缓存管理 154

 8.6 使用动态规划的代码生成 154

 8.7 小结 157

 练习 157

第9章 代码优化 159

 9.1 优化的需求 159

 9.2 优化编译器设计问题 160

 9.3 优化的分类 161

 9.4 影响优化的因素 162

 9.5 优化技术背后的主题 163

 9.6 优化变换 164

9.6.1 编译时计算 164

9.6.2 公共子表达式消除 166

9.6.3 变量传播 167

9.6.4 代码迁移优化 167

9.6.5 强度折减 170

9.6.6 无效代码消除 171

9.6.7 循环优化 172

 9.7 局部优化 175

 9.8 全局优化 177

9.8.1 控制流分析 177

9.8.2 数据流分析 178

9.8.3 获取数据流信息 182

 9.9 计算全局数据流信息 183

9.9.1 汇合路径 183

9.9.2 数据流等式 185

 9.10 建立数据流等式 187

9.10.1 数据流分析 188

9.10.2 数据流等式的保守解 189

 9.11 迭代数据流分析 190

9.11.1 可用表达式 191

9.11.2 有效范围识别 192

9.11.3 降低迭代数据流分析的复杂性 192

 9.12 小结 194

 练习 194