编译器设计（第3版）

·2024年TAA教材卓越奖获奖作品

《编译器设计(第3版)》(“壁画书”)是一本架起编译理论与工程实践桥梁的经典教材。与侧重原理的“龙书”不同，本书更加关注现代编译器的实际构建过程，不仅系统涵盖了现代编译器的前端、中间部分及后端，还深入讲解了优化与代码生成部分。书中用清晰的伪代码和丰富的真实案例，带你深入理解代码优化、指令选择、寄存器分配等关键技术。

·特色与优势

1.以“设计决策”为主线，剖析不同方案的权衡，培养工程判断力

2.率先深入讲解即时编译与运行时优化，紧跟工业界前沿

3.行文通俗、示例翔实，公认更易入门

·为什么值得读

它不是一本枯燥的理论词典，而是能让你上手、理解工业级编译器工作逻辑的指南。翻开它，你将获得从算法到实现的完整工程视野——这正是写出高效代码、深入系统底层的关键一步。

本书是编译器设计领域的经典著作，是构建现代优化编译器的优秀指南，其中汲取了编译器构建领域大量的经验，以帮助学生掌握整体设计思路，同时引导学生了解构建有效的优化编译器所必需的许多重要而微妙的细节。本书主要从以下四部分详解了编译器的设计过程：第一部分涉及编译器前端设计以及自动构造前端工具的算法；第二部分不仅探讨了如何将源代码映射到编译器的中间表示，还研究了前端可以为优化器和后端所生成的代码类型；第三部分介绍了代码优化；第四部分重点介绍了编译器后端的主要算法，包括指令选择、指令调度和寄存器分配。第3版涵盖了编译器技术的最新发展，新增章节侧重于语义加工、对命名和寻址的运行时支持，以及表达式、赋值和控制结构的代码形式。

第 1章 编译概述 1

1.1 引言 1

1.2 编译器结构 5

1.3 翻译过程概述 8

1.3.1 前端 9

1.3.2 优化器 11

1.3.3 后端 12

1.4 工程实践 17

1.5 总结与展望 18

本章注释 18

练习题 19

第 2章 扫描器 20

2.1 引言 20

2.2 识别单词 22

2.2.1 识别器的形式化表述 24

2.2.2 识别更复杂的单词 25

2.3 正则表达式 27

2.3.1 形式化表示法 28

2.3.2 正则表达式样例 29

2.3.3 正则表达式的闭包性质 32

2.4 从正则表达式到扫描器 34

2.4.1 非确定有限自动机 35

2.4.2 从正则表达式到NFA：Thompson构造法 37

2.4.3 从NFA到DFA：子集构造法 38

2.4.4 最小化DFA 41

2.4.5 将DFA用作扫描器 45

2.5 实现扫描器 49

2.5.1 表驱动扫描器 49

2.5.2 直接编码扫描器 52

2.5.3 手动编写扫描器 54

2.5.4 实践中的问题 54

2.6 进阶内容 58

2.6.1 从DFA到正则表达式 58

2.6.2 无闭包正则表达式 59

2.6.3 DFA最小化的一种替代算法 60

2.7 总结与展望 62

本章注释 63

练习题 63

第3章 解析器 66

3.1 引言 66

3.2 语法的表示 67

3.2.1 为什么不使用正则表达式 68

3.2.2 上下文无关文法 69

3.2.3 更复杂的例子 71

3.2.4 将含义嵌入结构中 74

3.2.5 找出输入串的推导过程 76

3.3 自顶向下解析 77

3.3.1 文法转换 78

3.3.2 自顶向下的递归下降解析器 88

3.3.3 表驱动LL(1) 解析器  89

3.4 自底向上解析 93

3.4.1 LR(1) 解析算法 95

3.4.2 建立LR(1) 解析表 100

3.4.3 表构造中的错误 108

3.5 实践中的问题 111

3.5.1 错误恢复 111

3.5.2 一元运算符 112

3.5.3 上下文相关二义性的处理 113

3.6 进阶内容 114

3.6.1 优化文法 115

3.6.2 缩小LR(1) 解析表的体积 116

3.7 总结与展望 120

本章注释 121

练习题 121

第4章 中间表示 124

4.1 引言 124

4.2 IR的分类体系 126

4.3 图IR 129

4.3.1 与语法相关的树 129

4.3.2 图 132

4.4 线性IR 136

4.4.1 栈机器代码 137

4.4.2 三地址代码 138

4.4.3 线性代码的表示  139

4.4.4 从线性代码构造CFG 140

4.5 符号表 143

4.5.1 名称解析 144

4.5.2 表的实现 146

4.6 命名空间 148

4.6.1 IR中的命名空间 148

4.6.2 静态单赋值形式 151

4.7 内存中值的放置 153

4.7.1 内存模型 154

4.7.2 在寄存器中保留值 156

4.7.3 将值分配到数据区 156

4.8 总结与展望 159

本章注释 159

练习题 160

第5章 语法驱动翻译 163

5.1 引言 163

5.2 背景 165

5.3 语法驱动翻译概述 166

5.3.1 第 一个例子 166

5.3.2 翻译表达式 168

5.3.3 控制流语句的翻译 173

5.4 建立命名环境的模型 176

5.4.1 词法层级 177

5.4.2 继承层级 181

5.4.3 可见性 184

5.4.4 执行编译时名称解析 185

5.5 类型信息 186

5.5.1 类型在翻译中的作用 186

5.5.2 类型系统的组成部分 188

5.5.3 表达式的类型推导 191

5.6 存储布局 194

5.6.1 存储类和数据区 195

5.6.2 虚拟地址空间中的布局 196

5.6.3 存储分配 198

5.6.4 在翻译过程中安排存储分配  202

5.6.5 对齐限制和填充 202

5.7 进阶内容 204

5.7.1 文法结构与结合性 204

5.7.2 类型推导中的难题 206

5.7.3 相对偏移与缓存性能 207

5.8 总结与展望 208

本章注释 209

练习题 209

第6章 过程的实现 212

6.1 引言 212

6.2 背景 215

6.3 命名的运行时支持 217

6.3.1 类Algol语言的运行时支持 218

6.3.2 面向对象语言的运行时支持 222

6.4 过程间值传递 226

6.4.1 参数传递 227

6.4.2 返回值 229

6.4.3 为非局部变量建立可寻址性 230

6.5 标准化链接 234

6.6 进阶内容 238

6.6.1 显式堆管理 238

6.6.2 隐式释放 241

6.7 总结与展望 244

本章注释 245

练习题  245

第7章 代码形式 250

7.1 引言 250

7.2 算术运算符 252

7.2.1 表达式中的函数调用 254

7.2.2 混合类型表达式 254

7.2.3 减少对寄存器的需求 256

7.3 值的访问方法 258

7.3.1 标量变量的访问方法 258

7.3.2 聚合对象的访问方法 260

7.3.3 范围检查 266

7.4 布尔运算符和关系运算符 267

7.4.1 关系表达式的硬件支持 268

7.4.2 硬件支持的变化形式 270

7.5 控制流结构 272

7.5.1 条件执行 273

7.5.2 循环与迭代 274

7.5.3 case语句 277

7.6 字符串的处理 281

7.6.1 字符串的长度 281

7.6.2 字符串的赋值 281

7.6.3 字符串的连接 282

7.6.4 字符串操作的优化 282

7.7 过程调用 283

7.7.1 实参求值 284

7.7.2 保存与恢复寄存器 285

7.8 总结与展望 286

本章注释 287

练习题 287

第8章 优化简介 291

8.1 引言 291

8.2 背景 292

8.2.1 例子 293

8.2.2 对优化的考虑 297

8.2.3 优化的机会 299

8.3 优化的范围 300

8.4 局部优化 303

8.4.1 局部值编号 303

8.4.2 树高平衡 309

8.5 区域优化 316

8.5.1 超局部值编号 317

8.5.2 循环展开 319

8.6 全局优化 322

8.6.1 使用活跃集合查找未初始化变量 322

8.6.2 全局代码置放 327

8.7 过程间优化 332

8.7.1 内联替换 333

8.7.2 过程置放 336

8.7.3 针对过程间优化的编译器组织结构 340

8.8 总结与展望 341

本章注释 342

练习题 343

第9章 数据流分析 347

9.1 引言 347

9.2 迭代数据流分析 349

9.2.1 支配 349

9.2.2 活跃变量分析 353

9.2.3 数据流分析的局限 357

9.2.4 其他数据流问题 359

9.3 SSA 形式 363

9.3.1 构建SSA的简单方法 365

9.3.2 支配边界 366

9.3.3 放置 函数 369

9.3.4 重命名 372

9.3.5 从SSA形式转出为常规形式 377

9.3.6 使用SSA形式 383

9.4 过程间分析 387

9.4.1 构造调用图 387

9.4.2 过程间常量传播 389

9.5 进阶内容 393

9.5.1 结构化的数据流分析和可归约性 393

9.5.2 加速支配计算所用迭代框架的算法 396

9.6 总结与展望 398

本章注释 398

练习题 399

第 10章 标量优化 402

10.1 引言 402

10.2 死代码消除 405

10.2.1 消除无用代码 406

10.2.2 消除无用控制流 408

10.2.3 消除不可达代码 410

10.3 代码移动 411

10.3.1 惰性代码移动 412

10.3.2 代码提升 419

10.4 特化 420

10.4.1 尾调用优化 420

10.4.2 叶调用优化 421

10.4.3 参数提升 422

10.5 冗余消除 423

10.5.1 值相同与名称相同 423

10.5.2 基于支配者的值编号 424

10.6 为其他变换创造机会 427

10.6.1 超级块克隆 427

10.6.2 过程克隆 429

10.6.3 循环判断外提 429

10.6.4 重命名 430

10.7 进阶内容 431

10.7.1 组合优化 431

10.7.2 强度削弱 435

10.7.3 优化序列的选择 443

10.8 总结与展望 444

本章注释 445

练习题 446

第 11章 指令选择 448

11.1 引言 448

11.2 背景 451

11.2.1 ISA设计对指令选择的影响 452

11.2.2 一个示意性的例子 454

11.2.3 特定的匹配 456

11.3 基于窥孔优化的指令选择 457

11.3.1 窥孔优化 457

11.3.2 简化器 459

11.3.3 匹配器 462

11.4 基于树模式匹配的指令选择 463

11.4.1 树的表示方法 464

11.4.2 重写规则 464

11.4.3 计算覆盖方案 468

11.4.4 工具 474

11.5 进阶内容 476

11.5.1 学习窥孔模式 476

11.5.2 生成指令序列 477

11.6 总结与展望 477

本章注释 478

练习题 479

第 12章 指令调度 480

12.1 引言 480

12.2 背景 482

12.2.1 影响性能的体系结构特性 483

12.2.2 指令调度问题 485

12.3 局部调度 488

12.3.1 算法 489

12.3.2 重命名 489

12.3.3 构建依赖图 491

12.3.4 计算优先级 493

12.3.5 列表调度 493

12.3.6 前向列表调度与后向列表调度 496

12.4 区域调度 499

12.4.1 超局部调度 499

12.4.2 踪迹调度 500

12.4.3 超级块克隆 502

12.5 进阶内容 504

12.5.1 软件流水线背后的策略 504

12.5.2 软件流水线化算法 507

12.5.3 最后一个例子 511

12.6 总结与展望 512

本章注释 512

练习题 513

第 13章 寄存器分配 516

13.1 引言 516

13.2 背景 518

13.2.1 适于寄存器分配的命名空间：活跃范围 518

13.2.2 干涉 520

13.2.3 溢出代码 522

13.2.4 寄存器类别 523

13.3 局部寄存器分配 525

13.3.1 局部分配器中的重命名 527

13.3.2 分配和指派 528

13.4 基于图着色的全局分配 532

13.4.1 寻找全局LR 534

13.4.2 构建干涉图 535

13.4.3 合并复制操作 537

13.4.4 估算全局溢出开销 538

13.4.5 对图进行着色 539

13.4.6 插入溢出和恢复代码 542

13.4.7 处理有重叠的寄存器类别 542

13.5 进阶内容 546

13.5.1 保守的合并算法 546

13.5.2 改进的溢出策略 547

13.5.3 其他形式的LR 549

13.6 总结与展望 552

本章注释 552

练习题 553

第 14章 运行时优化 556

14.1 引言 556

14.2 背景 559

14.2.1 执行模型 560

14.2.2 编译触发程序 562

14.2.3 优化的粒度 563

14.2.4 改进的来源 564

14.2.5 构建运行时优化器 567

14.3 热踪迹优化 567

14.3.1 执行流程 568

14.3.2 踪迹的链接 572

14.4 热方法优化 574

14.4.1 混合模式环境中的热方法 575

14.4.2 本地代码环境中的热方法 579

14.5 进阶内容 582

14.5.1 优化级别 582

14.5.2 栈上替换 583

14.5.3 代码缓存管理 584

14.5.4 管理对源代码的更改 585

14.6 总结与展望 587

本章注释 587

练习题 588

附录A ILOC 590

附录B 数据结构  601

参考文献 619