目录 1
第1章 引论 1
1.1 编译的阶段 1
1.1.1 词法分析 2
1.1.2 语法分析 2
1.1.3 语义分析 4
1.1.4 中间代码生成 5
1.1.5 代码优化 5
1.1.6 代码生成 6
1.1.7 符号表管理 6
1.1.8 错误诊断和报告 8
1.1.9 阶段的分组 8
1.2 编译器的伙伴 8
1.2.1 预处理器 9
1.2.2 汇编器 10
1.2.3 装配器和连接编辑器 11
2.1 词法分析器的作用 12
第2章 词法分析 12
2.1.1 分离词法分析的理由 13
2.1.2 记号、模式、单词 13
2.1.3 记号的属性 14
2.1.4 词法错误 15
2.2 记号的描述 15
2.2.1 串和语言 15
2.2.2 语言的运算 16
2.2.3 正规式 16
2.2.5 表示的缩写 18
2.2.4 正规定义 18
2.2.6 非正规集 19
2.3 记号的识别 19
2.3.1 转换图 20
2.3.2 实现转换图 22
2.4 有限自动机 23
2.4.1 不确定的有限自动机 23
2.4.2 确定的有限自动机 25
2.4.3 NFA到DFA的变换 25
2.5 从正规式到NFA 29
2.6 DFA的化简 31
2.7 词法分析器的说明语言 33
习题 36
第3章 语法分析 39
3.1 分析器的作用 39
3.1.1 语法错误的处理 40
3.1.2 错误恢复策略 41
3.2 上下文无关文法 42
3.2.1 符号使用的约定 43
3.2.2 推导 44
3.2.3 分析树和推导 45
3.2.4 二义性 46
3.3 语言和文法 46
3.3.1 正规式和上下文无关文法的比较 47
3.3.2 验证文法产生的语言 48
3.3.3 适当的表达式文法 48
3.3.4 消除二义性 49
3.3.5 消除左递归 50
3.3.6 提左因子 51
3.3.7 非上下文无关的语言结构 52
3.3.8 形式语言概述 53
3.4 自上而下分析 55
3.4.1 自上而下分析的一般方法 55
3.4.2 预测分析器 56
3.4.3 非递归的预测分析 58
3.4.4 开始符号和后继符号 59
3.4.5 构造预测分析表 60
3.4.6 LL（1）文法 61
3.4.7 预测分析的错误恢复 62
3.5 自下而上分析 63
3.5.1 句柄 64
3.5.2 用栈实现移进-归约分析 66
3.5.3 移进-归约分析的冲突 67
3.6 LR分析器 68
3.6.1 LR分析算法 69
3.6.2 LR文法 72
3.6.3 构造SLR分析表 73
3.6.4 构造规范LR分析表 79
3.6.5 构造LALR分析表 83
3.6.6 非LR的上下文无关结构 86
3.7 二义文法的应用 87
3.7.1 使用优先级和结合规则来解决分析动作的冲突 87
3.7.2 悬空else的二义性 89
3.7.3 特殊情况产生式引起的二义性 90
3.7.4 LR分析的错误恢复 92
3.8 分析器的生成器 94
3.8.1 分析器的生成器Yacc 95
3.8.2 用Yacc处理二义文法 97
3.8.3 用Lex建立Yacc的词法分析器 99
3.8.4 Yacc的错误恢复 100
习题 101
第4章 语法制导的翻译 107
4.1 语法制导的定义 107
4.1.1 语法制导定义的形式 108
4.1.2 综合属性 108
4.1.3 继承属性 109
4.1.4 依赖图 110
4.1.5 计算次序 111
4.2 S属性的自下而上计算 112
4.2.1 语法树 113
4.2.2 构造表达式的语法树 113
4.2.3 构造语法树的语法制导定义 114
4.2.4 表达式的无环有向图 115
4.2.5 S属性的自下而上计算 116
4.3 L属性定义 118
4.3.2 翻译方案 119
4.3.1 L属性定义 119
4.4 自上而下翻译 122
4.4.1 删除翻译方案的左递归 122
4.4.2 预测翻译器的设计 126
4.5 继承属性的自下而上计算 127
4.5.1 删除翻译方案中嵌入的动作 127
4.5.2 分析栈上的继承属性 128
4.5.3 模拟继承属性的计算 130
4.5.5 一个困难的语法制导定义 133
4.5.4 用综合属性代替继承属性 133
4.6.1 自左向右遍历 134
4.6 递归计算 134
4.6.2 其它遍历方法 135
4.7 语法制导定义的分析 137
4.7.1 属性的递归计算 137
4.7.2 强无环的语法制导定义 138
习题 140
第5章 类型检查 143
5.1.1 类型表达式 144
5.1 类型体制 144
5.1.2 类型体制 145
5.1.3 静态和动态的类型检查 146
5.1.4 错误恢复 146
5.2 简单类型检查器的说明 146
5.2.1 一个简单的语言 147
5.2.2 表达式的类型检查 148
5.2.3 语句的类型检查 148
5.2.5 类型转换 149
5.2.4 函数的类型检查 149
5.3 类型表达式的等价 150
5.3.1 类型表达式的结构等价 151
5.3.2 类型表达式的名字 152
5.3.3 类型表示中的环 153
5.4 函数和算符的重载 154
5.4.1 子表达式的可能类型集合 154
5.4.2 缩小可能类型的集合 156
5.5 多态函数 156
5.5.1 为什么要使用多态函数 157
5.5.2 类型变量 158
5.5.3 一个含多态函数的语言 159
5.5.4 代换、实例和合一 161
5.5.5 多态函数的检查 161
习题 165
第6章 运行环境 168
6.1 源语言问题 168
6.1.1 过程 168
6.1.2 活动树 169
6.1.3 控制栈 170
6.1.4 声明的作用域 171
6.1.5 名字的结合 171
6.2 存储组织 172
6.2.1 运行时内存的划分 172
6.2.2 活动记录 173
6.2.3 编译时的局部数据安排 174
6.3.1 静态分配 175
6.3 存储分配策略 175
6.3.2 栈分配 177
6.3.3 悬空引用 180
6.3.4 堆分配 181
6.4 访问非局部名字 182
6.4.1 程序块 182
6.4.2 无过程嵌套的静态作用域 184
6.4.3 有过程嵌套的静态作用域 185
6.4.4 动态作用域 188
6.5 参数传递 189
6.5.1 值调用 190
6.5.2 引用调用 191
6.5.3 复写-恢复 191
6.5.4 换名调用 192
习题 193
第7章 中间代码生成 196
7.1 中间语言 196
7.1.1 后缀表示 196
7.1.3 三地址代码 197
7.1.2 图形表示 197
7.1.4 三地址语句的种类 198
7.1.5 三地址语句的实现 199
7.1.6 内部表示的比较 200
7.2 声明 201
7.2.1 过程中的声明 201
7.2.2 作用域信息的保存 202
7.3 赋值语句 204
7.3.1 符号表中的名字 204
7.2.3 记录的域名 204
7.3.2 临时名字的重新使用 205
7.3.3 数组元素的定址 206
7.3.4 数组元素定址的翻译方案 208
7.3.5 赋值语句中的类型转换 210
7.3.6 记录域的访问 211
7.4.1 翻译布尔表达式的方法 212
7.4.2 数值表示 212
7.4 布尔表达式 212
7.4.3 短路代码 214
7.4.4 控制流语句 214
7.4.5 布尔表达式的控制流翻译 216
7.5 分情况语句 218
习题 220
第8章 代码生成 224
8.1 代码生成器设计中的问题 224
8.1.1 代码生成器的输入 224
8.1.3 存储管理 225
8.1.2 目标程序 225
8.1.4 指令选择 226
8.1.5 寄存器分配 226
8.1.6 计算次序选译 227
8.1.7 代码生成途径 228
8.2 目标机器 228
8.2.1 目标机器 228
8.2.2 指令代价 229
8.3.1 基本块 230
8.3 基本块和流图 230
8.3.2 基本块的变换 232
8.3.3 流图 233
8.4 下次引用信息 234
8.4.1 计算下次引用信息 234
8.4.2 临时名字的存储分配 235
8.5 一个简单的代码生成器 235
8.5.1 寄存器描述和地址描述 236
8.5.2 代码生成算法 236
8.5.3 函数getreg 237
8.5.4 为其它类型的语句产生代码 238
8.5.5 条件语句 239
习题 240
第9章 代码优化 241
9.1 引言 241
9.1.1 代码改进变换的标准 241
9.1.2 争取较好的性能 242
9.1.3 优化编译器的组织 243
9.2 优化的主要种类 245
9.2.1 公共子表达式 245
9.2.2 复写传播 247
9.2.3 死代码删除 248
9.2.4 循环优化 248
9.2.5 代码外提 248
9.2.6 归纳变量和强度消弱 249
9.3 流图中的循环 250
9.3.1 必经结点 250
9.3.2 自然循环 251
9.3.4 前置结点 252
9.3.3 内循环 252
9.3.5 可归约流图 253
9.4 全局数据流分析介绍 254
9.4.1 点和路径 255
9.4.2 到达-定值 256
9.4.3 到达-定值的迭代算法 256
9.4.4 可用表达式 259
9.4.5 活跃变量分析 262
9.4.6 定值-引用链 262
9.5.1 公共子表达式删除 263
9.5 代码改进变换 263
9.5.2 复写传播 264
9.5.3 寻找循环不变计算 266
9.5.4 代码外提 267
9.5.5 代码外提后维持数据流信息 268
9.5.6 归纳变量删除 269
9.5.7 有循环不变计算的归纳变量 272
习题 272
10.1.1 对象 274
10.1 面向对象语言的概念 274
第10章 面向对象语言的编译 274
10.1.2 对象类 275
10.1.3 继承性 275
10.1.4 信息封装 277
10.1.5 小结 277
10.2 方法的编译 278
10.3 编译继承性的方案 279
10.3.1 简单继承性的编译方案 280
10.3.2 多继承性的编译方案 282
习题 286
第11章 函数式程序设计语言的编译 289
11.1 函数式程序设计语言简介 289
11.1.1 SFP的构造 289
11.1.2 参数传递机制 290
11.1.3 自由出现和约束出现 292
11.2 一个简单的函数式语言的编译简介 293
11.2.1 几个受启发的例子 293
11.2.3 环境与约束 295
11.2.2 4个编译函数 295
11.3 抽象机的系统结构 296
11.3.1 FAM的栈 297
11.3.2 FAM的堆 298
11.3.3 名字的寻址 299
11.3.4 约束的建立 300
11.4 指令集和编译 300
11.4.1 程序表达式 300
11.4.2 简单表达式 301
11.4.3 变量的引用性出现 302
11.4.4 函数定义 303
11.4.5 函数应用 304
11.4.6 构造和计算闭包 307
11.4.7 letrec表达式和局部变量 309
11.5 表的实现 310
11.5.1 SFP的扩充 310
11.5.2 表表达式的编译 312
11.5.3 表运算的编译 312
习题 315