编译器设计（第2版）
Keith D. Cooper，莱斯大学计算机科学系计算工程专业Doerr特聘教授，曾任该系系主任。Cooper博士的研究课题涵盖过程间数据流分析、标量指令优化、寄存器分配以及指令调度等方面。
Linda Torczon，莱斯大学计算机科学系高级研究员。Torczon的研究内容主要包括代码生成、过程间数据流分析和优化、编程环境。
译者简介：
郭旭，资深软件设计师。主要兴趣是复杂软件系统的分析和设计，目前从事高性能数据集成工具的研发。译有《深入Linux内核架构》、《C语言接口及实现》等书。
Linda Torczon，莱斯大学计算机科学系高级研究员。Torczon的研究内容主要包括代码生成、过程间数据流分析和优化、编程环境。
译者简介：
郭旭，资深软件设计师。主要兴趣是复杂软件系统的分析和设计，目前从事高性能数据集成工具的研发。译有《深入Linux内核架构》、《C语言接口及实现》等书。
1952年一个编译器诞生，至今已经过去了半个多世纪，编译器的发展日臻成熟，关于编译器设计的著作也出版了不少，但既关注设计细节，又具备大局观的经典之作凤毛麟角，《编译器设计（第2版）》即是这样一本难得的佳作。
两位作者多年来一直奋战在研发和教学一线，理论和实践上的丰厚经验都凝结在了《编译器设计（第2版）》中。书中论述了一系列构建现代编译器必需的核心技术，分析了编译器设计者需要面对的诸多问题，阐释了解决这些问题所用到的一些知识点。第2版是时隔8年之后全新修订的版本，充分展现了编译器构造技术的进展。作者重写了书中全部示例，并特别改进了阐述顺序，使得章与章之间的内容更具连续性，也更适合专业人士将这本高校教材作为参考书。
两位作者多年来一直奋战在研发和教学一线，理论和实践上的丰厚经验都凝结在了《编译器设计（第2版）》中。书中论述了一系列构建现代编译器必需的核心技术，分析了编译器设计者需要面对的诸多问题，阐释了解决这些问题所用到的一些知识点。第2版是时隔8年之后全新修订的版本，充分展现了编译器构造技术的进展。作者重写了书中全部示例，并特别改进了阐述顺序，使得章与章之间的内容更具连续性，也更适合专业人士将这本高校教材作为参考书。
第1章 编译概观
1.1 简介
1.2 编译器结构
1.3 转换概述
1.3.1 前端
1.3.2 优化器
1.3.3 后端
1.4 小结和展望
第2章 词法分析器
2.1 简介
2.2 识别单词
2.2.1 识别器的形式化
2.2.2 识别更复杂的单词
2.3 正则表达式
2.3.1 符号表示法的形式化
2.3.2 示例
2.3.3 RE的闭包性质
2.4 从正则表达式到词法分析器
2.4.1 非确定性有限自动机
2.4.2 从正则表达式到NFA：Thompson构造法
2.4.3 从NFA到DFA：子集构造法
2.4.4 从DFA到最小DFA：Hopcroft算法
2.4.5 将DFA用做识别器
2.5 实现词法分析器
2.5.1 表驱动词法分析器
2.5.2 直接编码的词法分析器
2.5.3 手工编码的词法分析器
2.5.4 处理关键字
2.6 高级主题
2.6.1 从DFA到正则表达式
2.6.2 DFA最小化的另一种方法：Brzozowski算法
2.6.3 无闭包的正则表达式
2.7 小结和展望
第3章 语法分析器
3.1 简介
3.2 语法的表示
3.2.1 为什么不使用正则表达式
3.2.2 上下文无关语法
3.2.3 更复杂的例子
3.2.4 将语义编码到结构中
3.2.5 为输入符号串找到推导
3.3 自顶向下语法分析
3.3.1 为进行自顶向下语法分析而转换语法
3.3.2 自顶向下的递归下降语法分析器
3.3.3 表驱动的LL(1)语法分析器
3.4 自底向上语法分析
3.4.1 LR(1)语法分析算法
3.4.2 构建LR(1)表
3.4.3 表构造过程中的错误
3.5 实际问题
3.5.1 出错恢复
3.5.2 一元运算符
3.5.3 处理上下文相关的二义性
3.5.4 左递归与右递归
3.6 高级主题
3.6.1 优化语法
3.6.2 减小LR(1)表的规模
3.7 小结和展望
第4章 上下文相关分析
4.1 简介
4.2 类型系统简介
4.2.1 类型系统的目标
4.2.2 类型系统的组件
4.3 属性语法框架
4.3.1 求值的方法
4.3.2 环
4.3.3 扩展实例
4.3.4 属性语法方法的问题
4.4 特设语法制导转换
4.4.1 特设语法制导转换的实现
4.4.2 例子
4.5 高级主题
4.5.1 类型推断中更困难的问题
4.5.2 改变结合性
4.6 小结和展望
第5章 中间表示
5.1 简介
5.2 图IR
5.2.1 与语法相关的树
5.2.2 图
5.3 线性IR
5.3.1 堆栈机代码
5.3.2 三地址代码
5.3.3 线性代码的表示
5.3.4 根据线性代码建立控制流图
5.4 将值映射到名字
5.4.1 临时值的命名
5.4.2 静态单赋值形式
5.4.3 内存模型
5.5 符号表
5.5.1 散列表
5.5.2 建立符号表
5.5.3 处理嵌套的作用域
5.5.4 符号表的许多用途
5.5.5 符号表技术的其他用途
5.6 小结和展望
第6章 过程抽象
6.1 简介
6.2 过程调用
6.3 命名空间
6.3.1 类Algol语言的命名空间
6.3.2 用于支持类Algol语言的运行时结构
6.3.3 面向对象语言的命名空间
6.3.4 支持面向对象语言的运行时结构
6.4 过程之间值的传递
6.4.1 传递参数
6.4.2 返回值
6.4.3 确定可寻址性
6.5 标准化链接
6.6 高级主题
6.6.1 堆的显式管理
6.6.2 隐式释放
6.7 小结和展望
第7章 代码形式
7.1 简介
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.3.6 作为运算符的赋值操作
7.4 布尔运算符和关系运算符
7.4.1 表示
7.4.2 对关系操作的硬件支持
7.5 数组的存储和访问
7.5.1 引用向量元素
7.5.2 数组存储布局
7.5.3 引用数组元素
7.5.4 范围检查
7.6 字符串
7.6.1 字符串表示
7.6.2 字符串赋值
7.6.3 字符串连接
7.6.4 字符串长度
7.7 结构引用
7.7.1 理解结构布局
7.7.2 结构数组
7.7.3 联合和运行时标记
7.7.4 指针和匿名值
7.8 控制流结构
7.8.1 条件执行
7.8.2 循环和迭代
7.8.3 case语句
7.9 过程调用
7.9.1 实参求值
7.9.2 保存和恢复寄存器
7.10 小结和展望
第8章 优化简介
8.1 简介
8.2 背景
8.2.1 例子
8.2.2 对优化的考虑
8.2.3 优化的时机
8.3 优化的范围
8.4 局部优化
8.4.1 局部值编号
8.4.2 树高平衡
8.5 区域优化
8.5.1 超局部值编号
8.5.2 循环展开
8.6 全局优化
8.6.1 利用活动信息查找未初始化变量
8.6.2 全局代码置放
8.7 过程间优化
8.7.1 内联替换
8.7.2 过程置放
8.7.3 针对过程间优化的编译器组织结构
8.8 小结和展望
第9章 数据流分析
9.1 简介
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.3.5 从静态单赋值形式到其他形式的转换
9.3.6 使用静态单赋值形式
9.4 过程间分析
9.4.1 构建调用图
9.4.2 过程间常量传播
9.5 高级主题
9.5.1 结构性数据流算法和可归约性
9.5.2 加速计算支配性的迭代框架算法的执行
9.6 小结和展望
第10章 标量优化
10.1 简介
10.2 消除无用和不可达代码
10.2.1 消除无用代码
10.2.2 消除无用控制流
10.2.3 消除不可达代码
10.3 代码移动
10.3.1 缓式代码移动
10.3.2 代码提升
10.4 特化
10.4.1 尾调用优化
10.4.2 叶调用优化
10.4.3 参数提升
10.5 冗余消除
10.5.1 值相同与名字相同
10.5.2 基于支配者的值编号算法
10.6 为其他变换制造时机
10.6.1 超级块复制
10.6.2 过程复制
10.6.3 循环外提
10.6.4 重命名
10.7 高级主题
10.7.1 合并优化
10.7.2 强度削减
10.7.3 选择一种优化序列
10.8 小结和展望
第11章 指令选择
11.1 简介
11.2 代码生成
11.3 扩展简单的树遍历方案
11.4 通过树模式匹配进行指令选择
11.4.1 重写规则
11.4.2 找到平铺方案
11.4.3 工具
11.5 通过窥孔优化进行指令选择
11.5.1 窥孔优化
11.5.2 窥孔变换程序
11.6 高级主题
11.6.1 学习窥孔模式
11.6.2 生成指令序列
11.7 小结和展望
第12章 指令调度
12.1 简介
12.2 指令调度问题
12.2.1 度量调度质量的其他方式
12.2.2 是什么使调度这样难
12.3 局部表调度
12.3.1 算法
12.3.2 调度具有可变延迟的操作
12.3.3 扩展算法
12.3.4 在表调度算法中打破平局
12.3.5 前向表调度与后向表调度
12.3.6 提高表调度的效率
12.4 区域性调度
12.4.1 调度扩展基本程序块
12.4.2 跟踪调度
12.4.3 通过复制构建适当的上下文环境
12.5 高级主题
12.5.1 软件流水线的策略
12.5.2 用于实现软件流水线的算法
12.6 小结和展望
第13章 寄存器分配
13.1 简介
13.2 背景问题
13.2.1 内存与寄存器
13.2.2 分配与指派
13.2.3 寄存器类别
13.3 局部寄存器分配和指派
13.3.1 自顶向下的局部寄存器分配
13.3.2 自底向上的局部寄存器分配
13.3.3 超越单个程序块
13.4 全局寄存器分配和指派
13.4.1 找到全局活动范围
13.4.2 估算全局逐出代价
13.4.3 冲突和冲突图
13.4.4 自顶向下着色
13.4.5 自底向上着色
13.4.6 合并副本以减小度数
13.4.7 比较自顶向下和自底向上全局分配器
13.4.8 将机器的约束条件编码到冲突图中
13.5 高级主题
13.5.1 图着色寄存器分配方法的变体
13.5.2 静态单赋值形式上的全局寄存器分配
13.6 小结和展望
附录A ILOC
附录B 数据结构
参考文献
索引
^ 收 起
1.1 简介
1.2 编译器结构
1.3 转换概述
1.3.1 前端
1.3.2 优化器
1.3.3 后端
1.4 小结和展望
第2章 词法分析器
2.1 简介
2.2 识别单词
2.2.1 识别器的形式化
2.2.2 识别更复杂的单词
2.3 正则表达式
2.3.1 符号表示法的形式化
2.3.2 示例
2.3.3 RE的闭包性质
2.4 从正则表达式到词法分析器
2.4.1 非确定性有限自动机
2.4.2 从正则表达式到NFA：Thompson构造法
2.4.3 从NFA到DFA：子集构造法
2.4.4 从DFA到最小DFA：Hopcroft算法
2.4.5 将DFA用做识别器
2.5 实现词法分析器
2.5.1 表驱动词法分析器
2.5.2 直接编码的词法分析器
2.5.3 手工编码的词法分析器
2.5.4 处理关键字
2.6 高级主题
2.6.1 从DFA到正则表达式
2.6.2 DFA最小化的另一种方法：Brzozowski算法
2.6.3 无闭包的正则表达式
2.7 小结和展望
第3章 语法分析器
3.1 简介
3.2 语法的表示
3.2.1 为什么不使用正则表达式
3.2.2 上下文无关语法
3.2.3 更复杂的例子
3.2.4 将语义编码到结构中
3.2.5 为输入符号串找到推导
3.3 自顶向下语法分析
3.3.1 为进行自顶向下语法分析而转换语法
3.3.2 自顶向下的递归下降语法分析器
3.3.3 表驱动的LL(1)语法分析器
3.4 自底向上语法分析
3.4.1 LR(1)语法分析算法
3.4.2 构建LR(1)表
3.4.3 表构造过程中的错误
3.5 实际问题
3.5.1 出错恢复
3.5.2 一元运算符
3.5.3 处理上下文相关的二义性
3.5.4 左递归与右递归
3.6 高级主题
3.6.1 优化语法
3.6.2 减小LR(1)表的规模
3.7 小结和展望
第4章 上下文相关分析
4.1 简介
4.2 类型系统简介
4.2.1 类型系统的目标
4.2.2 类型系统的组件
4.3 属性语法框架
4.3.1 求值的方法
4.3.2 环
4.3.3 扩展实例
4.3.4 属性语法方法的问题
4.4 特设语法制导转换
4.4.1 特设语法制导转换的实现
4.4.2 例子
4.5 高级主题
4.5.1 类型推断中更困难的问题
4.5.2 改变结合性
4.6 小结和展望
第5章 中间表示
5.1 简介
5.2 图IR
5.2.1 与语法相关的树
5.2.2 图
5.3 线性IR
5.3.1 堆栈机代码
5.3.2 三地址代码
5.3.3 线性代码的表示
5.3.4 根据线性代码建立控制流图
5.4 将值映射到名字
5.4.1 临时值的命名
5.4.2 静态单赋值形式
5.4.3 内存模型
5.5 符号表
5.5.1 散列表
5.5.2 建立符号表
5.5.3 处理嵌套的作用域
5.5.4 符号表的许多用途
5.5.5 符号表技术的其他用途
5.6 小结和展望
第6章 过程抽象
6.1 简介
6.2 过程调用
6.3 命名空间
6.3.1 类Algol语言的命名空间
6.3.2 用于支持类Algol语言的运行时结构
6.3.3 面向对象语言的命名空间
6.3.4 支持面向对象语言的运行时结构
6.4 过程之间值的传递
6.4.1 传递参数
6.4.2 返回值
6.4.3 确定可寻址性
6.5 标准化链接
6.6 高级主题
6.6.1 堆的显式管理
6.6.2 隐式释放
6.7 小结和展望
第7章 代码形式
7.1 简介
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.3.6 作为运算符的赋值操作
7.4 布尔运算符和关系运算符
7.4.1 表示
7.4.2 对关系操作的硬件支持
7.5 数组的存储和访问
7.5.1 引用向量元素
7.5.2 数组存储布局
7.5.3 引用数组元素
7.5.4 范围检查
7.6 字符串
7.6.1 字符串表示
7.6.2 字符串赋值
7.6.3 字符串连接
7.6.4 字符串长度
7.7 结构引用
7.7.1 理解结构布局
7.7.2 结构数组
7.7.3 联合和运行时标记
7.7.4 指针和匿名值
7.8 控制流结构
7.8.1 条件执行
7.8.2 循环和迭代
7.8.3 case语句
7.9 过程调用
7.9.1 实参求值
7.9.2 保存和恢复寄存器
7.10 小结和展望
第8章 优化简介
8.1 简介
8.2 背景
8.2.1 例子
8.2.2 对优化的考虑
8.2.3 优化的时机
8.3 优化的范围
8.4 局部优化
8.4.1 局部值编号
8.4.2 树高平衡
8.5 区域优化
8.5.1 超局部值编号
8.5.2 循环展开
8.6 全局优化
8.6.1 利用活动信息查找未初始化变量
8.6.2 全局代码置放
8.7 过程间优化
8.7.1 内联替换
8.7.2 过程置放
8.7.3 针对过程间优化的编译器组织结构
8.8 小结和展望
第9章 数据流分析
9.1 简介
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.3.5 从静态单赋值形式到其他形式的转换
9.3.6 使用静态单赋值形式
9.4 过程间分析
9.4.1 构建调用图
9.4.2 过程间常量传播
9.5 高级主题
9.5.1 结构性数据流算法和可归约性
9.5.2 加速计算支配性的迭代框架算法的执行
9.6 小结和展望
第10章 标量优化
10.1 简介
10.2 消除无用和不可达代码
10.2.1 消除无用代码
10.2.2 消除无用控制流
10.2.3 消除不可达代码
10.3 代码移动
10.3.1 缓式代码移动
10.3.2 代码提升
10.4 特化
10.4.1 尾调用优化
10.4.2 叶调用优化
10.4.3 参数提升
10.5 冗余消除
10.5.1 值相同与名字相同
10.5.2 基于支配者的值编号算法
10.6 为其他变换制造时机
10.6.1 超级块复制
10.6.2 过程复制
10.6.3 循环外提
10.6.4 重命名
10.7 高级主题
10.7.1 合并优化
10.7.2 强度削减
10.7.3 选择一种优化序列
10.8 小结和展望
第11章 指令选择
11.1 简介
11.2 代码生成
11.3 扩展简单的树遍历方案
11.4 通过树模式匹配进行指令选择
11.4.1 重写规则
11.4.2 找到平铺方案
11.4.3 工具
11.5 通过窥孔优化进行指令选择
11.5.1 窥孔优化
11.5.2 窥孔变换程序
11.6 高级主题
11.6.1 学习窥孔模式
11.6.2 生成指令序列
11.7 小结和展望
第12章 指令调度
12.1 简介
12.2 指令调度问题
12.2.1 度量调度质量的其他方式
12.2.2 是什么使调度这样难
12.3 局部表调度
12.3.1 算法
12.3.2 调度具有可变延迟的操作
12.3.3 扩展算法
12.3.4 在表调度算法中打破平局
12.3.5 前向表调度与后向表调度
12.3.6 提高表调度的效率
12.4 区域性调度
12.4.1 调度扩展基本程序块
12.4.2 跟踪调度
12.4.3 通过复制构建适当的上下文环境
12.5 高级主题
12.5.1 软件流水线的策略
12.5.2 用于实现软件流水线的算法
12.6 小结和展望
第13章 寄存器分配
13.1 简介
13.2 背景问题
13.2.1 内存与寄存器
13.2.2 分配与指派
13.2.3 寄存器类别
13.3 局部寄存器分配和指派
13.3.1 自顶向下的局部寄存器分配
13.3.2 自底向上的局部寄存器分配
13.3.3 超越单个程序块
13.4 全局寄存器分配和指派
13.4.1 找到全局活动范围
13.4.2 估算全局逐出代价
13.4.3 冲突和冲突图
13.4.4 自顶向下着色
13.4.5 自底向上着色
13.4.6 合并副本以减小度数
13.4.7 比较自顶向下和自底向上全局分配器
13.4.8 将机器的约束条件编码到冲突图中
13.5 高级主题
13.5.1 图着色寄存器分配方法的变体
13.5.2 静态单赋值形式上的全局寄存器分配
13.6 小结和展望
附录A ILOC
附录B 数据结构
参考文献
索引
^ 收 起
Keith D. Cooper，莱斯大学计算机科学系计算工程专业Doerr特聘教授，曾任该系系主任。Cooper博士的研究课题涵盖过程间数据流分析、标量指令优化、寄存器分配以及指令调度等方面。
Linda Torczon，莱斯大学计算机科学系高级研究员。Torczon的研究内容主要包括代码生成、过程间数据流分析和优化、编程环境。
译者简介：
郭旭，资深软件设计师。主要兴趣是复杂软件系统的分析和设计，目前从事高性能数据集成工具的研发。译有《深入Linux内核架构》、《C语言接口及实现》等书。
Linda Torczon，莱斯大学计算机科学系高级研究员。Torczon的研究内容主要包括代码生成、过程间数据流分析和优化、编程环境。
译者简介：
郭旭，资深软件设计师。主要兴趣是复杂软件系统的分析和设计，目前从事高性能数据集成工具的研发。译有《深入Linux内核架构》、《C语言接口及实现》等书。
1952年一个编译器诞生，至今已经过去了半个多世纪，编译器的发展日臻成熟，关于编译器设计的著作也出版了不少，但既关注设计细节，又具备大局观的经典之作凤毛麟角，《编译器设计（第2版）》即是这样一本难得的佳作。
两位作者多年来一直奋战在研发和教学一线，理论和实践上的丰厚经验都凝结在了《编译器设计（第2版）》中。书中论述了一系列构建现代编译器必需的核心技术，分析了编译器设计者需要面对的诸多问题，阐释了解决这些问题所用到的一些知识点。第2版是时隔8年之后全新修订的版本，充分展现了编译器构造技术的进展。作者重写了书中全部示例，并特别改进了阐述顺序，使得章与章之间的内容更具连续性，也更适合专业人士将这本高校教材作为参考书。
两位作者多年来一直奋战在研发和教学一线，理论和实践上的丰厚经验都凝结在了《编译器设计（第2版）》中。书中论述了一系列构建现代编译器必需的核心技术，分析了编译器设计者需要面对的诸多问题，阐释了解决这些问题所用到的一些知识点。第2版是时隔8年之后全新修订的版本，充分展现了编译器构造技术的进展。作者重写了书中全部示例，并特别改进了阐述顺序，使得章与章之间的内容更具连续性，也更适合专业人士将这本高校教材作为参考书。
比价列表
缺书网
扫码进群