编译器设计:第2版(构建现代编译器必需的核心技术是不可多得的参考手册)

2.4.2 　从正则表达式到NFA：Thompson构造法　　33
2.4.3 　从NFA到DFA：子集构造法　　34
2.4.4 　从DFA到最小DFA：Hopcroft算法　　39
2.4.5 　将DFA用做识别器　　42
2.5 　实现词法分析器　　43
2.5.1 　表驱动词法分析器　　44
2.5.2 　直接编码的词法分析器　　48
2.5.3 　手工编码的词法分析器　　50
2.5.4 　处理关键字　　53
2.6 　高级主题　　54
2.6.1 　从DFA到正则表达式　　54
2.6.2 　DFA最小化的另一种方法：Brzozowski算法　　55
2.6.3 　无闭包的正则表达式　　56
2.7 　小结和展望　　57
第3章 　语法分析器　　61
3.1 　简介　　61
3.2 　语法的表示　　62
3.2.1 　为什么不使用正则表达式　　62
3.2.2 　上下文无关语法　　63
3.2.3 　更复杂的例子　　66
3.2.4 　将语义编码到结构中　　69
3.2.5 　为输入符号串找到推导　　71
3.3 　自顶向下语法分析　　71
3.3.1 　为进行自顶向下语法分析而转换语法　　73
3.3.2 　自顶向下的递归下降语法分析器　　81
3.3.3 　表驱动的LL(1)语法分析器　　83
3.4 　自底向上语法分析　　87
3.4.1 　LR(1)语法分析算法　　89
3.4.2 　构建LR(1)表　　94
3.4.3 　表构造过程中的错误　　103
3.5 　实际问题　　106
3.5.1 　出错恢复　　106
3.5.2 　一元运算符　　107
3.5.3 　处理上下文相关的二义性　　108
3.5.4 　左递归与右递归　　109
3.6 　高级主题　　111
3.6.1 　优化语法　　111
3.6.2 　减小LR(1)表的规模　　113
3.7 　小结和展望　　116
第4章 　上下文相关分析　　120
4.1 　简介　　120
4.2 　类型系统简介　　122
4.2.1 　类型系统的目标　　123
4.2.2 　类型系统的组件　　126
4.3 　属性语法框架　　134
4.3.1 　求值的方法　　137
4.3.2 　环　　138
4.3.3 　扩展实例　　138
4.3.4 　属性语法方法的问题　　143
4.4 　特设语法制导转换　　146
4.4.1 　特设语法制导转换的实现　　147
4.4.2 　例子　　148
4.5 　高级主题　　155
4.5.1 　类型推断中更困难的问题　　155
4.5.2 　改变结合性　　157
4.6 　小结和展望　　158
第5章 　中间表示　　162
5.1 　简介　　162
5.2 　图IR　　165
5.2.1 　与语法相关的树　　165
5.2.2 　图　　168
5.3 　线性IR　　173
5.3.1 　堆栈机代码　　173
5.3.2 　三地址代码　　174
5.3.3 　线性代码的表示　　175
5.3.4 　根据线性代码建立控制流图　　176
5.4 　将值映射到名字　　179
5.4.1 　临时值的命名　　179
5.4.2 　静态单赋值形式　　180
5.4.3 　内存模型　　183
5.5 　符号表　　186
5.5.1 　散列表　　187
5.5.2 　建立符号表　　187
5.5.3 　处理嵌套的作用域　　188
5.5.4 　符号表的许多用途　　191
5.5.5 　符号表技术的其他用途　　193
5.6 　小结和展望　　193
第6章 　过程抽象　　198
6.1 　简介　　198
6.2 　过程调用　　200
6.3 　命名空间　　203
6.3.1 　类Algol语言的命名空间　　203
6.3.2 　用于支持类Algol语言的运行时结构　　206
6.3.3 　面向对象语言的命名空间　　210
6.3.4 　支持面向对象语言的运行时结构　　214
6.4 　过程之间值的传递　　219
6.4.1 　传递参数　　219
6.4.2 　返回值　　222
6.4.3 　确定可寻址性　　223
6.5 　标准化链接　　227
6.6 　高级主题　　231
6.6.1 　堆的显式管理　　231
6.6.2 　隐式释放　　234
6.7 　小结和展望　　237
第7章 　代码形式　　245
7.1 　简介　　245
7.2 　分配存储位置　　247
7.2.1 　设定运行时数据结构的位置　　248
7.2.2 　数据区的布局　　249
7.2.3 　将值保持在寄存器中　　252
7.3 　算术运算符　　253
7.3.1 　减少对寄存器的需求　　254
7.3.2 　访问参数值　　255
7.3.3 　表达式中的函数调用　　257
7.3.4 　其他算术运算符　　257
7.3.5 　混合类型表达式　　258
7.3.6 　作为运算符的赋值操作　　258
7.4 　布尔运算符和关系运算符　　259
7.4.1 　表示　　260
7.4.2 　对关系操作的硬件支持　　262
7.5 　数组的存储和访问　　265
7.5.1 　引用向量元素　　266
7.5.2 　数组存储布局　　267
7.5.3 　引用数组元素　　268
7.5.4 　范围检查　　272
7.6 　字符串　　273
7.6.1 　字符串表示　　273
7.6.2 　字符串赋值　　274
7.6.3 　字符串连接　　275
7.6.4 　字符串长度　　276
7.7 　结构引用　　277
7.7.1 　理解结构布局　　277
7.7.2 　结构数组　　278
7.7.3 　联合和运行时标记　　278
7.7.4 　指针和匿名值　　279
7.8 　控制流结构　　281
7.8.1 　条件执行　　281
7.8.2 　循环和迭代　　283
7.8.3 　case语句　　286
7.9 　过程调用　　289
7.9.1 　实参求值　　290
7.9.2 　保存和恢复寄存器　　291
7.10 　小结和展望　　292
第8章 　优化简介　　298
8.1 　简介　　298
8.2 　背景　　299
8.2.1 　例子　　300
8.2.2 　对优化的考虑　　303
8.2.3 　优化的时机　　305
8.3 　优化的范围　　306
8.4 　局部优化　　308
8.4.1 　局部值编号　　309
8.4.2 　树高平衡　　314
8.5 　区域优化　　321
8.5.1 　超局部值编号　　321
8.5.2 　循环展开　　324
8.6 　全局优化　　327
8.6.1 　利用活动信息查找未初始化变量　　328
8.6.2 　全局代码置放　　331
8.7 　过程间优化　　336
8.7.1 　内联替换　　337
8.7.2 　过程置放　　340
8.7.3 　针对过程间优化的编译器组织结构　　344
8.8 　小结和展望　　345
第9章 　数据流分析　　350
9.1 　简介　　350
9.2 　迭代数据流分析　　351
9.2.1 　支配性　　352
9.2.2 　活动变量分析　　355
9.2.3 　数据流分析的局限性　　359
9.2.4 　其他数据流问题　　361
9.3 　静态单赋值形式　　365
9.3.1 　构造静态单赋值形式的简单方法　　366
9.3.2 　支配边界　　366
9.3.3 　放置 函数　　369
9.3.4 　重命名　　372
9.3.5 　从静态单赋值形式到其他形式的转换　　376
9.3.6 　使用静态单赋值形式　　379
9.4 　过程间分析　　383
9.4.1 　构建调用图　　383
9.4.2 　过程间常量传播　　385
9.5 　高级主题　　388
9.5.1 　结构性数据流算法和可归约性　　388
9.5.2 　加速计算支配性的迭代框架算法的执行　　391
9.6 　小结和展望　　393
第10章 　标量优化　　398
10.1 　简介　　398
10.2 　消除无用和不可达代码　　401
10.2.1 　消除无用代码　　402
10.2.2 　消除无用控制流　　404
10.2.3 　消除不可达代码　　406
10.3 　代码移动　　407
10.3.1 　缓式代码移动　　407
10.3.2 　代码提升　　413
10.4 　特化　　414
10.4.1 　尾调用优化　　415
10.4.2 　叶调用优化　　416
10.4.3 　参数提升　　416
10.5 　冗余消除　　417
10.5.1 　值相同与名字相同　　417
10.5.2 　基于支配者的值编号算法　　418
10.6 　为其他变换制造时机　　421
10.6.1 　超级块复制　　421
10.6.2 　过程复制　　422
10.6.3 　循环外提　　423
10.6.4 　重命名　　423
10.7 　高级主题　　425
10.7.1 　合并优化　　425
10.7.2 　强度削减　　429
10.7.3 　选择一种优化序列　　437
10.8 　小结和展望　　438
第11章 　指令选择　　441
11.1 　简介　　441
11.2 　代码生成　　443
11.3 　扩展简单的树遍历方案　　445
11.4 　通过树模式匹配进行指令选择　　450
11.4.1 　重写规则　　451
11.4.2 　找到平铺方案　　454
11.4.3 　工具　　457
11.5 　通过窥孔优化进行指令选择　　458
11.5.1 　窥孔优化　　458
11.5.2 　窥孔变换程序　　463
11.6 　高级主题　　465
11.6.1 　学习窥孔模式　　465
11.6.2 　生成指令序列　　466
11.7 　小结和展望　　467
第12章 　指令调度　　470
12.1 　简介　　470
12.2 　指令调度问题　　473
12.2.1 　度量调度质量的其他方式　　477
12.2.2 　是什么使调度这样难　　478
12.3 　局部表调度　　478
12.3.1 　算法　　478
12.3.2 　调度具有可变延迟的操作　　481
12.3.3 　扩展算法　　481
12.3.4 　在表调度算法中打破平局　　481
12.3.5 　前向表调度与后向表调度　　482
12.3.6 　提高表调度的效率　　484
12.4 　区域性调度　　485
12.4.1 　调度扩展基本程序块　　486
12.4.2 　跟踪调度　　487
12.4.3 　通过复制构建适当的上下文环境　　488
12.5 　高级主题　　489
12.5.1 　软件流水线的策略　　490
12.5.2 　用于实现软件流水线的算法　　492
12.6 　小结和展望　　495
第13章 　寄存器分配　　499
13.1 　简介　　499
13.2 　背景问题　　500
13.2.1 　内存与寄存器　　500
13.2.2 　分配与指派　　501
13.2.3 　寄存器类别　　502
13.3 　局部寄存器分配和指派　　502
13.3.1 　自顶向下的局部寄存器分配　　503
13.3.2 　自底向上的局部寄存器分配　　504
13.3.3 　超越单个程序块　　506
13.4 　全局寄存器分配和指派　　509
13.4.1 　找到全局活动范围　　511
13.4.2 　估算全局逐出代价　　512
13.4.3 　冲突和冲突图　　513
13.4.4 　自顶向下着色　　515
13.4.5 　自底向上着色　　517
13.4.6 　合并副本以减小度数　　518
13.4.7 　比较自顶向下和自底向上全局分配器　　520
13.4.8 　将机器的约束条件编码到冲突图中　　521
13.5 　高级主题　　523
13.5.1 　图着色寄存器分配方法的变体　　523
13.5.2 　静态单赋值形式上的全局寄存器分配　　525
13.6 　小结和展望　　526
附录A 　ILOC　　531
附录B 　数据结构　　540
参考文献　　559
索引　　574

.　　打开一个现代优化编译器，你会发现各式各样的技术。编译器使用贪婪启发式搜索来探索很大的解空间，使用确定性有限自动机来识别输入中的单词。不动点算法被用于推断程序行为，通过定理证明程序和代数化简器来预测表达式的值。编译器利用快速模式匹配算法将抽象计算映射到机器层次上的操作。它们使用线性丢番图方程和普瑞斯伯格算术（Pressburger arithmetic）来分析数组下标。最后，编译器使用了大量经典的算法和数据结构，如散列表、图算法和稀疏集实现方法等。
　　本书尝试同时阐释编译器构建的艺术和科学这两方面内容。通过选取足够广泛的题材，向读者表明，确实存在一些折中的解决方案，而设计决策的影响可能是微妙而深远的。另一方面，本书也省去了某些长期以来都列入本科编译器构建课程的技术，随着市场、语言和编译器技术或工具可用性方面的改变，这些技术已变得不那么重要了。
　　讲述方法
　　编译器构建是一种工程设计实践。每个方案的成本、优点和复杂程度各异，编译器编写者必须在多种备选方案中做出抉择。每个决策都会影响到最终的编译器。最终产品的质量，取决于抉择过程中所做的每一个理性决断。
　　因而，对于编译器中的许多设计决策来说，并不存在唯一的正确答案。即使在“理解透彻”和“已解决”的问题中，设计和实现中的细微差别都会影响到编译器的行为及其产生的代码的质量。每个决策都涉及许多方面。举例来说，中间表示的选择对于编译器中其余部分有着深刻的影响，无论是时间和空间需求，还是应用不同算法的难易程度。但实际上确定该决策时，通常可供设计者考虑的时间并不多。第5章考察了中间表示的空间需求，以及其他一些应该在选择中间表示时考虑的问题。在本书中其他地方，我们会再次提出该问题，既会在正文中直接提出，也会在习题里间接提出。
　　本书探索了编译器的设计空间，既从深度上阐释问题，也从广度上探讨可能的答案。它给出了这些问题的某些解决方法，并说明了使用这些方案的约束条件。编译器编写者需要理解这些问题及其答案，以及所作决策对编译器设计的其他方面的影响。只有这样，编写者才能作出理性和明智的选择。
　　思想观念
　　本书阐释了我们在构建编译器方面的思想观念，这是在各自超过25年的研究、授课和实践过程中发展起来的。例如，中间表示应该展示最终代码所关注的那些细节，这种理念导致了对底层表示的偏爱。又比如，值应该驻留在寄存器中，直至分配器发现无法继续保留它为止，这种做法产生了使用虚拟寄存器的例子，以及仅在无可避免时才将值存储到内存的例子。每个编译器都应该包括优化，它简化了编译器其余的部分。多年以来的经验，使得我们能够理性地选择书的主题和展现方式。
　　关于编程习题的选择
　　编译器构建方面的课程，提供了在一个具体应用程序（编译器）环境中探索软件设计问题的机会，任何具备编译器构建课程背景的学生，都已经透彻理解了该应用程序的基本功能。在多数编译器设计课程中，编程习题发挥了很大的作用。
　　我们以这样的方式讲授过这门课：学生从头到尾构建一个简单的编译器，从生成的词法分析器和语法分析器开始，结束于针对某个简化的RISC指令集的代码生成器。我们也以另一种方式讲授过这门课程，学生编写程序来解决各个良好自包含的问题，诸如寄存器分配或指令调度。编程习题的选择实际上非常依赖于本课程在相关课程中所扮演的角色。
　　在某些学校，编译器课程充当高年级的顶级课程，将来自许多其他课程的概念汇集到一个大型的实际设计和实现项目中。在这样的课程中，学生应该为一门简单的语言编写一个完整的编译器，或者修改一个开源的编译器，以支持新的语言或体系结构特性。这门课程可以按本书的内容组织，从头到尾讲授本书的内容。
　　在另外一些学校，编译器设计出现在其他课程中，或以其他方式呈现在教学中。此时，编译器设计教师应该专注于算法及其实现，比如局部寄存器分配器或树高重新平衡趟这样的编程习题。在这种情况下，可以选择性讲解本书中的内容，也可以调整讲述的顺序，以满足编程习题的需求。例如，在莱斯大学，我们通常使用简单的局部寄存器分配器作为第一个编程习题，任何具有汇编语言编程经验的学生，都可以理解该问题的基本要素。但这种策略，需要让学生在学习第2章之前，首先接触第13章的内容。
　　不管采用哪种方案，本课程都应该从其他课程取材。在计算机组织结构、汇编语言编程、操作系统、计算机体系结构、算法和形式语言之间，存在着明显的关联。尽管编译器构建与其他课程的关联不那么明显，但这种关联同等重要。第7章中讨论的字符复制，对于网络协议、文件服务器和Web服务器等应用程序的性能而言，都发挥着关键的作用。第2章中用于词法分析的技术可以应用到文本编辑和URL过滤等领域。第13章中自底向上的局部寄存器分配器是最优离线页面替换算法MIN的“近亲”。
　　补充材料
　　还有一些补充的资源可用，可帮助读者改编本书的内容，使之适用于自己的课程。这包括作者在莱斯大学讲授这门课程的一套完整的讲义以及习题答案。读者可以联系本地的Elsevier业务代表，询问如何获取这些补充材料 。
　　致谢
　　许多人参与了第1版的出版工作，他们的贡献也体现在第2版中。许多人指出了第1版中的问题，包括Amit Saha、Andrew Waters、Anna Youssefi、Ayal Zachs、Daniel Salce、David Peixotto、Fengmei Zhao、Greg Malecha、Hwansoo Han、Jason Eckhardt、Jeffrey Sandoval、John Elliot、Kamal Sharma、Kim Hazelwood、Max Hailperin、Peter Froehlich、Ryan Stinnett、Sachin Rehki、Sa?nak Ta??rlar、Timothy Harvey和Xipeng Shen，在此向他们致谢。我们还要感谢第2版的审阅者，包括Jeffery von Ronne、Carl Offner、David Orleans、K. Stuart Smith、John Mallozzi、Elizabeth White和Paul C. Anagnostopoulos。Elsevier的产品团队，特别是Alisa Andreola、Andre Cuello和Megan Guiney，在将草稿转换成书的过程中发挥了关键作用。所有这些人都以其深刻的洞察力和无私的帮助，从各个重要方面提升了本书的质量。
　　最后，在过去5年中，无论是从精神方面，还是从知识方面，许多人都为我们提供了莫大的支持。首先，我们的家庭和莱斯大学的同事都在不断地鼓励我们。特别感谢小女Christine和Carolyn，她们耐心容忍了无数次关于编译器构建方面各种主题的长时间讨论。Nate McFadden以其耐心和出色的幽默感，从开始到出版，一直指导着本书的工作。Penny Anderson对于日常行政事务管理方面的帮助对于本书的完成至关重要。对所有这些人，我们表示衷心的感谢。