编译原理是计算机科学与技术、软件工程专业，以及计算机系统安全有关专业的核心基础课程，也是培养学生解决复杂软件问题能力的重要课程之一。本书系统地介绍了编译程序的基本原理、主要实现技术、基本设计方法和一些自动构造工具，深入浅出地介绍了完整的编译程序构造和实现过程，具体包括：编译引论、词法分析、语法分析、语义分析和符号表、运行时存储空间的组织与管理、中间代码生成、中间代码优化和目标代码生成。
本书可以作为普通高等教育本科院校计算机相关专业编译原理课程的教学教材，也可以作为学生学习编译原理相关知识的参考教材。
编译原理是计算机科学与技术、软件工程专业、以及计算机系统安全有关专业的核心基础课程。通过学习该课程，学生不仅可以掌握编译程序本身的实现技术，而且能够提高对程序设计语言的理解，提高开发大型软件的能力、软件程序的设计能力以及抽象思维能力。
编译程序是计算机系统软件的重要组成部分，其基本原理和实现技术也适用于一般软件的设计和实现，而且在软件工程、软件自动化、程序分析等领域有着广泛的应用。通常把编译程序视为高级语言到目标语言（通常是机器语言或汇编语言）的转换程序，这种转换不是结构上的变换，而是基于语言语义的等价变换，因此，编译程序设计的难度和复杂性是很高的。编译原理也是一门对实践性要求较高的课程。本书充分考虑了教师教学和学生自学的问题，系统地介绍了编译程序的基本原理、主要实现技术、基本设计方法和一些自动构造工具，深入浅出地介绍了完整的编译程序构造和实现过程，可作为普通高等教育本科院校计算机相关专业的专业课教材或选修课教材。
本书是在第2版的基础上修订而来的，对第2版教材内容的结构进行了调整，将形式语言与自动机部分的知识穿插在了编译过程中，将运行时空间管理相关的内容调整到了中间代码生成之前，同时对书中抽象难懂的知识点补充了详细的解释和实例，并改变了原书中一些知识点的讲述思路，使得知识点更贴近编译过程中的实际问题。同时，本书还新增了微课视频，读者可扫描书中二维码进行观看和学习。
本书是根据作者多年的教学经验和科研经历编写而成的，由刘磊确定内容的选取和组织，最终定稿。其中，张鹏编写第1、4、5章，刘宇舟编写第2、3章，刘华虓编写第6章，申春编写第7、8、9章。
由于编者水平有限，书中难免还存在一些缺点和不妥之处，殷切希望广大读者批评指正。
编 者
刘磊，吉林大学计算机科学与软件学院教授，博士生导师。现任吉林大学第一届教学委员会委员、吉林大学信息科学学部教学委员会副主任委员、吉林大学信息科学学部学术委员会副主任委员、吉林大学计算机科学与技术学院学术委员会主任委员，同时兼任吉林省高等学校软件新技术重点实验室（吉林大学）主任、吉林大学-德蒙福特大学软件工程联合研究中心主任。现为吉林大学“985工程”项目“软件与网络新技术及生物计算科技创新平台”专家委员会主任。曾获得吉林省有突出贡献的中青年专业技术人才、吉林省教学名师、宝钢优秀教师、东北师范大学“东师学者”教学名师、长春市师德标兵等荣誉称号。
前言
第1章 编译引论 1
1.1 程序设计语言和编译程序 1
1.2 编译程序的结构 2
1.2.1 编译程序的构成 2
1.2.2 遍 5
1.2.3 编译程序的前端和后端 5
1.3 编译程序和程序设计环境 5
1.4 编译程序的实现 6
习题 7
第2章 词法分析 8
2.1 词法分析介绍 8
2.1.1 词法分析程序的功能 8
2.1.2 单词分类 8
2.1.3 词法分析程序的接口 9
2.2 字符串与正则表达式 10
2.2.1 符号串与符号串集合 10
2.2.2 正则表达式与正则集 13
2.3 有限自动机（FA） 15
2.3.1 确定有限自动机 15
2.3.2 非确定有限自动机 18
2.3.3 自动机的实现 20
2.3.4 NFA的确定化 22
2.3.5 DFA的化简 24
2.4 正则表达式与有限自动机 26
2.5 词法分析程序设计 30
2.5.1 过程概述 30
2.5.2 单词的形式描述 30
2.5.3 单词的内部表示 32
2.6 词法分析程序的实现 33
2.6.1 实现词法分析程序应注意的问题 33
2.6.2 单词结构 35
2.6.3 实现算法 35
2.7 词法分析程序自动生成 37
2.7.1 LEX简介 37
2.7.2 LEX工作原理 37
2.7.3 LEX源文件结构 38
2.7.4 LEX系统中的正则式 40
2.7.5 LEX的使用方式 42
2.7.6 应用实例 43
习题 43
第3章 语法分析自顶向下分析方法 44
3.1 文法 44
3.1.1 文法的定义 44
3.1.2 文法的分类 45
3.1.3 推导和归约 48
3.1.4 语法树与文法二义性 49
3.1.5 文法等价变换 53
3.2 语法分析程序介绍 58
3.2.1 语法分析程序的功能 58
3.2.2 语法错误类别及错误处理 58
3.2.3 自顶向下语法分析基本思想 60
3.2.4 三个重要的集合 61
3.2.5 自顶向下语法分析条件 64
3.3 递归下降法 65
3.3.1 递归下降法语法分析原理 65
3.3.2 递归下降法语法分析程序的构造 67
3.4 LL(1)分析方法 68
3.4.1 LL(1)分析法原理 68
3.4.2 LL(1)分析表的构造 69
3.4.3 LL(1)驱动程序构造 71
3.5 自顶向下分析程序的自动生成 72
习题 73
第4章 语法分析自底向上分析方法 75
4.1 自底向上语法分析方法介绍 75
4.2 简单优先分析法 76
4.2.1 简单优先文法及其优先关系矩阵的构造 77
4.2.2 简单优先分析算法 79
4.3 LR分析法 79
4.3.1 LR(0)归约规范活前缀状态机 80
4.3.2 LR(0)分析方法 85
4.3.3 SLR(1)分析方法 90
4.3.4 LR(1)分析方法 93
4.3.5 LALR(1)分析方法 96
4.3.6 LR方法小结 98
4.4 自底向上分析程序的自动生成 101
习题 101
第5章 语义分析和符号表 104
5.1 语义分析概述 104
5.1.1 什么是语义 104
5.1.2 语义分析的功能 105
5.1.3 语义分析的一般过程 107
5.1.4 语法制导方法 109
5.2 符号表的数据结构 112
5.2.1 标识符的属性 113
5.2.2 标识符的内部表示 114
5.2.3 类型的内部表示 121
5.2.4 值的内部表示 125
5.3 符号表的管理 125
5.3.1 符号表的建立与访问 125
5.3.2 符号表的组织 127
5.3.3 符号表的局部化处理 128
5.4 程序设计语言符号表的实例 132
5.4.1 Pascal语言的符号表 132
5.4.2 C语言的符号表 135
习题 139
第6章 运行时存储空间的组织与管理 141
6.1 目标程序运行时的存储结构 141
6.1.1 目标程序运行时内存的划分 141
6.1.2 目标程序运行时的存储分配策略 142
6.2 过程活动记录和运行时栈 145
6.2.1 过程活动记录 145
6.2.2 过程活动记录的申请和释放 146
6.3 变量访问环境 148
6.3.1 变量访问环境概述 148
6.3.2 Display表方法 149
6.3.3 静态链方法 153
习题 155
第7章 中间代码生成 156
7.1 常用的中间代码结构 156
7.1.1 后缀式 157
7.1.2 抽象语法树和有向无环图 158
7.1.3 三地址中间代码 159
7.2 类型检查和类型转换 162
7.3 中间代码生成中的几个问题 162
7.3.1 抽象地址ARG语义信息的获取和保存 162
7.3.2 语义栈Sem及其操作 163
7.3.3 常用的语义子程序 164
7.4 表达式的中间代码生成 165
7.5 下标变量的中间代码生成 167
7.5.1 下标变量的地址计算 167
7.5.2 下标变量的四元式结构 169
7.5.3 下标变量的中间代码生成 169
7.6 赋值语句的中间代码生成 172
7.7 控制语句的中间代码生成 173
7.7.1 goto语句和标号定位的中间代码 173
7.7.2 if条件语句的中间代码 174
7.7.3 while循环语句的中间代码 175
7.8 过程调用和函数调用的中间代码生成 176
7.9 过程声明和函数声明的中间代码生成 179
习题 182
第8章 中间代码优化 184
8.1 优化方法概述 184
8.1.1 优化目标和要求 184
8.1.2 优化内容 185
8.1.3 局部优化和全局优化 186
8.1.4 基本块划分 186
8.2 常量表达式优化 188
8.2.1 常量表达式的局部优化 189
8.2.2 基于常量定值分析的常量表达式全局优化 189
8.3 公共表达式优化 192
8.3.1 公共表达式的局部优化 192
8.3.2 基于活跃代码分析的公共表达式全局优化 193
8.4 循环不变式外提 198
8.4.1 循环不变式外提概述 198
8.4.2 循环不变式外提原理 201
8.5 临时变量的存储分配 205
8.5.1 临时变量特点 205
8.5.2 临时变量存储分配 205
8.6 其他各类优化介绍 206
习题 207
第9章 目标代码生成 210
9.1 目标代码生成介绍 210
9.1.1 代码生成器的输入和输出 210
9.1.2 指令选择 211
9.2 一个简单的虚拟目标机模型 212
9.3 四元式到目标代码的翻译 214
9.3.1 目标地址生成 214
9.3.2 表达式四元式的翻译 216
9.3.3 赋值语句四元式的翻译 216
9.3.4 输入输出语句四元式的翻译 217
9.3.5 条件语句四元式的翻译 218
9.3.6 循环语句四元式的翻译 219
9.3.7 标号语句和goto语句四元式的翻译 220
9.3.8 过程/函数声明和调用语句四元式的翻译 220
9.4 多寄存器的代码生成 225
9.4.1 寄存器分配准则 225
9.4.2 寄存器分配单位 226
9.4.3 变量活跃性分析 226
9.4.4 寄存器分配算法 228
习题 230
参考文献 232
书单推荐
