专家指导委员会对本书的赞誉 1
译者序 1
前言 1
第1章 编译总览 1
1.1 概述 1
出版者的话 1
1.2 为什么研究编译器构造法 2
1.3 编译的基本原则 2
1.4 编译器的结构 3
1.5.1 理解输入 5
1.5 翻译综述 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
本章注释 41
2.7 概括和展望 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.3 扩展例子 102
4.3.2 循环性 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.2 分类法 121
第5章 中间表示 121
5.1 概述 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.1 概述 144
第6章 过程抽象 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.1 平凡基地址 161
6.5 建立可寻址性 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.1 概述 177
第7章 代码形态 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.6 作为操作符的赋值 184
7.3.5 混合型表达式 184
7.3.4 其他算术操作符 184
7.3.3 表达式中的函数调用 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.8 控制流结构 204
7.7.4 联合和运行时标签 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.10.1 单一类，无继承 214
7.10 实现面向对象语言 214
7.9.4 叶过程的优化 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.3 冗余表达式 226
8.2.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.5.1 超局部值编号 235
8.5 比基本块大的区域上的值编号 235
8.4.5 完整程序方法 235
8.4.4 全局方法 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.2 支配 263
9.3.1 构建SSA形式的简单方法 263
9.3.3 放置φ函数 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.1 概述 283
第10章 标量优化 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.1 优化组合 302
10.4 高级话题 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 窥孔转换器 329
11.5 高级话题 334
11.5.1 学习窥孔模式 334
11.5.2 生成指令序列 335
11.6 概括和展望 336
本章注释 336
12.1 概述 338
第12章 指令调度 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.1 区域调度 349
12.4 高级话题 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.3 局部寄存器分配和赋值 359
13.2.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.1 概述 380
附录A ILOC 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.6 SSA形式的表示 386
A.5.2 跳转 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