编译器工程

第1章　编译总览        1
1.1  概述        1
1.2  为什么研究编译器构造法        2
1.3  编译的基本原则        2
1.4  编译器的结构        3
1.5  翻译综述        5
1.5.1  理解输入        5
1.5.2  创建和维护运行时环境        7
1.5.3  改进代码        8
1.5.4  生成输出程序        9
1.6  编译器应有的性质        13
1.7  概括和展望        14
本章注释        15
第2章　扫描        16
2.1  概述        16
2.2  识别字        17
2.2.1  识别器的形式        18
2.2.2  识别更复杂的字        19
2.2.3  扫描器的自动构建        20
2.3  正则表达式        21
2.3.1  正则表达式的定义        22
2.3.2  例子        23
2.3.3  RE的性质        25
2.4  从正则表达式到扫描器以及从扫描器到正则表达式        26
2.4.1  非确定性有穷自动机         26
2.4.2  正则表达式到NFA：Thompson构造法        28
2.4.3  NFA到DFA：子集构造法        29
2.4.4  DFA到最小DFA：Hopcroft算法        32
2.4.5  DFA到正则表达式        34
2.4.6  将DFA作为识别器        35
2.5  实现扫描器        35
2.5.1  表驱动扫描器        35
2.5.2  直接编码扫描器        37
2.5.3  处理关键字        37
2.5.4  描述动作        38
2.6  高级话题        38
2.7  概括和展望        41
本章注释        41
第3章  语法分析        42
3.1  概述        42
3.2  表示语法        42
3.2.1  上下文无关文法        43
3.2.2  构造句子        45
3.2.3  使用结构描述优先权        48
3.2.4  发现特定派生        49
3.2.5  上下文无关文法与正则表达式的对比        50
3.3  自顶向下分析        51
3.3.1  例子        52
3.3.2  自顶向下分析的复杂因素        54
3.3.3  消除左递归        54
3.3.4  消除回溯        55
3.3.5  自顶向下递归下降分析器        59
3.4  自底向上分析        62
3.4.1  移入归约分析        63
3.4.2  发现句柄        65
3.4.3  LR(1)分析器        67
3.5  构建LR(1)表格        70
3.5.1  LR(1)项目        71
3.5.2  构造规范集合        72
3.5.3  填充表格        74
3.5.4  表构造法的出错        76
3.6  实践中的问题        78
3.6.1  错误恢复        79
3.6.2  一元操作符        79
3.6.3  处理上下文相关歧义性        80
3.6.4  左递归与右递归        81
3.7  高级话题        82
3.7.1  优化文法        83
3.7.2  减小LR(1)表格的大小        84
3.8  概括和展望        86
本章注释        87
第4章  上下文相关分析        88
4.1  概述        88
4.2  类型系统概述        89
4.2.1  类型系统的目的        89
4.2.2  类型系统的组成部分        93
4.3  属性文法框架        99
4.3.1  评估方法        101
4.3.2  循环性        102
4.3.3  扩展例子        102
4.3.4  属性文法方法的问题        107
4.4  特定语法制导翻译        109
4.4.1  实现特定语法制导翻译        110
4.4.2  例子        111
4.5  高级话题        117
4.5.1  类型推断中的较难问题        117
4.5.2  更改结合性        118
4.6  概括和展望        119
本章注释        120
第5章  中间表示        121
5.1  概述        121
5.2  分类法        121
5.3  图示IR        123
5.3.1  与语法相关的树        123
5.3.2  图        126
5.4  线性IR        128
5.4.1  栈机器代码        129
5.4.2  三地址代码        129
5.4.3  表示线性代码        130
5.5  静态单赋值形式        131
5.6  把值映射到名字        133
5.6.1  命名临时值        134
5.6.2  内存模型        135
5.7  符号表        137
5.7.1  散列表        138
5.7.2  构建符号表        139
5.7.3  处理嵌套作用域        139
5.7.4  符号表的多种运用        142
5.8  概括和展望        143
本章注释        143
第6章  过程抽象        144
6.1  概述        144
6.2  控制抽象        145
6.3  名字空间        147
6.3.1  类Algol语言的名字空间        147
6.3.2  活动记录        150
6.3.3  面向对象语言的名字空间        153
6.4  过程间的值传递        158
6.4.1  参数传递        158
6.4.2  返回值        160
6.5  建立可寻址性        161
6.5.1  平凡基地址        161
6.5.2  其他过程的局部变量        162
6.6  标准链接        164
6.7  管理内存        167
6.7.1  内存布局        167
6.7.2  堆管理算法        170
6.7.3  隐式释放        172
6.8  概括和展望        175
本章注释        176
第7章  代码形态        177
7.1  概述        177
7.2  指定存储位置        178
7.2.1  布局数据区         178
7.2.2  把值保存在寄存器中        179
7.2.3  机器特性        180
7.3  算术操作符        180
7.3.1  降低对寄存器的要求        181
7.3.2  存取参数值        183
7.3.3  表达式中的函数调用        184
7.3.4  其他算术操作符        184
7.3.5  混合型表达式        184
7.3.6  作为操作符的赋值        184
7.3.7  交换性、结合性以及数系        185
7.4  布尔操作符和关系操作符        185
7.4.1  表示        186
7.4.2  关系操作的硬件支持        189
7.4.3  选择表示        191
7.5  存储和存取数组        191
7.5.1  引用向量元素        191
7.5.2  数组存储布局        193
7.5.3  引用数组元素        194
7.5.4  范围检测        197
7.6  字符串        197
7.6.1  串的表示        198
7.6.2  串赋值        198
7.6.3  串连接        200
7.6.4  串长        201
7.7  结构引用        201
7.7.1  装入和存储匿名值        201
7.7.2  理解结构布局        202
7.7.3  结构数组        203
7.7.4  联合和运行时标签        204
7.8  控制流结构        204
7.8.1  条件执行        205
7.8.2  循环和迭代        207
7.8.3  选择语句        210
7.8.4  中断语句        211
7.9  过程调用        212
7.9.1  评估实参        212
7.9.2  过程值参数        213
7.9.3  保存和恢复寄存器        213
7.9.4  叶过程的优化        214
7.10  实现面向对象语言        214
7.10.1  单一类，无继承        214
7.10.2  单一继承        216
7.11  概括和展望        219
本章注释        219
第8章  代码优化概述        221
8.1  概述        221
8.2  背景知识        222
8.2.1  LINPACK的一个例子        223
8.2.2  优化的各种考虑        224
8.2.3  优化的机会        226
8.3  冗余表达式        226
8.3.1  构建有向无环图        227
8.3.2  值编号        229
8.3.3  冗余消除的经验        232
8.4  优化作用域        233
8.4.1  局部方法        233
8.4.2  超局部方法        233
8.4.3  区域方法        234
8.4.4  全局方法        235
8.4.5  完整程序方法        235
8.5  比基本块大的区域上的值编号        235
8.5.1  超局部值编号        235
8.5.2  基于支配者的值编号        238
8.6  全局冗余消除        241
8.6.1  计算可用表达式        242
8.6.2  取代冗余计算        243
8.6.3  结合上述两个阶段        244
8.7  高级话题        245
8.7.1  通过复制增加上下文        246
8.7.2  内联替换        247
8.8  概括和展望        248
本章注释        249
第9章  数据流分析        250
9.1  概述        250
9.2  迭代数据流分析        251
9.2.1  活变量        251
9.2.2  迭代LIVEOUT解算器的性质        256
9.2.3  数据流分析的局限性        258
9.2.4  数据流分析的其他问题        260
9.3  静态单一赋值形式        262
9.3.1  构建SSA形式的简单方法        263
9.3.2  支配        263
9.3.3  放置f函数        267
9.3.4  重命名        269
9.3.5  从SSA形式重新构造可执行代码        273
9.4  高级话题        277
9.4.1  结构数据流算法和可约性        277
9.4.2  过程间分析        279
9.5  概括和展望        281
本章注释        282
第10章  标量优化        283
10.1  概述        283
10.2  转换分类        284
10.2.1  机器无关转换        284
10.2.2  机器相关转换        286
10.3  优化示例        286
10.3.1  消除无用和不可达代码        286
10.3.2  代码移动        291
10.3.3  特化        297
10.3.4  激活其他转换        299
10.3.5  冗余消除        301
10.4  高级话题        302
10.4.1  优化组合        302
10.4.2  强度减弱        304
10.4.3  优化的其他目标        311
10.4.4  优化序列的选择        312
10.5  概括和展望        312
本章注释        313
第11章  指令筛选        315
11.1  概述        315
11.2  简单的树遍历方案         318
11.3  通过树模式匹配实现指令筛选        322
11.3.1  重写规则        323
11.3.2  寻找铺盖        326
11.3.3  工具        328
11.4  指令筛选与窥孔优化        329
11.4.1  窥孔优化        329
11.4.2  窥孔转换器        333
11.5  高级话题        334
11.5.1  学习窥孔模式        334
11.5.2  生成指令序列        335
11.6  概括和展望        336
本章注释        336
第12章  指令调度        338
12.1  概述        338
12.2  指令调度问题        339
12.2.1  调度质量的其他度量        342
12.2.2  使调度困难的因素        342
12.3  列表调度        343
12.3.1  效率        345
12.3.2  其他的优先度方案        346
12.3.3  前向与向后列表调度        346
12.3.4  使用列表调度的原因        348
12.4  高级话题        349
12.4.1  区域调度        349
12.4.2  上下文的复制        354
12.5  概括和展望        356
本章注释        356
第13章  寄存器分配        357
13.1  概述        357
13.2  背景问题        357
13.2.1  内存与寄存器        358
13.2.2  分配与赋值        358
13.2.3  寄存器分类        359
13.3  局部寄存器分配和赋值        359
13.3.1  自顶向下的局部寄存器分配        360
13.3.2  自底向上的局部寄存器分配        360
13.4  移到超出单一块的范围        363
13.4.1  活性和存活范围        363
13.4.2  块边界处的复杂性        364
13.5  全局寄存器分配和赋值        365
13.5.1  发现全局存活范围        366
13.5.2  评估全局溢出代价        367
13.5.3  冲突和冲突图        368
13.5.4  自顶向下着色        370
13.5.5  自底向上着色        371
13.5.6  接合存活范围以降低度        372
13.5.7  回顾与比较        373
13.5.8  在冲突图中编码机器限制        374
13.6  高级话题        375
13.6.1  图着色分配的若干变形        375
13.6.2  寄存器分配中较困难的问题        377
13.7  概括和展望        379
本章注释        379
附录A  ILOC        380
A.1  概述        380
A.2  命名约定        381
A.3  各种操作        382
A.3.1  算术        382
A.3.2  移位        382
A.3.3  内存操作        383
A.3.4  寄存器到寄存器的拷贝操作        383
A.4  例子        384
A.5  控制流操作        384
A.5.1  其他比较和分支语法        385
A.5.2  跳转        386
A.6  SSA形式的表示        386
附录B  数据结构        389
B.1  概述        389
B.2  表示集合        389
B.2.1  把集合表示成有序表        390
B.2.2  把集合表示成位向量        391
B.2.3  表示稀疏集合        391
B.3  实现中间表示        392
B.3.1  图式中间表示        392
B.3.2  线性中间形式        395
B.4  实现散列表        396
B.4.1  选择散列函数        397
B.4.2  开放散列        398
B.4.3  开放寻址        399
B.4.4  存储符号记录        400
B.4.5  增加嵌套词法作用域        401
B.5  一个灵活的符号表设计        403
附录注释        404
参考文献        405
练习        424
索引        452