编译器工程PDF电子书下载

专家指导委员会对本书的赞誉 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