现代编译原理（C语言描述）

第一部分　编译基本原理
第1章　绪论　1
1.1　模块与接口　1
1.2　工具和软件　3
1.3　树语言的数据结构　3
程序设计：直线式程序解释器　7
推荐阅读　9
习题　9
第2章　词法分析　10
2.1　词法单词　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.4　提取左因子　37
3.2.5　错误恢复　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章　抽象语法　62
4.1　语义动作　62
4.1.1　递归下降　62
4.1.2　Yacc生成的分析器　62
4.1.3　语义动作的解释器　64
4.2　抽象语法分析树　65
4.2.1　位置　67
4.2.2　Tiger的抽象语法　68
程序设计：抽象语法　71
推荐阅读　71
习题　72
第5章　语义分析　73
5.1　符号表　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.2　类型声明　85
5.4.3　函数声明　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.4　返回地址　94
6.1.5　栈帧内的变量　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.5　结构化的左值　114
7.2.6　下标和域选择　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.2.14　函数调用　120
7.3　声明　120
7.3.1　变量定义　120
7.3.2　函数定义　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.1.4　线性语句表　131
8.2　处理条件分支　131
8.2.1　基本块　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　Tiger编译器的活跃分析　162
10.2.1　图　162
10.2.2　控制流图　163
10.2.3　活跃分析　164
程序设计：构造流图　164
程序设计：活跃分析模块　165
习题　165
第11章　寄存器分配　166
11.1　通过简化进行着色　166
11.2　合并　168
11.3　预着色的结点　171
11.3.1　机器寄存器的临时副本　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
第二部分高级主题
第13章　垃圾收集　193
13.1　标记-清扫式收集　194
13.2　引用计数　197
13.3　复制式收集　198
13.4　分代收集　201
13.5　增量式收集　203
13.6　Baker算法　205
13.7　编译器接口　205
13.7.1　快速分配　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章　函数式程序设计语言　222
15.1　一个简单的函数式语言　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.2.3　到达表达式　274
17.2.4　活跃分析　274
17.3　使用数据流分析结果的几种转换　274
17.3.1　公共子表达式删除　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.5　工作表算法　278
17.4.6　增量式数据流分析　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　必经结点　289
18.1.1　寻找必经结点的算法　289
18.1.2　直接必经结点　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.3　删除　296
18.3.4　重写比较　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章　存储层次　346
21.1　cache的组织结构　346
21.2　cache块对齐　349
21.3　预取　350
21.4　循环交换　354
21.5　分块　355
21.6　垃圾收集和存储层次　357
推荐阅读　358
习题　358
附录　Tiger语言参考手册　360
参考文献　368
索引　376