《编译原理》是编译原理课程方面的经典教材,全面、深入地探讨了编译器设计方面的重要主题,包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术,并在相关章节中给出大量的实例。与上一版相比,本书进行了全面修订,涵盖了编译器开发方面最新进展。每章中都提供了大量的实例及参考文献。
本书基于该书第2版进行改编,内容更加精练和实用,体系更加符合国内教学情况,适合作为高等院校计算机及相关专业本科生的编译原理课程的教材,也是广大研究人员和技术人员的极佳参考读物。
从本书的1986版出版到现在， 编译器设计领域已经发生了很大的改变。随着程序设计语
言
的发展， 提出了新的编译问题。计算机体系结构提供了多种多样的资源， 而编译器设
计者必须能
够充分利用这些资源。最有意思的事情可能是， 古老的代码优化技术已经在编译器之外
找到了
新的应用。现在， 有些工具利用这些技术来寻找软件中的缺陷， 以及（最重要的是）
寻找现有代
码中的安全漏洞。而且， 很多“前端”技术———文法、 正则表达式、 语法分析器以
及语法制导翻译
器
等———仍 然被广泛应用。
因此， 本书先前的版本所体现的我们的价值观一直没有改变。我们知道， 只有很少的
读者将
会去构建甚至维护一个主流程序设计语言的编译器。但是， 和编译器相关的模型、 理
论和算法可
以被应用到软件设计和开发中出现的各种各样的问题上。因此， 我们会关注那些在设计
一个语
言处理器时常常会碰到的问题， 而不考虑具体的源语言和目标机器究竟是什么。
使用本书
下面是各章的概要介绍:
第1章给出一些关于学习动机的资料， 同时也将给出一些关于计算机体系结构和程序设
计语言原则的背景知识。
第2章会开发一个小型的编译器， 并介绍很多重要概念。这些概念将在后面的各章中深
入介绍。这个编译器本身将在附录中给出。
第3章将讨论词法分析、 正则表达式、 有穷状态自动机和词法分析器的生成器工具。这
些内容是各种文本处理的基础。
第4章将讨论主流的语法分析方法， 包括自顶向下方法（递归下降法、 LL技术）和自底
向
上方法（LR技术和它的变体）。
第5章将介绍语法制导定义和语法制导翻译的基本思想。
第6章将使用第5章中的理论， 并说明如何使用这些理论为一个典型的程序设计语言生
成中间代码。
第7章将讨论运行时刻环境， 特别是运行时刻栈的管理和垃圾回收机制。
第8章将主要讨论目标代码生成技术。该章会讨论基本块的构造， 从表达式和基本块生
成代码的方法， 以及寄存器分配技术。
第9章将介绍代码优化技术， 包括流图、 数据流分析框架以及求解这些框架的迭代算法
。
哥伦比亚大学、 哈佛大学、 斯坦福大学已经开设了讲授本书内容的课程。哥伦比亚大
学定期
开设一门关于程序设计语言和翻译器的课程， 使用了本书前8章的内容。该课程常年面
向高年级
本科生/一年级研究生讲授， 这门课程的亮点是一个长达一个学期的课程实践项目。在
该项目
中， 学生分成小组， 创建并实现一个他们自己设计的小型语言。学生创建的语言涉及
多个应用领
域， 包括量子计算、 音乐合成、 计算机图形学、 游戏、 矩阵运算和很多其他领域。
在构建他们自
己的编译器时， 学生们使用了很多种可以生成编译器组件的工具， 比如ANTLR、 Lex和
Yacc; 他
们还使用了第2章和第5章中讨论的语法制导翻译技术。
斯坦福大学开设了一门历时一个学季的入门课程， 大致涵盖了本书第1章到第8章的内容
，
同时还会简介本书第9章中全局代码优化的相关内容。
预备知识
学习本书的读者应该拥有一些“计算机科学的综合知识”， 至少学过两门程序设计课
程， 以
及数据结构和离散数学的课程。具备多种程序设计语言的知识对学习本书会有所帮助。
练习
本书包含内容广泛的练习， 几乎每一节都有一些练习。我们用感叹号来表示较难的练
习或
练习中的一部分。难度最大的练习有两个感叹号。
万维网上的支持
在本书的主页（http://dragonbook.stanford.edu）
上可以找到本书已知错误的勘误表以及一
些支持性资料。我们希望将我们讲授的每一门与编译器相关的课程的可用讲义（包括家
庭作
业、 答案和练习等）都提供出来。我们也计划公布由一些重要编译器的作者撰写的关于
这些编
译器的描述。
致谢
本书封面由Strange Tonic Productions的S.D.Ullman设计。
Jon Bentley针对本书的初稿中的多章内容与我们进行了广泛深入的讨论。我们收到了
来
自下列人员的有帮助的评价和勘误: Domenico Bianculli、 Peter Bosch、 Marcio B
uss、 Marc Eaddy、
读者可以从http://infolab.stanford.edu/
～
ullman/dragon/errata.html找到本书的勘误表， 并可以从http://infolab.
stanford.edu/
～
ullman/dragon.html处找到本书的一些支持资料。
Stephen Edwards、 Vibhav Garg、 Kim Hazelwood、 Gaurav Kc、 Wei Li、 Mike
Smith、 Art Stamness、 Krysˉ
ta Svore、 Olivier Tardieu和Jia Zeng。我们衷心感谢这些人的帮助。当然， 书中
还可能有错漏之
处， 希望得到指正和反馈。
另外， Monica希望能够向她在SUIF编译器团队的同事表示感谢， 感谢他们在18年的时
间里
给予她的支持和帮助， 他们是: Gerald Aigner、 Dzintars Avots、 Saman Amara
singhe、 Jennifer Anderˉ
son、 Michael Carbin、 Gerald Cheong、 Amer Diwan、 Robert French、 Anwar G
huloum、 Mary Hall、 John
Hennessy、 David Heine、 ShihˉWei Liao、 Amy Lim、 Benjamin Livshits、
Michael Martin、 Dror Maydan、
Todd Mowry、 Brian Murphy、 Jeffrey Oplinger、 Karen Pieper、 Martin Rina
rd、 Olatunji Ruwase、 Constanˉ
tine Sapuntzakis、 Patrick Sathyanathan、 Michael Smith、 Steven Tjiang、
ChauˉWen Tseng、 Christopher
Unkel、 John Whaley、 Robert W ilson、 Christopher W ilson和Michael Wolf。
A.V.A.， Chatham NJ
M.S.L.， Menlo Park CA
R.S.， Far H ills NJ
J.D.U.， Stanford CA
2006年6月
Alfred V. Aho; Monica S.Lam ; Ravi Sethi ; Jeffrey D. Ullman：暂无简介
赵建华; 郑滔; 戴新宇：暂无简介
构造编译器的原理和技术是计算机科学技术领域中一个非常重要的组成部分， 指导人
们构
造能够生成正确、 高效的代码的编译器。现在的绝大部分软件都是使用高级程序设计语
言编写
的， 需要使用编译器来得到可运行代码， 因此编译原理和技术对于构造正确、 可靠、
高效的软件
是非常重要的。经过了50年的研究发展， 编译技术已经使得人们可以为各种高级编程机
制生成
高效的代码， 使得人们可以使用更加抽象的语言来编写高效的软件。但硬件技术的进步
仍然对
编译技术提出了新的挑战。比如多核CPU的广泛应用要求更优秀的程序分析技术和并行编
译
器。因此， 编译原理和技术在将来仍然是一个重要的研究课题。
Aho.等人编写的《编译原理》是一本经典的教材。这本书不仅包含了编译器构造的基本
原理
和技术， 还包含了很多和编译相关的高级技术。对于专业技术人员来说， 这是一本很
全面的参考
书目。但是书中的很多内容超出了本科教学的要求， 不符合中国的本科教材的习惯。因
此， 出版
社委托我们对这本书进行改编， 主要的工作是删减一些不需要在本科教学过程中讲授的
内容。
保留下的内容包括词法分析、 语法分析、 语义分析、 中间代码生成， 以及运行时刻
环境、 优化和
代码生成方法的基本技术。
我们删去了原书的第十章、 第十一章和第十二章。这三章的内容是关于并行性和程序分
析
的高级议题， 一般不对本科生讲授。此外， 我们对原书第九章机器无关优化的内容进
行了删减，
保留了一些基本的数据流优化算法。我们还删减了一些高级的算法和技术， 包括运行
时刻环境
中的短停顿垃圾收集算法、 类型检查中的类型推导和合一算法， 高效构造DFA算法等。
另外， 我
们还删去了一些与实现细节有关的技术， 比如词法分析中缓冲区的管理、 语法分析中
LR分析表
的压缩技术等。删去了这些高级内容之后， 保留部分已经可以在一个学期的本科生课程
中讲完。
当然， 考虑到不同学校有不同的专业要求， 任课教师仍然可以考虑舍弃一些内容， 比
如第八章中
关于代码生成的高级议题。
编译原理是一门比较难学的课程。主要原因在于它包含了很多理论性的东西， 抽象程度
比
较高， 而且还包含了很多复杂的算法和用于编译器构造的抽象数学概念。我建议学生学
习的时
候可以先阅读本书的第二章。第二章的内容可以帮助大家了解编译器的基本构造和功能
， 然后
在学习后续各章节的时候加深理解。自己动手编写一个小型语言的编译器也是一个很好
的学习
方法。使用Yacc和Lex等工具之后， 编写一个这样的编译器并不需要很大的工作量， 却
可以有
效帮助大家深入理解各种编译技术。
对编译的基本原理和技术有所了解之后， 如果读者还希望进一步深入学习， 我建议大
家购买
完整版的《编译原理》来阅读。
译者
2009年4月
出版者的话
改编者序
前言
第1章 引论
1………………………………
1.1 语言处理器
1……………………………
1.2 一个编译器的结构
2……………………
1.2.1 词法分析
3…………………………
1.2.2 语法分析
4…………………………
1.2.3 语义分析
5…………………………
1.2.4 中间代码生成
5……………………
1.2.5 代码优化
5…………………………
1.2.6 代码生成
6…………………………
1.2.7 符号表管理
6………………………
1.2.8 将多个步骤组合成趟
6……………
1.2.9 编译器构造工具
7…………………
1.3 程序设计语言的发展历程
7……………
1.3.1 走向高级程序设计语言
7…………
1.3.2 对编译器的影响
8…………………
1.3.3 1.3节的练习
8……………………
1.4 构建一个编译器的相关科学
8…………
1.4.1 编译器设计和实现中的建模
9……
1.4.2 代码优化的科学
9…………………
1.5 编译技术的应用
10……………………
1.5.1 高级程序设计语言的实现
10………
1.5.2 针对计算机体系结构的优化
11……
1.5.3 新计算机体系结构的设计
12………
1.5.4 程序翻译
13………………………
1.5.5 软件生产率工具
14………………
1.6 程序设计语言基础
15…………………
1.6.1 静态和动态的区别
15………………
1.6.2 环境与状态
15……………………
1.6.3 静态作用域和块结构
17……………
1.6.4 显式访问控制
18…………………
1.6.5 动态作用域
19……………………
1.6.6 参数传递机制
20…………………
1.6.7 别名
21……………………………
1.6.8 1.6节的练习
22……………………
1.7 第1章总结
22…………………………
1.8 第1章参考文献
23……………………
第2章 一个简单的语法制导
翻译器
24……………………………
2.1 引言
24…………………………………
2.2 语法定义
25……………………………
2.2.1 文法定义
26………………………
2.2.2 推导
27……………………………
2.2.3 语法分析树
28……………………
2.2.4 二义性
29…………………………
2.2.5 运算符的结合性
29………………
2.2.6 运算符的优先级
30………………
2.2.7 2.2节的练习
31……………………
2.3 语法制导翻译
32………………………
2.3.1 后缀表示
33………………………
2.3.2 综合属性
33………………………
2.3.3 简单语法制导定义
35………………
2.3.4 树的遍历
35………………………
2.3.5 翻译方案
35………………………
2.3.6 2.3节的练习
37……………………
2.4 语法分析
37……………………………
2.4.1 自顶向下分析方法
38………………
2.4.2 预测分析法
39……………………
2.4.3 何时使用产生式
41………………
2.4.4 设计一个预测分析器
41……………
2.4.5 左递归
42…………………………
2.4.6 2.4节的练习
42……………………
2.5 简单表达式的翻译器
43…………………
2.5.1 抽象语法和具体语法
43……………
2.5.2 调整翻译方案
43…………………
2.5.3 非终结符号的过程
44………………
2.5.4 翻译器的简化
45…………………
2.5.5 完整的程序
46……………………
2.6 词法分析
47……………………………
2.6.1 剔除空白和注释
48………………
2.6.2 预读
48……………………………
2.6.3 常量
49……………………………
2.6.4 识别关键字和标识符
49……………
2.6.5 词法分析器
50……………………
2.6.6 2.6节的练习
53……………………
2.7 符号表
53………………………………
2.7.1 为每个作用域设置一个符号表
54……
2.7.2 符号表的使用
56…………………
2.8 生成中间代码
57………………………
2.8.1 两种中间表示形式
57………………
2.8.2 语法树的构造
58…………………
2.8.3 静态检查
61………………………
2.8.4 三地址码
62………………………
2.8.5 2.8节的练习
66……………………
2.9 第2章总结
66…………………………
第3章 词法分析
68…………………………
3.1 词法分析器的作用
68…………………
3.1.1 词法分析及语法分析
69……………
3.1.2 词法单元、 模式和词素
69…………
3.1.3 词法单元的属性
70………………
3.1.4 词法错误
71………………………
3.1.5 3.1节的练习
71……………………
3.2 词法单元的规约
71……………………
3.2.1 串和语言
72………………………
3.2.2 语言上的运算
72…………………
3.2.3 正则表达式
73……………………
3.2.4 正则定义
74………………………
3.2.5 正则表达式的扩展
75………………
3.2.6 3.2节的练习
76……………………
3.3 词法单元的识别
78……………………
3.3.1 状态转换图
79……………………
3.3.2 保留字和标识符的识别
80…………
3.3.3 完成我们的例子
81………………
3.3.4 基于状态转换图的词法分析器的
体系结构
82………………………
3.3.5 3.3节的练习
84……………………
3.4 词法分析器生成工具Lex
86……………
3.4.1 Lex的使用
86………………………
3.4.2 Lex程序的结构
87…………………
3.4.3 Lex中的冲突解决
89………………
3.4.4 向前看运算符
89…………………
3.4.5 3.4节的练习
90……………………
3.5 有穷自动机
91…………………………
3.5.1 不确定的有穷自动机
91……………
3.5.2 转换表
92…………………………
3.5.3 自动机中输入字符串的接受
92……
3.5.4 确定的有穷自动机
93………………
3.5.5 3.5节的练习
93……………………
3.6 从正则表达式到自动机
94………………
3.6.1 从NFA到DFA的转换
94…………
3.6.2 最小化一个DFA的状态数
96………
3.6.3 从正则表达式构造NFA
99………
3.6.4 字符串处理算法的效率
101………
3.6.5 3.6节的练习
103…………………
3.7 词法分析器生成工具的设计
103………
3.7.1 生成的词法分析器的结构
103………
3.7.2 词法分析器使用的DFA
105………
3.7.3 词法分析器的状态最小化
105……
3.7.4 实现向前看运算符
105……………
3.7.5 3.7节的练习
106…………………
3.8 第3章总结
107…………………………
3.9 第3章参考文献
108……………………
第4章 语法分析
110………………………
4.1 引论
110………………………………
4.1.1 语法分析器的作用
110……………
4.1.2 代表性的文法
111…………………
4.1.3 语法错误的处理
112………………
4.1.4 错误恢复策略
112…………………
4.2 上下文无关文法
113……………………
4.2.1 上下文无关文法的正式定义
114…
4.2.2 符号表示的约定
114………………
4.2.3 推导
115……………………………
4.2.4 语法分析树和推导
116……………
4.2.5 二义性
117…………………………
4.2.6 验证文法生成的语言
118…………
4.2.7 上下文无关文法和正则
表达式
119…………………………
4.2.8 4.2节的练习
119…………………
4.3 设计文法
121……………………………
4.3.1 词法分析和语法分析
121…………
4.3.2 消除二义性
122……………………
4.3.3 左递归的消除
123…………………
4.3.4 提取左公因子
124…………………
4.3.5 非上下文无关语言的构造
125……
4.3.6 4.3节的练习
126…………………
4.4 自顶向下的语法分析
126………………
4.4.1 递归下降的语法分析
128…………
4.4.2 FIRST和FOLLOW
129……………
4.4.3 LL（1）文法
130……………………
4.4.4 非递归的预测分析
133……………
4.4.5 预测分析中的错误恢复
134………
4.4.6 4.4节的练习
136…………………
4.5 自底向上的语法分析
137………………
4.5.1 归约
138……………………………
4.5.2 句柄剪枝
138………………………
4.5.3 移入-归约语法分析技术
139……
4.5.4 移入-归约语法分析中的
冲突
140……………………………
4.5.5 4.5节的练习
141…………………
4.6 LR语法分析技术介绍: 简单LR
技术
142………………………………
4.6.1 为什么使用LR语法分析器
142……
4.6.2 项和LR（0）自动机
143……………
4.6.3 LR语法分析算法
147………………
4.6.4 构造SLR语法分析表
150…………
4.6.5 可行前缀
152………………………
4.6.6 4.6节的练习
153…………………
4.7 更强大的LR语法分析器
154……………
4.7.1 规范LR（1）项
154…………………
4.7.2 构造LR（1）项集
155………………
4.7.3 规范LR（1）语法分析表
158………
4.7.4 构造LALR语法分析表
159………
4.7.5 高效构造LALR语法分析表
的方法
162…………………………
4.7.6 4.7节的练习
165…………………
4.8 使用二义性文法
165……………………
4.8.1 用优先级和结合性解决冲突
165……
4.8.2 “悬空ˉelse” 的二义性
167…………
4.8.3 LR语法分析中的错误恢复
168……
4.8.4 4.8节的练习
169…………………
4.9 语法分析器生成工具
170………………
4.9.1 语法分析器生成工具Yacc
170……
4.9.2 使用带有二义性文法的Yacc
规约
173……………………………
4.9.3 用Lex创建Yacc的词法
分析器
175…………………………
4.9.4 Yacc中的错误恢复
175……………
4.9.5 4.9节的练习
176…………………
4.10 第4章总结
177………………………
4.11 第4章参考文献
178…………………
第5章 语法制导的翻译
182………………
5.1 语法制导定义
182………………………
5.1.1 继承属性和综合属性
183…………
5.1.2 在语法分析树的结点上对
SDD求值
184………………………
5.1.3 5.1节的练习
186…………………
5.2 SDD的求值顺序
186……………………
5.2.1 依赖图
186…………………………
5.2.2 属性求值的顺序
187………………
5.2.3 S属性的定义
188…………………
5.2.4 L属性的定义
188…………………
5.2.5 具有受控副作用的语义规则
189……
5.2.6 5.2节的练习
190…………………
5.3 语法制导翻译的应用
191………………
5.3.1 抽象语法树的构造
191……………
5.3.2 类型的结构
194……………………
5.3.3 5.3节的练习
195…………………
5.4 语法制导的翻译方案
195………………
5.4.1 后缀翻译方案
195…………………
5.4.2 后缀SDT的语法分析栈实现
196…
5.4.3 产生式内部带有语义动作
的SDT
197………………………
5.4.4 从SDT中消除左递归
198…………
5.4.5 L属性定义的SDT
200……………
5.4.6 5.4节的练习
204…………………
5.5 实现L属性的SDD
204…………………
5.5.1 在递归下降语法分析过程中
进行翻译
205………………………
5.5.2 边扫描边生成代码
207……………
5.5.3 L属性的SDD和LL语法
分析
208……………………………
5.5.4 L属性的SDD的自底向上语法
分析
212……………………………
5.5.5 5.5节的练习
214…………………
5.6 第5章总结
215…………………………
5.7 第5章参考文献
216……………………
第6章 中间代码生成
217…………………
6.1 语法树的变体
218………………………
6.1.1 表达式的有向无环图
218…………
6.1.2 构造DAG的值编码方法
219………
6.1.3 6.1节的练习
220…………………
6.2 三地址代码
221…………………………
6.2.1 地址和指令
221……………………
6.2.2 四元式表示
223……………………
6.2.3 三元式表示
223……………………
6.2.4 静态单赋值形式
225………………
6.2.5 6.2节的练习
225…………………
6.3 类型和声明
225…………………………
6.3.1 类型表达式
226……………………
6.3.2 类型等价
227………………………
6.3.3 声明
227……………………………
6.3.4 局部变量名的存储布局
227………
6.3.5 声明的序列
229……………………
6.3.6 记录和类中的字段
230……………
6.3.7 6.3节的练习
230…………………
6.4 表达式的翻译
231………………………
6.4.1 表达式中的运算
231………………
6.4.2 增量翻译
232………………………
6.4.3 数组元素的寻址
233………………
6.4.4 数组引用的翻译
234………………
6.4.5 6.4节的练习
235…………………
6.5 类型检查
236……………………………
6.5.1 类型检查规则
236…………………
6.5.2 类型转换
237………………………
6.5.3 函数和运算符的重载
238…………
6.5.4 6.5节的练习
239…………………
6.6 控制流
239……………………………
6.6.1 布尔表达式
240……………………
6.6.2 短路代码
240………………………
6.6.3 控制流语句
240……………………
6.6.4 布尔表达式的控制流翻译
242……
6.6.5 避免生成冗余的goto指令
244……
6.6.6 布尔值和跳转代码
245……………
6.6.7 6.6节的练习
246…………………
6.7 回填
246………………………………
6.7.1 使用回填技术的一趟式目标
代码生成
246………………………
6.7.2 布尔表达式的回填
247……………
6.7.3 控制转移语句
249…………………
6.7.4 break语句、 continue语句和
goto语句
250………………………
6.7.5 6.7节的练习
251…………………
6.8 switch语句
252…………………………
6.8.1 switch语句的翻译
252……………
6.8.2 switch语句的语法制导翻译
253……
6.8.3 6.8节的练习
254…………………
6.9 过程的中间代码
254……………………
6.10 第6章总结
255………………………
6.11 第6章参考文献
256…………………
第7章 运行时刻环境
258…………………
7.1 存储组织
258……………………………
7.2 空间的栈式分配
259……………………
7.2.1 活动树
260…………………………
7.2.2 活动记录
262………………………
7.2.3 调用代码序列
263…………………
7.2.4 栈中的变长数据
265………………
7.2.5 7.2节的练习
266…………………
7.3 栈中非局部数据的访问
267……………
7.3.1 没有嵌套过程时的数据访问
267…
7.3.2 和嵌套过程相关的问题
267………
7.3.3 一个支持嵌套过程声明的
语言
268……………………………
7.3.4 嵌套深度
268………………………
7.3.5 访问链
269…………………………
7.3.6 处理访问链
270……………………
7.3.7 过程型参数的访问链
271…………
7.3.8 显示表
272…………………………
7.3.9 7.3节的练习
273…………………
7.4 堆管理
274……………………………
7.4.1 存储管理器
274……………………
7.4.2 一台计算机的存储层次结构
275……
7.4.3 程序中的局部性
276………………
7.4.4 碎片整理
278………………………
7.4.5 人工回收请求
280…………………
7.4.6 7.4节的练习
282…………………
7.5 垃圾回收概述
282………………………
7.5.1 垃圾回收器的设计目标
282………
7.5.2 可达性
284…………………………
7.5.3 引用计数垃圾回收器
285…………
7.5.4 7.5节的练习
286…………………
7.6 基于跟踪的回收的介绍
286……………
7.6.1 基本的标记-清扫式回收器
287……
7.6.2 基本抽象
288………………………
7.6.3 标记-清扫式算法的优化
289……
7.6.4 标记并压缩的垃圾回收器
290……
7.6.5 复制回收器
292……………………
7.6.6 开销的比较
293……………………
7.6.7 7.6节的练习
294…………………
7.7 第7章总结
294…………………………
7.8 第7章参考文献
295……………………
第8章 代码生成
298………………………
8.1 代码生成器设计中的问题
299…………
8.1.1 代码生成器的输入
299……………
8.1.2 目标程序
299………………………
8.1.3 指令选择
300………………………
8.1.4 寄存器分配
301……………………
8.1.5 求值顺序
302………………………
8.2 目标语言
302……………………………
8.2.1 一个简单的目标机模型
302…………
8.2.2 程序和指令的代价
304……………
8.2.3 8.2节的练习
304…………………
8.3 目标代码中的地址
306…………………
8.3.1 静态分配
306………………………
8.3.2 栈分配
307…………………………
8.3.3 名字的运行时刻地址
309…………
8.3.4 8.3节的练习
309…………………
8.4 基本块和流图
310………………………
8.4.1 基本块
311…………………………
8.4.2 后续使用信息
312…………………
8.4.3 流图
312……………………………
8.4.4 流图的表示方式
313………………
8.4.5 循环
313……………………………
8.4.6 8.4节的练习
314…………………
8.5 基本块的优化
314………………………
8.5.1 基本块的DAG表示
314……………
8.5.2 寻找局部公共子表达式
315…………
8.5.3 消除死代码
316……………………
8.5.4 代数恒等式的使用
316……………
8.5.5 数组引用的表示
317………………
8.5.6 指针赋值和过程调用
318…………
8.5.7 从DAG到基本块的重组
319………
8.5.8 8.5节的练习
320…………………
8.6 一个简单的代码生成器
320……………
8.6.1 寄存器和地址描述符
321…………
8.6.2 代码生成算法
321…………………
8.6.3 函数getReg的设计
324……………
8.6.4 8.6节的练习
324…………………
8.7 窥孔优化
325……………………………
8.7.1 消除冗余的加载和保存指令
325……
8.7.2 消除不可达代码
326………………
8.7.3 控制流优化
326……………………
8.7.4 代数化简和强度消减
327…………
8.7.5 使用机器特有的指令
327…………
8.7.6 8.7节的练习
327…………………
8.8 寄存器分配和指派
327…………………
8.8.1 全局寄存器分配
328………………
8.8.2 使用计数
328………………………
8.8.3 外层循环的寄存器指派
330………
8.8.4 通过图着色方法进行寄存器
分配
330……………………………
8.8.5 8.8节的练习
331…………………
8.9 通过树重写来选择指令
331……………
8.9.1 树翻译方案
331……………………
8.9.2 通过覆盖一个输入树来生成
代码
333……………………………
8.9.3 通过扫描进行模式匹配
334………
8.9.4 用于语义检查的例程
335…………
8.9.5 通用的树匹配方法
335……………
8.9.6 8.9节的练习
336…………………
8.10 表达式的优化代码的生成
337…………
8.10.1 Ershov数
337……………………
8.10.2 从带标号的表达式树生成
代码
337…………………………
8.10.3 寄存器数量不足时的表达式
求值
338…………………………
8.10.4 8.10节的练习
340………………
8.11 使用动态规划的代码生成
340…………
8.11.1 连续求值
340……………………
8.11.2 动态规划的算法
341………………
8.11.3 8.11节的练习
343………………
8.12 第8章总结
343………………………
8.13 第8章参考文献
344…………………
第9章 机器无关优化
346…………………
9.1 优化的主要来源
346……………………
9.1.1 冗余的原因
346……………………
9.1.2 一个贯穿本章的例子:快速
排序
347……………………………
9.1.3 保持语义不变的转换
348…………
9.1.4 全局公共子表达式
349……………
9.1.5 复制传播
350………………………
9.1.6 死代码消除
350……………………
9.1.7 代码移动
351………………………
9.1.8 归纳变量和强度消减
351…………
9.1.9 9.1节的练习
353…………………
9.2 数据流分析简介
354……………………
9.2.1 数据流抽象
354……………………
9.2.2 数据流分析模式
355………………
9.2.3 基本块上的数据流模式
356………
9.2.4 到达定值
357………………………
9.2.5 活跃变量分析
362…………………
9.2.6 可用表达式
363……………………
9.2.7 小结
365……………………………
9.2.8 9.2节的练习
365…………………
9.3 数据流分析基础
367……………………
9.3.1 半格
368……………………………
9.3.2 传递函数
371………………………
9.3.3 通用框架的迭代算法
372…………
9.3.4 数据流解的含义
374………………
9.3.5 9.3节的练习
375…………………
9.4 常量传播
376……………………………
9.4.1 常量传播框架的数据流值
376……
9.4.2 常量传播框架的交汇运算
377……
9.4.3 常量传播框架的传递函数
377……
9.4.4 常量传递框架的单调性
378………
9.4.5 常量传播框架的不可分配性
378……
9.4.6 对算法结果的解释
379……………
9.4.7 9.4节的练习
380…………………
9.5 流图中的循环
380………………………
9.5.1 支配结点
380………………………
9.5.2 深度优先排序
382…………………
9.5.3 深度优先生成树中的边
384………
9.5.4 回边和可归约性
384………………
9.5.5 流图的深度
385……………………
9.5.6 自然循环
385………………………
9.5.7 迭代数据流算法的收敛速度
386……
9.5.8 9.5节的练习
388…………………
9.6 第9章总结
389…………………………
9.7 第9章参考文献
391……………………
附录 一个完整的编译器前端
394…………
