现代编译原理C语言描述PDF电子书下载

第一部分 编译基本原理 1

第1章 绪论 1

1.1 模块与接口 1

1.2 工具和软件 3

1.3 树语言的数据结构 3

程序设计：直线式程序解释器 7

推荐阅读 9

习题 9

2.1 词法单词 10

第2章 词法分析 10

2.2 正则表达式 11

2.3 有限自动机 13

2.4 非确定有限自动机 15

2.4.1 将正则表达式转换为NFA 16

2.4.2 将NFA转换为DFA 18

2.5 Lex：词法分析器的生成器 20

程序设计：词法分析 22

推荐阅读 23

习题 23

第3章 语法分析 27

3.1 上下文无关文法 28

3.1.1 推导 29

3.1.2 语法分析树 29

3.1.3 二义性文法 30

3.1.4 文件结束符 31

3.2 预测分析 32

3.2.1 FIRST集合和FOLLOW集合 33

3.2.2 构造一个预测分析器 35

3.2.3 消除左递归 36

3.2.5 错误恢复 37

3.2.4 提取左因子 37

3.3 LR分析 39

3.3.1 LR分析引擎 40

3.3.2 LR（0）分析器生成器 41

3.3.3 SLR分析器的生成 44

3.3.4 LR（1）项和LR（1）分析表 45

3.3.5 LALR（1）分析表 46

3.3.6 各类文法的层次 47

3.3.7 二义性文法的LR分析 47

3.4 使用分析器的生成器 48

3.4.1 冲突 49

3.4.2 优先级指导 50

3.4.3 语法和语义 53

3.5 错误恢复 54

3.5.1 用error符号恢复 54

3.5.2 全局错误修复 55

程序设计：语法分析 57

推荐阅读 58

习题 58

4.1.1 递归下降 62

4.1.2 Yacc生成的分析器 62

4.1 语义动作 62

第4章 抽象语法 62

4.1.3 语义动作的解释器 64

4.2 抽象语法分析树 65

4.2.1 位置 67

4.2.2 Tiger的抽象语法 68

程序设计：抽象语法 71

推荐阅读 71

习题 72

5.1 符号表 73

第5章 语义分析 73

5.1.1 多个符号表 74

5.1.2 高效的命令式风格符号表 75

5.1.3 高效的函数式符号表 76

5.1.4 Tiger编译器的符号 77

5.1.5 函数式风格的符号表 79

5.2 Tiger编译器的绑定 79

5.3 表达式的类型检查 82

5.4 声明的类型检查 84

5.4.1 变量声明 84

5.4.3 函数声明 85

5.4.2 类型声明 85

5.4.4 递归声明 86

程序设计：类型检查 87

习题 87

第6章 活动记录 89

6.1 栈帧 90

6.1.1 帧指针 91

6.1.2 寄存器 92

6.1.3 参数传递 92

6.1.5 栈帧内的变量 94

6.1.4 返回地址 94

6.1.6 静态链 95

6.2 Tiger编译器的栈帧 96

6.2.1 栈帧描述的表示 98

6.2.2 局部变量 98

6.2.3 计算逃逸变量 99

6.2.4 临时变量和标号 100

6.2.5 两层抽象 100

6.2.6 管理静态链 102

6.2.7 追踪层次信息 102

习题 103

程序设计：栈帧 103

推荐阅读 103

第7章 翻译成中间代码 106

7.1 中间表示树 106

7.2 翻译为树中间语言 108

7.2.1 表达式的种类 108

7.2.2 简单变量 111

7.2.3 追随静态链 112

7.2.4 数组变量 113

7.2.6 下标和域选择 114

7.2.5 结构化的左值 114

7.2.7 关于安全性的劝告 115

7.2.8 算术操作 116

7.2.9 条件表达式 116

7.2.10 字符串 117

7.2.11 记录和数组的创建 118

7.2.12 while循环 119

7.2.13 for循环 119

7.3.2 函数定义 120

7.3.1 变量定义 120

7.3 声明 120

7.2.14 函数调用 120

7.3.3 片段 121

程序设计：翻译成树 122

习题 123

第8章 基本块和轨迹 125

8.1 规范树 126

8.1.1 ESEQ的转换 126

8.1.2 一般重写规则 126

8.1.3 将CALL移到顶层 130

8.2.1 基本块 131

8.1.4 线性语句表 131

8.2 处理条件分支 131

8.2.2 轨迹 132

8.2.3 完善 133

8.2.4 最优轨迹 133

推荐阅读 134

习题 134

第9章 指令选择 136

9.1 指令选择算法 138

9.1.1 Maximal Munch算法 138

9.1.2 动态规划 140

9.1.3 树文法 141

9.1.4 快速匹配 143

9.1.5 覆盖算法的效率 143

9.2 CISC机器 144

9.3 Tiger编译器的指令选择 146

9.3.1 抽象的汇编语言指令 146

9.3.2 生成汇编指令 148

9.3.3 过程调用 151

9.3.4 无帧指针的情形 151

程序设计：指令选择 152

推荐阅读 153

习题 154

第10章 活跃分析 155

10.1 数据流方程的解 156

10.1.1 活跃性计算 156

10.1.2 集合的表示 158

10.1.3 时间复杂度 158

10.1.4 最小不动点 159

10.1.5 静态活跃性与动态活跃性 160

10.1.6 冲突图 161

10.2.1 图 162

10.2 Tiger编译器的活跃分析 162

10.2.2 控制流图 163

10.2.3 活跃分析 164

程序设计：构造流图 164

程序设计：活跃分析模块 165

习题 165

第11章 寄存器分配 166

11.1 通过简化进行着色 166

11.2 合并 168

11.3.1 机器寄存器的临时副本 171

11.3 预着色的结点 171

11.3.2 调用者保护的寄存器和被调用者保护的寄存器 172

11.3.3 含预着色结点的例子 172

11.4 图着色的实现 175

11.4.1 传送指令工作表的管理 176

11.4.2 数据结构 176

11.4.3 程序代码 177

11.5 针对树的寄存器分配 181

程序设计：图着色 184

推荐阅读 185

习题 185

第12章 整合为一体 188

程序设计：过程入口／出口 189

程序设计：创建一个可运行的编译器 191

第二部分 高级主题 193

第13章 垃圾收集 193

13.1 标记－清扫式收集 194

13.2 引用计数 197

13.3 复制式收集 198

13.4 分代收集 201

13.5 增量式收集 203

13.7.1 快速分配 205

13.6 Baker算法 205

13.7 编译器接口 205

13.7.2 数据布局的描述 206

13.7.3 导出指针 207

程序设计：描述字 208

程序设计：垃圾收集 208

推荐阅读 208

习题 210

第14章 面向对象的语言 211

14.1 类 211

14.2 数据域的单继承性 213

14.3 多继承 214

14.4 测试类成员关系 216

14.5 私有域和私有方法 218

14.6 无类语言 219

14.7 面向对象程序的优化 219

程序设计：OBJECT-Tiger 220

推荐阅读 220

习题 221

15.1 一个简单的函数式语言 222

第15章 函数式程序设计语言 222

15.2 闭包 224

15.3 不变的变量 225

15.3.1 基于延续的I/O 226

15.3.2 语言上的变化 227

15.3.3 纯函数式语言的优化 228

15.4 内联扩展 229

15.5 闭包变换 233

15.6 高效的尾递归 235

15.7 懒惰计算 236

15.7.1 传名调用计算 237

15.7.2 按需调用 238

15.7.3 懒惰程序的计算 239

15.7.4 懒惰函数式程序的优化 239

15.7.5 严格性分析 241

推荐阅读 243

程序设计：编译函数式语言 244

习题 244

第16章 多态类型 246

16.1 参数多态性 246

16.1.1 显式带类型的多态语言 247

16.1.2 多态类型的检查 248

16.2 类型推论 253

16.2.1 一个隐式类型的多态语言 254

16.2.2 类型推论算法 255

16.2.3 递归的数据类型 257

16.2.4 Hindley-Milner类型的能力 259

16.3 多态变量的表示 259

16.3.1 多态函数的扩展 260

16.3.2 完全的装箱转换 261

16.3.3 基于强制的表示分析 262

16.3.4 将类型作为运行时参数传递 264

16.4 静态重载的解决方法 265

推荐阅读 266

习题 266

第17章 数据流分析 269

17.1 流分析使用的中间表示 270

17.2 各种数据流分析 271

17.2.1 到达定值 271

17.2.2 可用表达式 273

17.3.1 公共子表达式删除 274

17.3 使用数据流分析结果的几种转换 274

17.2.3 到达表达式 274

17.2.4 活跃分析 274

17.3.2 常数传播 275

17.3.3 复写传播 275

17.3.4 死代码删除 275

17.4 加快数据流分析 276

17.4.1 位向量 276

17.4.2 基本块 276

17.4.3 结点排序 277

17.4.4 使用－定值链和定值－使用链 277

17.4.6 增量式数据流分析 278

17.4.5 工作表算法 278

17.5 别名分析 281

17.5.1 基于类型的别名分析 282

17.5.2 基于流的别名分析 283

17.5.3 使用可能别名信息 284

17.5.4 严格的纯函数式语言中的别名分析 285

推荐阅读 285

习题 285

第18章 循环优化 287

18.1.2 直接必经结点 289

18.1 必经结点 289

18.1.1 寻找必经结点的算法 289

18.1.3 循环 290

18.1.4 循环前置结点 291

18.2 循环不变量计算 292

18.3 归纳变量 293

18.3.1 发现归纳变量 294

18.3.2 强度削弱 295

18.3.4 重写比较 296

18.3.3 删除 296

18.4 数组边界检查 297

18.5 循环展开 300

推荐阅读 301

习题 301

第19章 静态单赋值形式 303

19.1 转化为SSA形式 305

19.1.1 插入φ函数的标准 306

19.1.2 必经结点边界 306

19.1.3 插入φ函数 308

19.1.4 变量重命名 309

19.1.5 边分割 310

19.2 必经结点树的高效计算 310

19.2.1 深度优先生成树 310

19.2.2 半必经结点 311

19.2.3 Lengauer-Tarjan算法 312

19.3 使用SSA的优化算法 315

19.3.1 死代码删除 315

19.3.2 简单的常数传播 316

19.3.3 条件常数传播 317

19.3.4 保持必经结点性质 319

19.4 数组、指针和存储器 320

19.5 控制依赖图 321

19.6 从SSA形式转变回来 323

19.7 函数式中间形式 324

推荐阅读 327

习题 328

第20章 流水和调度 331

20.1 没有资源约束时的循环调度 332

20.2 有资源约束的循环流水 336

20.2.1 模调度 337

20.2.2 寻找最小的启动间距 338

20.2.3 其他控制流 340

20.2.4 编译器应该调度指令吗 340

20.3 分支预测 341

20.3.1 静态分支预测 342

20.3.2 编译器应该预测分支吗 342

推荐阅读 343

习题 343

21.1 cache的组织结构 346

第21章 存储层次 346

21.2 cache块对齐 349

21.3 预取 350

21.4 循环交换 354

21.5 分块 355

21.6 垃圾收集和存储层次 357

推荐阅读 358

习题 358

附录 Tiger语言参考手册 360

参考文献 368

索引 376