第1章 概述 1
1.1 编译的历史 1
1.2 编译器可以做什么 3
1.2.1 编译器生成的机器代码 3
1.2.2 目标代码格式 5
1.3 解释器 6
1.4 语法和语义 7
1.4.1 静态语义 8
1.4.2 运行时语义 8
1.5 编译器的组织结构 10
1.5.1 扫描器 11
1.5.2 分析器 12
1.5.3 类型检查器（语义分析） 12
1.5.4 翻译器（程序综合） 12
1.5.5 符号表 13
1.5.6 优化器 13
1.5.7 代码生成器 13
1.5.8 编译器开发工具 14
1.6 程序设计语言和编译器设计 14
1.7 计算机体系结构和编译器设计 15
1.8 编译器设计的考虑事项 16
1.8.1 调试（开发）编译器 16
1.8.2 优化编译器 17
1.8.3 可重定向编译器 17
1.9 集成开发环境 18
练习 18
第2章 一个简单的编译器 21
2.1 ac语言的非形式化定义 21
2.2 ac语言的形式化定义 22
2.2.1 语法规范 22
2.2.2 词法单元规范 24
2.3 一个简单编译器中的阶段 25
2.4 扫描 25
2.5 分析 27
2.5.1 分析过程的预测 27
2.5.2 产生式的实现 28
2.6 抽象语法树 29
2.7 语义分析 31
2.7.1 符号表 31
2.7.2 类型检查 32
2.8 代码生成 34
练习 36
第3章 扫描——理论和实践 38
3.1 扫描器概述 38
3.2 正则表达式 40
3.3 示例 42
3.4 有限自动机和扫描器 43
3.4.1 确定性的有限自动机 44
3.5 扫描器生成工具Lex 46
3.5.1 定义Lex中的词法单元 47
3.5.2 字符类 48
3.5.3 使用正则表达式来定义词法单元 49
3.5.4 使用Lex进行字符处理 51
3.6 其他扫描器生成工具 53
3.7 构造扫描器的实际注意事项 53
3.7.1 处理标识符和字面常量 54
3.7.2 使用编译命令和列出源码行 57
3.7.3 扫描器的终止 58
3.7.4 向前看多个字符 58
3.7.5 性能上的考虑 60
3.7.6 词法错误恢复 61
3.8 正则表达式和有限自动机 63
3.8.1 把正则表达式转换为NFA 64
3.8.2 创建DFA 64
3.8.3 有限状态机的化简 66
3.8.4 把有限自动机转换为正则表达式 68
3.9 本章小结 71
练习 72
第4章 文法和分析 77
4.1 上下文无关文法 77
4.1.1 最左推导 79
4.1.2 最右推导 79
4.1.3 分析树 80
4.1.4 其他类型的文法 81
4.2 上下文无关文法的属性 81
4.2.1 简化的文法 82
4.2.2 二义性 82
4.2.3 语言定义中的错误 83
4.3 扩展文法的转换 83
4.4 分析器和识别器 84
4.5 文法分析的算法 86
4.5.1 文法表示 87
4.5.2 推导空字符串 88
4.5.3 First集合 89
4.5.4 Follow集合 92
练习 94
第5章 自顶向下分析 98
5.1 概述 98
5.2 LL（k）文法 99
5.3 递归下降的LL（l）分析器 102
5.4 表格驱动的LL（l）分析器 103
5.5 如何获得LL（l）文法 105
5.5.1 公共前缀 106
5.5.2 左递归 106
5.6 非LL（l）的语言 107
5.7 LL（l）分析器的属性 109
5.8 分析表的表示方法 110
5.8.1 精简方法 111
5.8.2 压缩方法 112
5.9 语法错误的恢复和修复 114
5.9.1 错误恢复 114
5.9.2 错误修复 115
5.9.3 LL（l）分析器中的错误检查 115
5.9.4 LL（l）分析器中的错误恢复 116
练习 117
第6章 自底向上分析 121
6.1 概述 121
6.2 移进—规约分析器 122
6.2.1 LR分析器和最右推导 123
6.2.2 把LR分析看做是编织过程（knitting） 123
6.2.3 LR分析引擎 125
6.2.4 LR分析表 125
6.2.5 LR（k）分析 128
6.3 LR（0）分析表的构造 129
6.4 冲突诊断 133
6.4.1 二义性文法 135
6.4.2 非LR（k）的文法 137
6.5 冲突解决方法和分析表的构造 138
6.5.1 SLR（k）分析表的构造 138
6.5.2 LALR（k）分析表的构造 141
6.5.3 LALR传播图 143
6.5.4 LR（k）分析表的构造 147
本章小结 151
练习 151
第7章 语法制导翻译 158
7.1 概述 158
7.1.1 语义动作和语义值 158
7.1.2 综合和继承属性 159
7.2 自底向上的语法制导翻译 160
7.2.1 示例 161
7.2.2 规则克隆 163
7.2.3 强加语义动作 164
7.2.4 进一步的文法重组 164
7.3 自顶向下的语法制导翻译 166
7.4 抽象语法树 168
7.4.1 具体和抽象语法树 168
7.4.2 高效的抽象语法树数据结构 168
7.4.3 创建抽象语法树的基础结构 169
7.5 抽象语法树的设计和构造 171
7.5.1 设计 171
7.5.2 构造 173
7.6 左值和右值的抽象语法树结构 175
7.7 抽象语法树的设计模式 177
7.7.1 结点的类层次结构 177
7.7.2 访问者模式 178
7.7.3 反射的访问者模式 179
本章小结 182
练习 182
第8章 符号表和声明处理 186
8.1 构造符号表 186
8.1.1 静态作用域 187
8.1.2 符号表的接口 188
8.2 块结构的语言和作用域 189
8.2.1 处理作用域 189
8.2.2 使用一个还是多个符号表 190
8.3 基本的实现技术 191
8.3.1 添加和查找名称 191
8.3.2 名字空间 193
8.3.3 一种高效的符号表实现方法 194
8.4 高级特性 196
8.4.1 记录和类型名 196
8.4.2 重载和类型层次结构 197
8.4.3 隐式声明 198
8.4.4 导出和导入命令 198
8.4.5 查找规则的修改 199
8.5 声明处理的基础 199
8.5.1 符号表中的属性 199
8.5.2 类型描述符的结构 200
8.5.3 使用抽象语法树进行类型检查 201
8.6 变量和类型声明 203
8.6.1 简单变量声明 203
8.6.2 类型名称的处理 204
8.6.3 类型声明 204
8.6.4 复杂的变量声明 207
8.6.5 静态数组类型 208
8.6.6 结构和记录类型 209
8.6.7 枚举类型 210
8.7 类和方法的声明 212
8.7.1 类声明的处理 213
8.7.2 方法声明的处理 215
8.8 类型检查简介 217
8.8.1 简单标识符和字面常量 219
8.8.2 赋值语句 220
8.8.3 表达式检查 220
8.8.4 复杂名称的检查 221
本章小结 224
练习 225
第9章 语义分析 229
9.1 控制结构的语义分析 229
9.1.1 可达和终止分析 231
9.1.2 if语句 232
9.1.3 While、Do和Repeat循环 234
9.1.4 for循环 236
9.1.5 break、continue、return和goto语句 238
9.1.6 switch和case语句 243
9.1.7 异常处理 246
9.2 方法调用的语义分析 251
9.3 本章小结 256
练习 256
第10章 中间表示形式 261
10.1 概述 261
10.1.1 示例 262
10.1.2 中端 263
10.2 Java虚拟机 265
10.2.1 概述和设计原则 265
10.2.2 类文件的内容 266
10.2.3 JVM指令 267
10.3 静态单赋值形式 275
10.3.1 重命名和？-函数 276
练习 277
第11章 面向虚拟机的代码生成 279
11.1 代码生成的Visitor 279
11.2 类和方法声明 280
11.2.1 类声明 282
11.2.2 方法声明 283
11.3 MethodBodyVisitor 284
11.3.1 常量 284
11.3.2 局部存储的引用 284
11.3.3 静态引用 285
11.3.4 表达式 285
11.3.5 赋值 286
11.3.6 方法调用 287
11.3.7 域引用 289
11.3.8 数组引用 290
11.3.9 条件执行 290
11.3.10 循环 291
11.4 LHS Visitor 292
11.4.1 局部引用 293
11.4.2 静态引用 293
11.4.3 域引用 293
11.4.4 数组引用 294
练习 295
第12章 运行时支持 298
12.1 静态分配 298
12.2 栈分配 299
12.2.1 类和struct中的域访问 300
12.2.2 在运行时访问活动记录 301
12.2.3 处理类和对象 302
12.2.4 处理多个作用域 303
12.2.5 程序块级的分配 305
12.2.6 关于活动记录的其他内容 306
12.3 数组 309
12.3.1 静态的一维数组 309
12.3.2 多维数组 313
12.4 堆管理 315
12.4.1 分配机制 315
12.4.2 释放机制 317
12.4.3 自动垃圾回收 318
12.5 基于区域的内存管理 323
练习 324
第13章 目标代码生成 330
13.1 字节码的翻译 331
13.1.1 内存地址的分配 332
13.1.2 数组和对象的分配 333
13.1.3 方法调用 335
13.1.4 字节码翻译的例子 337
13.2 表达式树的翻译 338
13.3 寄存器分配 342
13.3.1 On-the-Fly寄存器分配 342
13.3.2 使用图着色法的寄存器分配 344
13.3.3 基于优先级的寄存器分配 349
13.3.4 过程间寄存器分配 350
13.4 代码调度 351
13.4.1 代码调度的改进 354
13.4.2 全局和动态的代码调度 355
13.5 自动的指令选择 356
13.5.1 使用BURS进行指令选择 358
13.5.2 使用Twig进行指令选择 359
13.5.3 其他方法 360
13.6 窥孔优化 361
13.6.1 窥孔优化的层次 361
13.6.2 窥孔优化的自动生成 364
练习 364
第14章 程序优化 370
14.1 概述 370
14.1.1 为什么要进行优化 371
14.2 控制流分析 375
14.2.1 控制流图 376
14.2.2 程序和控制流结构 378
14.2.3 直接过程调用图 378
14.2.4 深度优先生成树 379
14.2.5 支配关系 382
14.2.6 简单的支配算法 383
14.2.7 快速的支配算法 385
14.2.8 支配边界 393
14.2.9 区间 395
14.3 数据流分析简介 403
14.3.1 可用表达式 404
14.3.2 活跃变量 406
14.4 数据流框架 407
14.4.1 数据流求值图 408
14.4.2 交格 409
14.4.3 转换函数 411
14.5 求值 412
14.5.1 迭代 412
14.5.2 初始化 414
14.5.3 终止问题和快速框架 415
14.5.4 分配式框架 418
14.6 常量传播 419
14.7 SSA形式 422
14.7.1 添加？-函数 424
14.7.2 重命名 424
练习 427
参考文献 436
缩略语 443