编译器构造

目　　录
Crafting a Compiler
前言
致谢
第1章　引言　1
1.1　编译技术历史　1
1.2　编译器的功能　2
1.2.1　编译器生成的机器代码　3
1.2.2　目标代码格式　4
1.3　解释器　5
1.4　语法和语义　6
1.4.1　静态语义　7
1.4.2　运行时语义　7
1.5　编译器的组织　9
1.5.1　词法分析器　10
1.5.2　语法分析器　10
1.5.3　类型检查器　10
1.5.4　翻译器　10
1.5.5　符号表　11
1.5.6　优化器　11
1.5.7　代码生成器　11
1.5.8　编译器编写工具　12
1.6　程序设计语言和编译器设计　12
1.7　计算机体系结构和编译器设计　13
1.8　编译器设计考虑　13
1.8.1　调试编译器　14
1.8.2　优化编译器　14
1.8.3　可重定位编译器　14
1.9　集成开发环境　15
习题　15
第2章　一个简单的编译器　18
2.1　ac语言的一个非形式化定义　18
2.2　ac的形式化定义　19
2.2.1　语法规范　19
2.2.2　单词规范　20
2.3　一个简单编译器的各阶段　21
2.4　词法分析　22
2.5　语法分析　23
2.5.1　预测语法分析例程　24
2.5.2　实现产生式　25
2.6　抽象语法树　25
2.7　语义分析　27
2.7.1　符号表　27
2.7.2　类型检查　27
2.8　代码生成　29
习题　31
第3章　词法分析——理论与实践　32
3.1　词法分析器概述　32
3.2　正则表达式　34
3.3　示例　35
3.4　有限自动机与词法分析器　36
3.5　词法分析器生成器　39
3.5.1　在Lex中定义单词　40
3.5.2　字符集　40
3.5.3　使用正则表达式定义单词　41
3.5.4　使用Lex处理字符　43
3.6　其他词法分析器生成器　44
3.7　构建词法分析器的实际考虑　45
3.7.1　处理标识符和字面值　45
3.7.2　使用编译器指示以及列出
源码行　48
3.7.3　结束词法分析器　49
3.7.4　多超前字符　49
3.7.5　性能考虑　51
3.7.6　词法错误恢复　52
3.8　正则表达式和有限自动机　53
3.8.1　将正则表达式转换为NFA　54
3.8.2　创建DFA　54
3.8.3　优化有限自动机　56
3.8.4　将有限自动机转换为正则
表达式　58
3.9　总结　60
习题　61
第4章　文法和语法分析　64
4.1　上下文无关文法　64
4.1.1　最左推导　66
4.1.2　最右推导　66
4.1.3　语法分析树　66
4.1.4　其他类型的文法　67
4.2　CFG的性质　68
4.2.1　归约文法　68
4.2.2　二义性　68
4.2.3　错误的语言定义　69
4.3　转换扩展文法　69
4.4　语法分析器和识别器　70
4.5　文法分析算法　72
4.5.1　文法表示　72
4.5.2　推导空字符串　73
4.5.3　First集　74
4.5.4　Follow集　77
习题　79
第5章　自顶向下语法分析　82
5.1　概述　82
5.2　LL(k)文法　83
5.3　递归下降LL(1)语法分析器　85
5.4　表驱动LL(1)语法分析器　86
5.5　获得LL(1)文法　88
5.5.1　公共前缀　88
5.5.2　左递归　89
5.6　一个非LL(1)语言　90
5.7　LL(1)分析器的性质　92
5.8　分析表的表示　92
5.8.1　紧凑存储　93
5.8.2　压缩　94
5.9　语法错误恢复和修复　96
5.9.1　错误恢复　96
5.9.2　错误修复　96
5.9.3　LL(1)分析器中的错误检测　97
5.9.4　LL(1)分析器中的错误恢复　97
习题　98
第6章　自底向上语法分析　102
6.1　概述　102
6.2　移进–归约语法分析器　103
6.2.1　LR语法分析器和最右推导　103
6.2.2　LR分析如针织　104
6.2.3　LR分析引擎　105
6.2.4　LR分析表　105
6.2.5　LR(k)分析　107
6.3　构造LR(0)分析表　109
6.4　冲突诊断　113
6.4.1　二义性文法　114
6.4.2　非LR(k)文法　116
6.5　冲突消解和表构造　117
6.5.1　SLR(k)分析表构造　117
6.5.2　LALR(k)分析表构造　120
6.5.3　LALR传播图　122
6.5.4　LR(k)表构造　125
习题　129
第7章　语法制导翻译　135
7.1　概述　135
7.1.1　语义动作和语义值　135
7.1.2　综合属性和继承属性　136
7.2　自底向上语法制导翻译　137
7.2.1　示例　137
7.2.2　 产生式克隆　139
7.2.3　强制执行语义动作　140
7.2.4　激进的文法重构　141
7.3　自顶向下语法制导翻译　142
7.4　抽象语法树　143
7.4.1　具体语法树与抽象语法树　144
7.4.2　一种高效的AST数据结构　144
7.4.3　创建AST的基础架构　145
7.5　AST设计和构造　146
7.5.1　设计　147
7.5.2　构造　148
7.6　左值和右值的AST结构　150
7.7　AST设计模式　152
7.7.1　节点类层次　152
7.7.2　访问者模式　153
7.7.3　反射访问者模式　154
习题　157
第8章　符号表和声明处理　160
8.1　构造符号表　160
8.1.1　静态作用域　161
8.1.2　符号表接口　162
8.2　块结构语言和作用域　163
8.2.1　处理作用域　163
8.2.2　单符号表还是多符号表　163
8.3　基本实现技术　164
8.3.1　插入和查找名字　164
8.3.2　名字空间　166
8.3.3　一个高效的符号表实现　166
8.4　高级特性　169
8.4.1　记录和类型名　169
8.4.2　重载和类型层次　170
8.4.3　隐式声明　170
8.4.4　导出指示和导入指示　171
8.4.5　改变搜索规则　171
8.5　声明处理基础　172
8.5.1　符号表中的属性　172
8.5.2　类型描述符结构　172
8.5.3　使用抽象语法树进行类型
检查　173
8.6　变量和类型声明　174
8.6.1　简单变量声明　174
8.6.2　处理类型名　175
8.6.3　类型声明　176
8.6.4　变量声明再探　178
8.6.5　静态数组类型　179
8.6.6　结构和记录类型　180
8.6.7　枚举类型　181
8.7　类和方法声明　183
8.7.1　处理类声明　184
8.7.2　处理方法声明　186
8.8　类型检查简介　188
8.8.1　简单标识符和字面量　190
8.8.2　赋值语句　190
8.8.3　检查表达式　191
8.8.4　检查复杂名字　191
8.9　总结　194
习题　195
第9章　语义分析　198
9.1　控制结构的语义分析　198
9.1.1　可达性和终止分析　199
9.1.2　if语句　200
9.1.3　while、do和repeat循环
语句　203
9.1.4　for循环语句　204
9.1.5　break、continue、return和
goto语句　205
9.1.6　switch和case语句　210
9.1.7　异常处理　214
9.2　方法调用的语义分析　218
9.3　总结　223
习题　223
第10章　中间表示　227
10.1　概述　227
10.1.1　示例　228
10.1.2　中端　229
10.2　Java虚拟机　230
10.2.1　简介和设计原则　230
10.2.2　类文件内容　231
10.2.3　JVM指令　232
10.3　静态单赋值形式　237
习题　239
第11章　虚拟机代码生成　241
11.1　代码生成访问者　241
11.2　类和方法声明　243
11.2.1　类声明　243
11.2.2　方法声明　245
11.3　MethodBodyVisitor　245
11.3.1　常量　245
11.3.2　局部存储引用　246
11.3.3　静态引用　246
11.3.4　表达式　247
11.3.5　赋值　248
11.3.6　方法调用　249
11.3.7　字段引用　250
11.3.8　数组引用　251
11.3.9　条件执行　252
11.3.10　循环　252
11.4　LHSVisitor　253
11.4.1　局部引用　254
11.4.2　静态引用　254
11.4.3　字段引用　255
11.4.4　数组引用　255
习题　256
第12章　运行时支持　258
12.1　静态分配　258
12.2　栈分配　259
12.2.1　类和结构中的字段访问　260
12.2.2　运行时访问帧　261
12.2.3　处理类和对象　262
12.2.4　处理多重作用域　263
12.2.5　块级分配　264
12.2.6　关于帧的更多讨论　265
12.3　数组　267
12.3.1　静态一维数组　267
12.3.2　多维数组　270
12.4　堆管理　272
12.4.1　分配机制　272
12.4.2　释放机制　274
12.4.3　自动垃圾收集　274
12.5　基于区域的内存管理　279
习题　280
第13章　目标代码生成　284
13.1　翻译字节码　285
13.1.1　分配内存地址　286
13.1.2　分配数组和对象　286
13.1.3　方法调用　288
13.1.4　字节码翻译过程的示例　290
13.2　翻译表达式树　291
13.3　寄存器分配　294
13.3.1　动态寄存器分配　294
13.3.2　使用图着色进行寄存器
分配　296
13.3.3　基于优先级的寄存器分配　300
13.3.4　过程间寄存器分配　301
13.4　代码调度　302
13.4.1　改进代码调度　305
13.4.2　全局和动态代码调度　306
13.5　指令自动选择　307
13.5.1　使用BURS选择指令　308
13.5.2　使用Twig选择指令　310
13.5.3　其他方法　310
13.6　窥孔优化　311
13.6.1　窥孔优化级别　311
13.6.2　自动生成窥孔优化器　313
习题　314
第14章　程序优化　318
14.1　概述　318
14.2　控制流分析　323
14.2.1　控制流图　323
14.2.2　程序和控制流结构　325
14.2.3　直接过程调用图　325
14.2.4　深度优先生成树　326
14.2.5　支配关系　329
14.2.6　简单的支配关系计算算法　330
14.2.7　快速的支配关系计算算法　332
14.2.8　支配前沿　339
14.2.9　区间　341
14.3　数据流分析介绍　349
14.3.1　可用表达式　349
14.3.2　活跃变量　351
14.4　数据流框架　352
14.4.1　数据流评估图　353
14.4.2　交格　354
14.4.3　转移函数　355
14.5　求解　356
14.5.1　迭代　356
14.5.2　初始化　359
14.5.3　终止和快速框架　360
14.5.4　满足分配律的框架　363
14.6　常量传播　364
14.7　SSA形式　366
14.7.1　放置函数　368
14.7.2　重命名　369
习题　371
参考文献　378