1.1模块及接口 1
3.4.4语法和语义 5 1
目 录 1
第一部分编译基础 1
第1章 概述 1
1.1.1阶段的描述 2
1.2工具和软件 3
1.3树型语言的数据结构 3
程序设计：直线程序解释器 6
习题 8
第2章词法分析 9
2.1词法记号 9
2.2正则表达式 10
2.3有限自动机 12
2.3.1识别最长的匹配 14
2.4非确定有限自动机 14
2.4.1正规文法转换为NFA 15
2.4.2 NFA转换为DFA 16
2.5词法分析生成器 19
2.5.1 JAVACC 19
程序设计：词法分析 20
2.5.2 SableCC 20
进一步阅读 21
习题 21
第3章语法分析 24
3.1上下文无关文法 25
3.1.1推导 26
3.1.2分析树 27
3.1.3二义性文法 27
3.1.4文件结束符 29
3.2预测分析 29
3.2.1 FIRST和FOLLOW集 30
3.2.3消除左递归 33
3.2.2构造一个预测分析器 33
3.2.4左因子 35
3.2.5 出错恢复 35
3.3 LR分析 36
3.3.1 LR分析器 38
3.3.2 LR（0）分析器生成器 38
3.3.3 SLR分析器生成器 41
3.3.4 LR（1）项目和LR（1）分析表 42
3.3.5 LALR（1）分析表 44
3.3.6文法类型的层次结构 44
3.4使用分析器生成器 45
3.3.7二义性文法的LR分析 45
3.4.1 JAVACC 46
3.4.2 SableCC 47
3.4.3算符优先分析法 49
3.5出错恢复 52
3.5.1用error符号恢复 52
3.5.2全局出错修复 53
习题 55
程序设计：实现分析器 55
进一步阅读 55
第4章抽象语法 59
4.1语义分析 59
4.1.1递归下降 59
4.1.2自动生成分析器 60
4.2抽象分析树 61
4.2.1位置 64
4.3访问者 64
4.3.1 MiniJava的抽象语法 67
程序设计：抽象语法 70
进一步阅读 70
习题 70
第5章语义分析 71
5.1符号表 71
5.1.1多重符号表 72
5.1.2高效率的命令符号表 73
5.1.3高效率的功能符号表 74
5.1.4符号 75
5.2 MiniJava的类型检查 77
5.2.1错误处理 79
程序设计：类型检查 79
习题 79
第6章活动纪录 81
6.1堆栈帧 82
6.1.1帧指针 84
6.1.2寄存器 84
6.1.3参数传递 85
6.1.4返回地址 86
6.1.5常驻帧变量 86
6.1.6静态连接 87
6.2 MiniJava语言编译器中的帧 88
6.2.1帧的表示 90
6.2.2局部变量 91
6.2.3临时（局部）变量和标号 92
6.2.4静态连接的管理 92
程序设计：帧 92
进一步阅读 93
习题 93
7.1中间树 96
第7章翻译成中间代码 96
7.2树的翻译 98
7.2.1表达式的类型 98
7.2.2简单变量 101
7.2.3数组变量 102
7.2.4结构化的L-值 103
7.2.5下标和域选择 103
7.2.6关于安全性 104
7.2.7算术运算 105
7.2.8条件 105
7.2.1 0记录和数组的创建 106
7.2.9字符串 106
7.2.11while循环 108
7.2.12 for循环 108
7.2.1 3函数调用 109
7.2.14静态连接 109
7.3声明 110
7.3.1变量定义 110
7.3.2函数定义 110
7.3.3段 111
7.3.4类和对象 112
习题 113
程序设计：翻译为树 113
第8章 基本块和轨迹 115
8.1规范树 116
8.1.1 ESEQ的翻译 116
8.1.2常用重写规则 117
8.1.3将CALL移至顶部 119
8.1.4语句的线性表 119
8.2时间条件分支 120
8.2.1基本块 120
8.2.3完成 121
8.2.2轨迹 121
8.2.4最佳轨迹 122
进一步阅读 122
习题 122
第9章指令选择 124
9.1指令选择的算法 126
9.1.1 maximal munch算法 127
9.1.2动态编程 128
9.1.3树的文法规则 129
9.1.5表示算法的效率 131
9.1.4快速匹配 131
9.2 CISC机 132
9.3 MiniJava编译器中的指令选择 134
9.3.1抽象的汇编语言指令 135
9.3.2生成汇编指令 137
9.3.3过程调用 139
9.3.4如果不存在帧指针 139
程序设计：指令选择 140
进一步阅读 142
习题 143
第10章活性分析 144
10.1数据流的解 145
10.1.1活性的计算 146
10.1.2集合的表示 147
10.1.3时间复杂度 148
10.1.4最少的确定点 148
10.1.5静态与动态活性 149
10.1.6干扰图 150
10.2 MiniJava编译器中的活性分析 151
10.2.1图 151
10.2.2控制流图 152
10.2.3活性分析 153
程序设计：构造流图 154
程序设计：活性 154
习题 154
第11章寄存器分配 156
11.1简化着色 156
11.1.1举例 157
11.2结合 158
11.2.1溢出 160
11.3.2调用保存寄存器和被调用保存寄存器 161
11.3预着色节点 161
11.3.1机器寄存器临时变量的复制 161
11.3.3预着色节点的例子 162
11.4图着色实现 165
11.4.1数据结构 166
11.4.2不变量 167
11.4.3程序代码 167
11.5树的寄存器分配 172
程序设计：图着色 175
习题 176
进一步阅读 176
第12章使之成为整体 179
程序设计进入／退出过程 179
程序设计：使程序运行 181
第二部分高级课题 182
第13章无用信息收集 182
13.1标记—清除收集机制 183
13.2引用计数 186
13.3复制收集 187
13.4世代收集 190
13.5增量收集 192
13.6 Baker算法 193
13.7编译器接口 194
13.7.1快速分配 194
13.7.2数据分布描述 195
13.7.3派生指针 195
程序设计：描述符 196
程序设计：无用信息收集 197
进一步阅读 197
习题 198
第14章面向对象语言 200
14.1类扩展 200
14.2数据字段的单继承 201
14.2.1方法 201
14.3多继承 202
14.4类成员测试 204
14.5私有字段成员和方法 207
14.6无类语言 207
14.7优化面向对象程序 207
进一步阅读 208
程序设计：带类扩展的MiniJava 208
习题 209
第15章函数式编程语言 211
15.1一种简单的函数式语言 211
15.2闭包 213
15.2.1堆分配激活记录 213
15.3恒变量 214
15.3.1基于连续的I/O 216
15.3.2语言变换 216
15.3.3纯函数式语言的优化 217
15.4内部扩展 218
15.5闭包转换 224
15.6有效尾部递归 226
15.7惰性评估 227
15.7.1按名调用评估 228
15.7.2按需调用 229
15.7.3一个惰性程序的计算 230
15.7.4推高不变量 230
15.7.5惰性函数式程序的优化 231
15.7.6严格性分析 233
进一步阅读 235
程序设计：编译函数式语言 236
习题 236
第16章 多态类型 237
16.1参数多态 237
16.2多态类型检查 240
16.3多态程序的翻译 244
16.3.1指针、整型和包装 245
进一步阅读 246
16.4静态重载的解决方法 246
习题 247
第17章数据流分析 248
17.1流分析的中间表示 249
17.1.1四元组 249
17.2多种的数据流分析 250
17.2.1到达定义 251
17.2.2可用表达式 252
17.2.3到达表达式 253
17.2.4活性分析 253
17.3.2常量传播 254
17.3.3复制传播 254
17.3.1公用子表达式消除 254
17.3使用数据流分析的变换 254
17.3.4死代码消除 255
17.4加快数据流分析 255
17.4.1位向量 255
17.4.2基本块 255
17.4.3节点排序 256
17.4.4 use-def和def-use链 257
17.4.5 work-list算法 257
17.4.6增量式数据流分析 258
17.5别名分析 261
17.5.1基于类型的别名分析 262
17.5.2基于流的别名分析 262
17.5.3使用may-alias信息 264
17.5.4严格纯函数式语言中的别名分析 265
进一步阅读 265
习题 265
第18章循环优化 267
18.1必经节点 269
18.1.1寻找必经节点的算法 269
18.1.2直接必经节点 270
18.1.3循环 271
18.1.4循环前置首部 272
18.2循环不变量的计算 272
18.2.1提升 273
18.3 归纳变量 274
18.3.1归纳变量检查 275
18.3.2强度削减 276
18.3.3消除 277
18.3.4重写比较 277
18.4数组边界检查 278
18.5循环展开 281
进一步阅读 282
习题 282
第19章静态单赋值表 284
19.1转化为SSA表 286
19.1.1插入φ-function的准则 286
19.1.2必经前端 287
19.1.3插入φ-function 289
19.1.4变量重命名 290
19.2.1深度优先生成（Spanning）树 291
19.2必经节点树的有效计算 291
19.1.5边分离 291
19.2.2半必经节点 292
19.2.3 Lengauer-Tarjan算法 293
19.3采用SSA优化算法 296
19.3.1消除死代码 296
19.3.2简单常量传播 297
19.3.3条件常量复制 298
19.3.4保存必经性质 300
19.4.1存储相关 301
19.4数组，指针和存储 301
19.5控制相关图 302
19.5.1积极的死代码消除 304
19.6从SSA表后的转换 305
19.6.1关于SSA的活性的分析 305
19.7函数式中介表 306
进一步阅读 309
习题 310
第20章流水线和调度 313
20.1不受资源限制的循环调度 315
20.2资源限制循环流水线 318
20.2.1模调度 319
20.2.2发现最小启动间隔 320
20.2.3其他控制流 322
20.2.4编译器应该调度指令吗 323
20.3分支预测 323
20.3.1静态转移预测 324
20.3.2编译器应该预测分支转移吗？ 324
进一步阅读 325
习题 326
21.1高速缓冲存储器结构 328
第21章分级存储器体系 328
21.2 cache块的排列 330
21.2.1指令cache的对齐 331
21.3预取指令 332
21.4循环交换 335
21.5分块 336
21.6无用信息收集和分级存储器体系 338
进一步阅读 339
习题 340
附录 MiniJava语言参考手册 341
参考文献 343