第1章 引论 1
1.1语言处理器 1
1.2一个编译器的结构 2
1.2.1词法分析 3
1.2.2语法分析 4
1.2.3语义分析 5
1.2.4中间代码生成 5
1.2.5代码优化 5
1.2.6代码生成 6
1.2.7符号表管理 6
1.2.8将多个步骤组合成趟 6
1.2.9编译器构造工具 7
1.3程序设计语言的发展历程 7
1.3.1走向高级程序设计语言 7
1.3.2对编译器的影响 8
1.3.3 1.3节的练习 8
1.4构建一个编译器的相关科学 8
1.4.1编译器设计和实现中的建模 9
1.4.2代码优化的科学 9
1.5编译技术的应用 10
1.5.1高级程序设计语言的实现 10
1.5.2针对计算机体系结构的优化 11
1.5.3新计算机体系结构的设计 12
1.5.4程序翻译 13
1.5.5软件生产率工具 14
1.6程序设计语言基础 15
1.6.1静态和动态的区别 15
1.6.2环境与状态 15
1.6.3静态作用域和块结构 17
1.6.4显式访问控制 18
1.6.5动态作用域 19
1.6.6参数传递机制 20
1.6.7别名 21
1.6.8 1.6节的练习 22
1.7第1章总结 22
1.8第1章参考文献 23
第2章 一个简单的语法制导翻译器 24
2.1引言 24
2.2语法定义 25
2.2.1文法定义 26
2.2.2推导 27
2.2.3语法分析树 28
2.2.4二义性 29
2.2.5运算符的结合性 29
2.2.6运算符的优先级 30
2.2.7 2.2节的练习 31
2.3语法制导翻译 32
2.3.1后缀表示 33
2.3.2综合属性 33
2.3.3简单语法制导定义 35
2.3.4树的遍历 35
2.3.5翻译方案 35
2.3.6 2.3节的练习 37
2.4语法分析 37
2.4.1自顶向下分析方法 38
2.4.2预测分析法 39
2.4.3何时使用?产生式 41
2.4.4设计一个预测分析器 41
2.4.5左递归 42
2.4.6 2.4节的练习 42
2.5简单表达式的翻译器 43
2.5.1抽象语法和具体语法 43
2.5.2调整翻译方案 43
2.5.3非终结符号的过程 44
2.5.4翻译器的简化 45
2.5.5完整的程序 46
2.6词法分析 47
2.6.1剔除空白和注释 48
2.6.2预读 48
2.6.3常量 49
2.6.4识别关键字和标识符 49
2.6.5词法分析器 50
2.6.6 2.6节的练习 53
2.7符号表 53
2.7.1为每个作用域设置一个符号表 54
2.7.2符号表的使用 56
2.8生成中间代码 57
2.8.1两种中间表示形式 57
2.8.2语法树的构造 58
2.8.3静态检查 61
2.8.4三地址码 62
2.8.52.8节的练习 66
2.9第2章总结 66
第3章 词法分析 68
3.1词法分析器的作用 68
3.1.1词法分析及语法分析 69
3.1.2词法单元、模式和词素 69
3.1.3词法单元的属性 70
3.1.4词法错误 71
3.1.5 3.1节的练习 71
3.2输入缓冲 71
3.2.1缓冲区对 72
3.2.2哨兵标记 72
3.3词法单元的规约 73
3.3.1串和语言 74
3.3.2语言上的运算 75
3.3.3正则表达式 75
3.3.4正则定义 77
3.3.5正则表达式的扩展 78
3.3.6 3.3节的练习 78
3.4词法单元的识别 80
3.4.1状态转换图 82
3.4.2保留字和标识符的识别 83
3.4.3完成我们的例子 84
3.4.4基于状态转换图的词法分析器的体系结构 84
3.4.5 3.4节的练习 86
3.5词法分析器生成工具Lex 89
3.5.1Lex的使用 89
3.5.2Lex程序的结构 89
3.5.3Lex中的冲突解决 91
3.5.4向前看运算符 92
3.5.5 3.5节的练习 92
3.6有穷自动机 93
3.6.1不确定的有穷自动机 93
3.6.2转换表 94
3.6.3自动机中输入字符串的接受 94
3.6.4确定的有穷自动机 95
3.6.5 3.6节的练习 96
3.7从正则表达式到自动机 96
3.7.1从NFA到DFA的转换 96
3.7.2NFA的模拟 99
3.7.3NFA模拟的效率 99
3.7.4从正则表达式构造NFA 100
3.7.5字符串处理算法的效率 103
3.7.6 3.7节的练习 105
3.8词法分析器生成工具的设计 105
3.8.1生成的词法分析器的结构 105
3.8.2基于NFA的模式匹配 106
3.8.3词法分析器使用的DFA 107
3.8.4实现向前看运算符 108
3.8.5 3.8节的练习 109
3.9基于DFA的模式匹配器的优化 109
3.9.1NFA的重要状态 109
3.9.2根据抽象语法树计算得到的函数 110
3.9.3计算nullable、firstpos及lastpos 111
3.9.4计算followpos 112
3.9.5根据正则表达式构建DFA 113
3.9.6最小化一个DFA的状态数 114
3.9.7词法分析器的状态最小化 116
3.9.8DFA模拟中的时间和空间权衡 116
3.9.9 3.9节的练习 117
3.10第3章总结 118
3.11第3章参考文献 119
第4章 语法分析 121
4.1引论 121
4.1.1语法分析器的作用 121
4.1.2代表性的文法 122
4.1.3语法错误的处理 123
4.1.4错误恢复策略 123
4.2上下文无关文法 124
4.2.1上下文无关文法的正式定义 125
4.2.2符号表示的约定 125
4.2.3推导 126
4.2.4语法分析树和推导 127
4.2.5二义性 128
4.2.6验证文法生成的语言 129
4.2.7上下文无关文法和正则表达式 130
4.2.8 4.2节的练习 130
4.3设计文法 132
4.3.1词法分析和语法分析 132
4.3.2消除二义性 133
4.3.3左递归的消除 134
4.3.4提取左公因子 135
4.3.5非上下文无关语言的构造 136
4.3.6 4.3节的练习 137
4.4自顶向下的语法分析 137
4.4.1递归下降的语法分析 139
4.4.2FIRST和FOLLOW 140
4.4.3LL（1）文法 141
4.4.4非递归的预测分析 144
4.4.5预测分析中的错误恢复 145
4.4.6 4.4节的练习 147
4.5自底向上的语法分析 148
4.5.1归约 149
4.5.2句柄剪枝 149
4.5.3移入-归约语法分析技术 150
4.5.4移入-归约语法分析中的冲突 151
4.5.5 4.5节的练习 152
4.6LR语法分析技术介绍：简单LR技术 153
4.6.1为什么使用LR语法分析器 153
4.6.2项和LR（0）自动机 154
4.6.3LR语法分析算法 158
4.6.4构造SLR语法分析表 161
4.6.5可行前缀 163
4.6.6 4.6节的练习 164
4.7更强大的LR语法分析器 165
4.7.1规范LR（1）项 165
4.7.2构造LR（1）项集 166
4.7.3规范LR（1）语法分析表 169
4.7.4构造LALR语法分析表 170
4.7.5高效构造LALR语法分析表的方法 173
4.7.6LR语法分析表的压缩 176
4.7.7 4.7节的练习 177
4.8使用二义性文法 178
4.8.1用优先级和结合性解决冲突 178
4.8.2“悬空-else”的二义性 179
4.8.3LR语法分析中的错误恢复 181
4.8.4 4.8节的练习 182
4.9语法分析器生成工具 183
4.9.1语法分析器生成工具Yacc 183
4.9.2使用带有二义性文法的Yacc规约 185
4.9.3用Lex创建Yacc的词法分析器 187
4.9.4Yacc中的错误恢复 188
4.9.5 4.9节的练习 189
4.10第4章总结 189
4.11第4章参考文献 191
第5章 语法制导的翻译 194
5.1语法制导定义 194
5.1.1继承属性和综合属性 195
5.1.2在语法分析树的结点上对SDD求值 196
5.1.3 5.1节的练习 198
5.2SDD的求值顺序 198
5.2.1依赖图 198
5.2.2属性求值的顺序 199
5.2.3S属性的定义 200
5.2.4L属性的定义 200
5.2.5具有受控副作用的语义规则 201
5.2.6 5.2节的练习 202
5.3语法制导翻译的应用 203
5.3.1抽象语法树的构造 203
5.3.2类型的结构 206
5.3.3 5.3节的练习 207
5.4语法制导的翻译方案 207
5.4.1后缀翻译方案 207
5.4.2后缀SDT的语法分析栈实现 208
5.4.3产生式内部带有语义动作的SDT 209
5.4.4从SDT中消除左递归 210
5.4.5L属性定义的SDT 212
5.4.6 5.4节的练习 216
5.5实现L属性的SDD 216
5.5.1在递归下降语法分析过程中进行翻译 217
5.5.2边扫描边生成代码 219
5.5.3L属性的SDD和LL语法分析 220
5.5.4L属性的SDD的自底向上语法分析 224
5.5.5 5.5节的练习 226
5.6第5章总结 227
5.7第5章参考文献 228
第6章 中间代码生成 229
6.1语法树的变体 230
6.1.1表达式的有向无环图 230
6.1.2构造DAG的值编码方法 231
6.1.3 6.1节的练习 232
6.2三地址代码 233
6.2.1地址和指令 233
6.2.2四元式表示 235
6.2.3三元式表示 235
6.2.4静态单赋值形式 237
6.2.5 6.2节的练习 237
6.3类型和声明 237
6.3.1类型表达式 238
6.3.2类型等价 239
6.3.3声明 239
6.3.4局部变量名的存储布局 239
6.3.5声明的序列 241
6.3.6记录和类中的字段 242
6.3.7 6.3节的练习 242
6.4表达式的翻译 243
6.4.1表达式中的运算 243
6.4.2增量翻译 244
6.4.3数组元素的寻址 245
6.4.4数组引用的翻译 246
6.4.5 6.4节的练习 247
6.5类型检查 248
6.5.1类型检查规则 248
6.5.2类型转换 249
6.5.3函数和运算符的重载 250
6.5.4类型推导和多态函数 251
6.5.5一个合一算法 254
6.5.6 6.5节的练习 256
6.6控制流 256
6.6.1布尔表达式 257
6.6.2短路代码 257
6.6.3控制流语句 257
6.6.4布尔表达式的控制流翻译 259
6.6.5避免生成冗余的goto指令 261
6.6.6布尔值和跳转代码 262
6.6.7 6.6节的练习 263
6.7回填 263
6.7.1使用回填技术的一趟式目标代码生成 263
6.7.2布尔表达式的回填 264
6.7.3控制转移语句 266
6.7.4break语句、continue语句和goto语句 267
6.7.5 6.7节的练习 268
6.8switch语句 269
6.8.1switch语句的翻译 269
6.8.2switch语句的语法制导翻译 270
6.8.3 6.8节的练习 271
6.9过程的中间代码 271
6.10第6章总结 272
6.11第6章参考文献 273
第7章 运行时刻环境 275
7.1存储组织 275
7.2空间的栈式分配 276
7.2.1活动树 277
7.2.2活动记录 279
7.2.3调用代码序列 280
7.2.4栈中的变长数据 282
7.2.5 7.2节的练习 283
7.3栈中非局部数据的访问 284
7.3.1没有嵌套过程时的数据访问 284
7.3.2和嵌套过程相关的问题 284
7.3.3一个支持嵌套过程声明的语言 285
7.3.4嵌套深度 285
7.3.5访问链 286
7.3.6处理访问链 287
7.3.7过程型参数的访问链 288
7.3.8显示表 289
7.3.9 7.3节的练习 290
7.4堆管理 291
7.4.1存储管理器 291
7.4.2一台计算机的存储层次结构 292
7.4.3程序中的局部性 293
7.4.4碎片整理 295
7.4.5人工回收请求 297
7.4.6 7.4节的练习 299
7.5垃圾回收概述 299
7.5.1垃圾回收器的设计目标 299
7.5.2可达性 301
7.5.3引用计数垃圾回收器 302
7.5.4 7.5节的练习 303
7.6基于跟踪的回收的介绍 304
7.6.1基本的标记-清扫式回收器 304
7.6.2基本抽象 305
7.6.3标记-清扫式算法的优化 306
7.6.4标记并压缩的垃圾回收器 307
7.6.5拷贝回收器 309
7.6.6开销的比较 311
7.6.7 7.6节的练习 311
7.7短停顿垃圾回收 311
7.7.1增量式垃圾回收 312
7.7.2增量式可达性分析 313
7.7.3部分回收概述 314
7.7.4世代垃圾回收 315
7.7.5列车算法 316
7.7.6 7.7节的练习 318
7.8垃圾回收中的高级论题 319
7.8.1并行和并发垃圾回收 319
7.8.2部分对象重新定位 321
7.8.3类型不安全的语言的保守垃圾回收 321
7.8.4弱引用 322
7.8.5 7.8节的练习 322
7.9第7章总结 322
7.10第7章参考文献 324
第8章 代码生成 326
8.1代码生成器设计中的问题 327
8.1.1代码生成器的输入 327
8.1.2目标程序 327
8.1.3指令选择 328
8.1.4寄存器分配 329
8.1.5求值顺序 330
8.2目标语言 330
8.2.1一个简单的目标机模型 330
8.2.2程序和指令的代价 332
8.2.3 8.2节的练习 332
8.3目标代码中的地址 334
8.3.1静态分配 334
8.3.2栈分配 335
8.3.3名字的运行时刻地址 337
8.3.4 8.3节的练习 337
8.4基本块和流图 338
8.4.1基本块 339
8.4.2后续使用信息 340
8.4.3流图 340
8.4.4流图的表示方式 341
8.4.5循环 341
8.4.6 8.4节的练习 342
8.5基本块的优化 342
8.5.1基本块的DAG表示 342
8.5.2寻找局部公共子表达式 343
8.5.3消除死代码 344
8.5.4代数恒等式的使用 344
8.5.5数组引用的表示 345
8.5.6指针赋值和过程调用 346
8.5.7从DAG到基本块的重组 347
8.5.8 8.5节的练习 348
8.6一个简单的代码生成器 348
8.6.1寄存器和地址描述符 349
8.6.2代码生成算法 349
8.6.3函数getReg的设计 352
8.6.4 8.6节的练习 352
8.7窥孔优化 353
8.7.1消除冗余的加载和保存指令 353
8.7.2消除不可达代码 354
8.7.3控制流优化 354
8.7.4代数化简和强度消减 355
8.7.5使用机器特有的指令 355
8.7.6 8.7节的练习 355
8.8寄存器分配和指派 355
8.8.1全局寄存器分配 356
8.8.2使用计数 356
8.8.3外层循环的寄存器指派 358
8.8.4通过图着色方法进行寄存器分配 358
8.8.5 8.8节的练习 359
8.9通过树重写来选择指令 359
8.9.1树翻译方案 359
8.9.2通过覆盖一个输入树来生成代码 361
8.9.3通过扫描进行模式匹配 362
8.9.4用于语义检查的例程 363
8.9.5通用的树匹配方法 363
8.9.6 8.9节的练习 364
8.10表达式的优化代码的生成 365
8.10.1Ershov数 365
8.10.2从带标号的表达式树生成代码 365
8.10.3寄存器数量不足时的表达式求值 366
8.10.4 8.10节的练习 368
8.11使用动态规划的代码生成 368
8.11.1连续求值 368
8.11.2动态规划的算法 369
8.11.3 8.11节的练习 371
8.12第8章总结 371
8.13第8章参考文献 372
第9章 机器无关优化 374
9.1优化的主要来源 374
9.1.1冗余的原因 374
9.1.2一个贯穿本章的例子：快速排序 375
9.1.3保持语义不变的转换 377
9.1.4全局公共子表达式 377
9.1.5复制传播 378
9.1.6死代码消除 379
9.1.7代码移动 379
9.1.8归纳变量和强度消减 380
9.1.9 9.1节的练习 381
9.2数据流分析简介 382
9.2.1数据流抽象 382
9.2.2数据流分析模式 383
9.2.3基本块上的数据流模式 384
9.2.4到达定值 385
9.2.5活跃变量分析 390
9.2.6可用表达式 391
9.2.7小结 393
9.2.8 9.2节的练习 394
9.3数据流分析基础 395
9.3.1半格 396
9.3.2传递函数 399
9.3.3通用框架的迭代算法 400
9.3.4数据流解的含义 402
9.3.5 9.3节的练习 404
9.4常量传播 404
9.4.1常量传播框架的数据流值 404
9.4.2常量传播框架的交汇运算 405
9.4.3常量传播框架的传递函数 405
9.4.4常量传递框架的单调性 406
9.4.5常量传播框架的不可分配性 406
9.4.6对算法结果的解释 407
9.4.7 9.4节的练习 408
9.5部分冗余消除 408
9.5.1冗余的来源 408
9.5.2可能消除所有冗余吗 410
9.5.3懒惰代码移动问题 411
9.5.4表达式的预期执行 412
9.5.5懒惰代码移动算法 413
9.5.6 9.5节的练习 418
9.6流图中的循环 419
9.6.1支配结点 419
9.6.2深度优先排序 421
9.6.3深度优先生成树中的边 423
9.6.4回边和可归约性 423
9.6.5流图的深度 424
9.6.6自然循环 424
9.6.7迭代数据流算法的收敛速度 425
9.6.8 9.6节的练习 427
9.7基于区域的分析 428
9.7.1区域 429
9.7.2可归约流图的区域层次结构 429
9.7.3基于区域的分析技术概述 431
9.7.4有关传递函数的必要假设 431
9.7.5一个基于区域的分析算法 433
9.7.6处理不可归约流图 436
9.7.7 9.7节的练习 437
9.8符号分析 437
9.8.1参考变量的仿射表达式 438
9.8.2数据流问题的公式化 440
9.8.3基于区域的符号化分析 442
9.8.4 9.8节的练习 445
9.9第9章总结 445
9.10第9章参考文献 448
第10章 指令级并行性 450
10.1处理器体系结构 450
10.1.1指令流水线和分支延时 451
10.1.2流水线执行 451
10.1.3多指令发送 451
10.2代码调度约束 452
10.2.1数据依赖 452
10.2.2寻找内存访问之间的依赖关系 453
10.2.3寄存器使用和并行性之间的折衷 454
10.2.4寄存器分配阶段和代码调度阶段之间的顺序 455
10.2.5控制依赖 455
10.2.6对投机执行的支持 456
10.2.7一个基本的机器模型 457
10.2.8 10.2节的练习 458
10.3基本块调度 459
10.3.1数据依赖图 459
10.3.2基本块的列表调度方法 460
10.3.3带优先级的拓扑排序 461
10.3.4 10.3节的练习 461
10.4全局代码调度 462
10.4.1基本的代码移动 462
10.4.2向上的代码移动 463
10.4.3向下的代码移动 464
10.4.4更新数据依赖关系 465
10.4.5全局调度算法 465
10.4.6高级代码移动技术 467
10.4.7和动态调度器的交互 468
10.4.8 10.4节的练习 468
10.5软件流水线化 468
10.5.1引言 468
10.5.2循环的软件流水线化 470
10.5.3寄存器分配和代码生成 471
10.5.4Do-Across循环 472
10.5.5软件流水线化的目标和约束 472
10.5.6一个软件流水线化算法 474
10.5.7对无环数据依赖图进行调度 475
10.5.8对有环数据依赖图进行调度 476
10.5.9对流水线化算法的改进 480
10.5.10模数变量扩展 480
10.5.11条件语句 482
10.5.12软件流水线化的硬件支持 483
10.5.13 10.5节的练习 483
10.6第10章总结 484
10.7第10章参考文献 485
第11章 并行性和局部性优化 487
11.1基本概念 488
11.1.1多处理器 488
11.1.2应用中的并行性 490
11.1.3循环层次上的并行性 491
11.1.4数据局部性 492
11.1.5仿射变换理论概述 493
11.2矩阵乘法：一个深入的例子 495
11.2.1矩阵相乘算法 495
11.2.2优化 497
11.2.3高速缓存干扰 499
11.2.4 11.2节的练习 499
11.3迭代空间 499
11.3.1从循环嵌套结构中构建迭代空间 499
11.3.2循环嵌套结构的执行顺序 501
11.3.3不等式组的矩阵表示方法 501
11.3.4混合使用符号常量 502
11.3.5控制执行的顺序 502
11.3.6坐标轴的变换 505
11.3.7 11.3节的练习 506
11.4仿射的数组下标 507
11.4.1仿射访问 507
11.4.2实践中的仿射访问和非仿射访问 508
11.4.3 11.4节的练习 508
11.5数据复用 509
11.5.1数据复用的类型 509
11.5.2自复用 510
11.5.3自空间复用 513
11.5.4组复用 514
11.5.5 11.5节的练习 515
11.6数组数据依赖关系分析 516
11.6.1数组访问的数据依赖关系的定义 517
11.6.2整数线性规划 518
11.6.3GCD测试 518
11.6.4解决整数线性规划的启发式规则 520
11.6.5解决一般性的整数线性规划问题 522
11.6.6小结 523
11.6.7 11.6节的练习 523
11.7寻找无同步的并行性 524
11.7.1一个介绍性的例子 525
11.7.2仿射空间分划 526
11.7.3空间分划约束 527
11.7.4求解空间分划约束 529
11.7.5一个简单的代码生成算法 531
11.7.6消除空迭代 533
11.7.7从最内层循环中消除条件测试 535
11.7.8源代码转换 537
11.7.9 11.7节的练习 539
11.8并行循环之间的同步 541
11.8.1固定多个同步运算 541
11.8.2程序依赖图 542
11.8.3层次结构化的时间 543
11.8.4并行化算法 544
11.8.5 11.8节的练习 545
11.9流水线化技术 545
11.9.1什么是流水线化 545
11.9.2连续过松弛方法：一个例子 546
11.9.3完全可交换循环 547
11.9.4把完全可交换循环流水线化 548
11.9.5一般性的理论 549
11.9.6时间分划约束 549
11.9.7用Farkas引理求解时间分划约束 552
11.9.8代码转换 554
11.9.9具有最小同步量的并行性 557
11.9.10 11.9节的练习 559
11.10局部性优化 560
11.10.1计算结果数据的时间局部性 560
11.10.2数组收缩 560
11.10.3分划单元的交织 562
11.10.4合成 565
11.10.5 11.10节的练习 566
11.11仿射转换的其他用途 566
11.11.1分布式内存计算机 566
11.11.2多指令发送处理器 567
11.11.3向量和SIMD指令 567
11.11.4数据预取 567
11.12第11章总结 568
11.13第11章参考文献 570
第12章 过程间分析 573
12.1基本概念 573
12.1.1调用图 573
12.1.2上下文相关 574
12.1.3调用串 576
12.1.4基于克隆的上下文相关分析 577
12.1.5基于摘要的上下文相关分析 578
12.1.6 12.1节的练习 579
12.2为什么需要过程间分析 580
12.2.1虚方法调用 580
12.2.2指针别名分析 581
12.2.3并行化 581
12.2.4软件错误和漏洞的检测 581
12.2.5SQL注入 581
12.2.6缓冲区溢出 582
12.3数据流的一种逻辑表示方式 583
12.3.1Datalog简介 583
12.3.2Datalog规则 584
12.3.3内涵断言和外延断言 585
12.3.4Datalog程序的执行 587
12.3.5Datalog程序的增量计算 588
12.3.6有问题的Datalog规则 589
12.3.7 12.3节的练习 590
12.4一个简单的指针分析算法 591
12.4.1为什么指针分析有难度 591
12.4.2一个指针和引用的模型 592
12.4.3控制流无关性 592
12.4.4在Datalog中的表示方法 593
12.4.5使用类型信息 594
12.4.6 12.4节的练习 595
12.5上下文无关的过程间分析 595
12.5.1一个方法调用的效果 595
12.5.2在Datalog中发现调用图 596
12.5.3动态加载和反射 597
12.5.4 12.5节的练习 597
12.6上下文相关指针分析 598
12.6.1上下文和调用串 598
12.6.2在Datalog规则中加入上下文信息 600
12.6.3关于相关性的更多讨论 600
12.6.4 12.6节的练习 600
12.7使用BDD的Datalog的实现 601
12.7.1分决策图 601
12.7.2对BDD的转换 602
12.7.3用BDD表示关系 603
12.7.4用BDD操作实现关系运算 603
12.7.5在指针指向分析中使用BDD 605
12.7.6 12.7节的练习 605
12.8第12章总结 606
12.9第12章参考文献 607
附录A 一个完整的编译器前端 611
附录B 寻找线性独立解 630