编译器设计(第2版)

深入剖析现代编译器运用的算法和技术。强调代码优化和代码生成。体现编译原理教学的**新理念

本书是编译器设计领域的经典著作，主要从以下四部分详解了编译器的设计过程。第一部分涵盖编译器前端设计和建立前端所用工具的设计和构建；第二部分探讨从源代码到编译器中间形式的映射，考察前端为优化器和后端所生成代码的种类；第三部分介绍代码优化，同时包含对分析和转换的进一步处理；第四部分专门讲解编译器后端使用的算法。本书适合作为高等院校计算机专业本科生和研究生编译课程的教材和参考书，也可供相关技术人员参考。

第1章编译概观1
1．1简介1
1．2编译器结构4
1．3转换概述7
1．3．1前端8
1．3．2优化器10
1．3．3后端11
1．4小结和展望15
第2章词法分析器17
2．1简介17
2．2识别单词18
2．2．1识别器的形式化20
2．2．2识别更复杂的单词21
2．3正则表达式24
2．3．1符号表示法的形式化25
2．3．2示例26
2．3．3RE的闭包性质28
2．4从正则表达式到词法分析器30
2．4．1非确定性有限自动机30
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．2DFA**小化的另一种方法：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．1LR(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图IR165
5．2．1与语法相关的树165
5．2．2图168
5．3线性IR173
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．3case语句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
附录AILOC531
附录B数据结构540
参考文献559
索引574