编译原理 (2008 年度畅销榜NO.2591 )

本书介绍编译器构造的一般原理和基本实现方法，主要内容包括词法分析：语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。除了介绍命令式编程语言的编译技术外，本书还介绍面向对象语言和函数式编程语言的实现技术。本书还强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统等。
本书取材广泛新颖、图文并茂，注意理论联系实际。本书可作为高等学校计算机科学及相关专业的教材，也可供计算机软件工程技术人员参考使用。

第1章 编译器概述
1.1 词法分析
1.2 语法分析
1.3 语义分析
1.4 中间代码生成
1.5 代码优化
1.6 代码生成
1.7 符号表管理
1.8 错误诊断和报告
1.9 阶段的分组
习题1

第2章 词法分析
2.1 词法记号及属性
2.1.1 词法记号、模式、词法单元
2.1.2 词法记号的属性
2.1.3 词法错误
2.2 词法记号的描述与识别
2.2.1 串和语言
2.2.2 正规式
2.2.3 正规定义
2.2.4 状态转换图
2.3 有限自动机
2.3.1 不确定的有限自动机
2.3.2 确定的有限自动机
2.3.3 NFA到DFA的变换
2.3.4 DFA的化简
2.4 从正规式到有限自动机
2.5 词法分析器的生成器
习题2

第3章 语法分析
3.1 下文无关文法
3.1.1 上下文无关文法的定义
3.1.2 推导
3.1.3 分析树
3.1.4 二义性
3.2 语言和文法
3.2.1 规式和上下文无关文法的比较
3.2.2 分离词法分析器的理由
3.2.3 验证文法产生的语言
3.2.4 适当的表达式文法
3.2.5 消除二义性
3.2.6 消除左递归
3.2.7 提左因子
3.2.8 非上下文无关的语言结构
3.2.9 形式语言鸟瞰
3.3 自上而下分析
3.3.1 自上而下分析的一般方法
3.3.2 LL(1)文法
3.3.3 递归下降的预测分析
3.3.4 非递归的预测分析
3.3.5 构造预测分析表
3.3.6 预测分析的错误恢复
3.4 自下而上分析
3.4.1 归约
3.4.2 句柄
3.4.3 用栈实现移进一归约分析
3.4.4 移进一归约分析的冲突
3.5 LR分析器
3.5.1 LR分析算法
3.5.2 LR文法和LR分析方法的特点
3，5.3 构造SLR分析表
3.5.4 构造规范的LR分析表
3.5.5 构造LALR分析表
3.5.6 非LR的上下文无关结构
3.6 二义文法的应用
3.6.1 使用文法以外的信息来解决分析动作的冲突
3.6.2 特殊情况产生式引起的二义性
3.6.3 LR分析的错误恢复
3.7 分析器的生成器
3.7.1 分析器的生成器Yacc
3.7.2 用Yacc处理二义文法
3.7.3 Yacc的错误恢复
习题3

第4章 语法制导的翻译
4.1 语法制导的定义
4.1.1 语法制导定义的形式
4.1.2 综合属性
4.1.3 继承属性
4.1.4 属性依赖图
4.1.5 属性计算次序
4.2 S属性定义的自下而上计算
4.2.1 语法树
4.2.2 构造语法树的语法制导定义
4.2.3 S属性的自下而上计算
4.3 L属性定义的自上而下计算
4.3.1 L属性定义
4.3.2 翻译方案
4.3.3 预测翻泽器的设计
4.3.4 用综合属性代替继承属性
4.4 L属性的自下而上计算
4.4.1 删除翻译方案中嵌入的动作
4.4.2 分析栈上的继承属性
4.4.3 模拟继承属性的计算
4.5 递归计算
4.5.1 自左向右遍历
4.5.2 其他遍历方法
4.5.3 多次遍历
习题4

第5章 类型检查
5.1 类型在程序设计语言中的作用
5.1.1 引言
5.1.2 执行错误和安全语言
5.1.3 类型化语言的优点
5.2 描述类型系统的语言
5.2.1 定型断言
5.2.2 定型规则
5.2.3 类型检查和类型推断
5.3 简单类型检查器的说明
5.3.1 一个简单的语言
5.3.2 类型系统
5.3.3 类型检查
5.3.4 类型转换
5.4 多态函数
5.4.1 为什么要使用多态函数
5.4.2 类型变量
5.4.3 一个含多态函数的语言
5.4.4 代换、实例和合一
5.4.5 多态函数的类型检查
5.5 类型表达式的等价
5，5.1 类型表达式的结构等价
5.5.2 类型表达式的名字等价
5.5.3 记录类型
5.5.4 类型表示中的环
5.6 函数和算符的重载
5.6.1 子表达式的可能类型集合
5.6.2 缩小可能类型的集合
习题5

第6章 运行时存储空间的组织和管理
6.1 局部存储分配策略
6.1.1 过程
6.1.2 名字的作用域和绑定
6.1.3 活动记录
6.1.4 局部数据的安排
6.1.5 程序块
6.2 全局存储分配策略
6.2.1 运行时内存的划分
6.2.2 静态分配
6.2.3 栈式分配
6.2.4 堆式分配
6.3 非局部名字的访问
6.3.1 无过程嵌套的静态作用域
6.3.2 有过程嵌套的静态作用域
6.3.3 动态作用域
6.4 参数传递
6.4.1 值调用
6.4.2 引用调用
6.4.3 复写—恢复调用
6.4.4 换名调用
习题6

第7章 中间代码生成
7.1 中间语言
7.1.1 后缀表示
7.1.2 图形表示
7.1.3 三地址代码
7.2 声明语句
7.2.1 过程中的声明
7.2.2 作用域信息的保存
7.2.3 记录的域名
7.3 赋值语句
7.3.1 符号表中的名字
7.3.2 临时名字的重新使用
7.3.3 数组元素的地址计算
7.3.4 数组元素地址计算的翻译方案
7.3.5 类型转换
7.4 布尔表达式和控制流语句
7.4.1 布尔表达式的翻译
7.4.2 控制流语句的翻译
7.4.3 布尔表达式的控制流翻译
7.4.4 开关语句的翻译
7.4.5 过程调用的翻译
习题7

第8章 代秒生成
8.1 代码生成器设计中的问题
8.1.1 目标程序
8.1.2 指令选择
8.1.3 寄存器分配
8.1.4 计算次序选择
8.2 目标机器
8.2.1 目标机器的指令系统
8.2.2 指令的代价
8.3 基本块和流图
8.3.1 基本块
8.3.2 基本块的变换
8.3.3 流图
8：3.4 下次引用信息
8.4 一个简单的代码生成器
8.4.1 寄存器描述和地址描述
8.4.2 代码生成算法
8.4.3 寄存器选择函数
8.4.4 为变址和指针语句产生代码
8.4.5 条件语句
习题8
*第9章 代码优化
9.1 优化的主要种类
9.1.1 代码改进变换的标准
9.1.2 公共子表达式删除
9.1.3 复写传播
9.1.4 死代码删除
9.1.5 代码外提
9.1.6 强度削弱和归纳变量删除
9.1.7 优化编译器的组织
9.2 流图中的循环
9.2.1 必经结点
9.2.2 自然循环
9.2.3 前置结点
9。2.4 可归约流图
9.3 全局数据流分析介绍
9.3.1 点和路径
9.3.2 到达—定值
9。3.3 可用表达式
9.3.4 活跃变量分析
9.4 代码改进变换
9.4.1 公共子表达式删除
9.4.2 复写传播
9.4.3 寻找循环不变计算
9.4.4 代码外提
9.4.5 归纳变量删除
习题9

第10章 编译系统和运行系统
10.1 C语言的编译系统
10.1.1 预处理器
10.1.2 汇编器
10.1.3 连接器
10.1.4 目标文件的格式
10.1.5 符号解析
10.1.6 静态库
10.1.7 可执行目标文件及装入
10.1.8 动态连接
10.1.9 处理目标文件的一些工具
10.2 Java语言的运行系统
10.2.1 Java虚拟机语言简介
10.2.2 Java虚拟机
10.2.3 即时编译器
10.3 无用单元收集
10.3.1 标记和清扫
10.3.2 引用计数
10.3.3 拷贝收集
10.3.4 分代收集
10.3.5 渐增式收集
10.3.6 编译器与收集器之间的相互影响
习题10

*第11章 面向对象语言的编译
11.1 面向对象语言的概念
11.1.1 对象和对象类
11.1.2 继承
11.1.3 信息封装
11.2 方法的编译
11.3 继承的编译方案
11.3.1 单一继承的编译方案
11.3.2 重复继承的编译方案
习题11

*第12章 函数式语言的编译
12.1 函数式程序设计语言简介
12.1.1 语言构造
12.1.2 参数传递机制
12.1.3 变量的自由出现和约束出现
12.2 函数式语言的编译简介
12.2.1 几个受启发的例子
12.2.2 编译函数
12.2.3 环境与约束
12.3 抽象机的系统结构
12.3.1 抽象机的栈
12.3.2 抽象机的堆
12.3.3 名字的寻址
12.3.4 约束的建立
12.4 指令集和编译
12.4.1 表达式
12.4.2 变量的此用性出现
12.4.3 函数定义
12.4.4 函数应用
12.4.5 构造和计算闭包
14.4.6 letrec表达式和局部变量
习题12

参考文献

本书介绍编译器构造的一般原理、基本设计方法和主要实现技术，可作为高等学校计算机科学及相关专业的教材。 虽然只有少数人从事构造或维护程序设计语言编译器的工作，但是编译原理和技术对高校学生和计算机软件工程技术人员来说仍是重要的基础知识之一。本书能使读者对程序设计语言的设计和实现有深刻的理解，对和程序设计语言有关的理论有所了解，对宏观上把握程序设计语言来说，能起一个奠基的作用。本书的学习还有助于读者快速理解、定位和解决在程序调试与运行中出现的问题。 对软件工程来说，编译器是一个很好的实例(基本设计、模块划分、基于事件驱动的编程等)，本书所介绍的概念和技术能应用到一般的软件设计之中。 大多数程序员同时也是语言的设计者，虽然只是一些简单语言(如输入输出、脚本语言)的设计者，但学习本书仍有助于提高他们设计这些语言的水平。 编译技术在软件安全、程序理解和软件逆向工程等方面有着广泛的应用。 作为教材，本书有如下一些特点： (1)在介绍语言实现技术的同时，强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统等。它们是计算机专业理论知识的一个重要部分，在本书中结合应用来介绍这些知识，有助于学生较快领会和掌握。 (2)在介绍编译器各逻辑阶段的实现时，强调形式化描述技术，并以语法制导定义作为翻译的主要描述工具。 (3)强调对编译原理和技术的宏观理解及全局把握，而不把读者的注意力分散到一些枝节的算法上，如计算开始符号集合和后继符号集合的算法、回填技术等。 出于同样的目的，本书较详细地介绍了编译系统和运行系统。 (4)本书还介绍了面向对象语言和函数式语言的实现技术，有助于加深读者对语言实现技术的理解。书中带星号的章节，作为教学的可选部分。 (5)作为原理性教材，本书介绍基本的理论和方法，而不偏向于某种源语言或目标机器。 (6)我们鼓励读者用所学的知识去分析和解决实际问题，因此本书中有很多习题是从实际碰到的问题中抽象出来的。这些习题也能激发读者学习编译原理和技术的积极性。 (7)为了便于读者学习，本书配有习题解答(见参考文献8)。 本书的多数章节是参考了参考文献1和参考文献7编写的，部分习题取自参考文献8。在此向有关作者表示感谢。 本书第1章到第6章以及第12章主要由陈意云编写，第7章到第11章主要由张昱编写。作者的学生陈晖准备了10．2节的初稿，李筱青准备了10．3节的初稿，吴萍和项森也为第10章的编写做了很多技术工作。 中国科学院软件研究所研究员程虎先生审阅了全书，并提出了许多宝贵的意见，在此表示衷心的感谢。 由于作者水平有限，书中难免还存在一些缺点和错误，恳请广大读者批评指正。