第1章 编译概述 1
1.1 翻译和解释 1
1.2 编译程序的组成部分 2
1.2.1 分析 2
1.2.2 综合 4
1.2.3 表格管理 5
1.2.4 错误处理 5
1.3 编译程序的组织 6
第2章 程序语言的基本知识 8
2.1 符号串的集合 8
2.1.1 字母表 8
2.1.2 符号串 8
2.1.3 语言 9
2.2 文法和语言 10
2.2.1 引言 11
2.2.2 文法和语言的形式定义 13
2.3 分析树和二义性 18
2.3.1 分析树 18
2.3.2 分析树的构造 20
2.3.3 二义性 21
2.4 形式语言概观 24
2.4.1 形式语言分类 24
2.4.2 非上下文无关的语言结构 25
2.4.3 上下文无关语言和正则语言的区别 26
练习 26
第3章 词法分析 29
3.1 词法分析程序的设计 29
3.1.1 词法分析程序的功能 29
3.1.2 单词的词类和属性 30
3.1.3 词法分析程序作为一个独立子程序 32
3.2 词法分析程序的手工构造 32
3.2.1 确定的有限自动机 32
3.2.2 构造识别单词的DFA 35
3.2.3 编写词法分析程序 36
3.3 有限自动机 38
3.3.1 非确定有限自动机 39
3.3.2 确定的有限自动机的化简 42
3.4 正规表达式与有限自动机 45
3.4.1 正规表达式与单词 45
3.4.2 正规表达式与有限自动机的等价性 48
3.5 词法分析程序的自动构造工具 51
练习 55
第4章 语法分析 58
4.1 语法分析器概述 58
4.2 预测分析器 59
4.2.1 预测分析 59
4.2.2 递归预测分析器的构造 62
4.2.3 非递归的预测分析器的构造 66
4.3 书写文法 72
4.3.1 消除左递归 73
4.3.2 提取左因子 75
4.4 自底向上分析 76
4.4.1 规范归约 77
4.4.2 “移进-归约”分析法的栈实现 79
4.5 算符优先分析法 81
4.5.1 利用算符优先关系寻找右句型的可归约串 83
4.5.2 算符优先关系表的构造 85
4.5.3 优先函数 86
4.5.4 算符优先分析法的错误处理示例 87
4.6 LR分析器 89
4.6.1 LR分析器的逻辑结构及工作过程 89
4.6.2 SLR分析表的构造 91
4.6.3 LR（1）分析表的构造 102
4.6.4 LALR分析表的构造 107
4.7 LR分析方法对二义文法的应用 113
4.8 分析器的生成器Yacc 116
4.8.1 引言 116
4.8.2 书写Yacc的源程序 117
4.8.3 用Yacc处理二义文法 119
4.8.4 用Lex建立Yacc的词法分析器 121
4.8.5 Yacc的错误恢复 122
练习 123
第5章 语法制导翻译 128
5.1 语法制导定义 128
5.1.1 语法制导定义的形式 129
5.1.2 综合属性 129
5.1.3 继承属性 130
5.1.4 依赖图 131
5.1.5 计算顺序 133
5.2 语法树的构造 134
5.2.1 语法树 134
5.2.2 建立表达式的语法树 135
5.2.3 建立语法树的语法制导定义 136
5.2.4 关于表达式的有向非循环图 137
5.3 S-属性定义及其自底向上的计算 138
5.4 L-属性定义 140
5.4.1 L-属性定义的含义 141
5.4.2 翻译模式 141
5.5 自顶向下的翻译 144
5.5.1 从翻译模式中消除左递归 144
5.5.2 预测翻译器的设计 147
5.6 自底向上计算继承属性 149
5.6.1 从翻译模式中去掉嵌入的动作 149
5.6.2 分析栈中的继承属性 150
5.6.3 模拟继承属性的计算 152
练习 155
第6章 运行时刻环境的组织 158
6.1 有关源语言中的一些问题的讨论 158
6.1.1 过程 158
6.1.2 活动树 159
6.1.3 控制栈 161
6.1.4 说明的作用域 162
6.1.5 名字的绑定 162
6.1.6 提出的问题 163
6.2 存储组织 163
6.2.1 运行时刻内存的划分 163
6.2.2 活动记录 164
6.2.3 编译时刻的局部数据的设计 165
6.3 运行时刻存储分配策略 165
6.3.1 静态存储分配 165
6.3.2 栈式存储分配 168
6.3.3 堆式存储分配 171
6.4 对非局部名字的访问 172
6.4.1 块 173
6.4.2 不含嵌套过程的词法作用域 174
6.4.3 含有嵌套过程的词法作用域 175
6.4.4 动态作用域 180
6.5 参数传递 181
6.5.1 传值调用 181
6.5.2 引用调用 182
6.5.3 复制恢复 183
6.5.4 传名调用 184
6.5.5 过程作为参数 185
6.6 符号表 186
6.6.1 符号表的作用 186
6.6.2 符号表的表项 187
6.6.3 符号表的存储结构 189
练习 195
第7章 中间代码生成 199
7.1 中间语言 199
7.1.1 图表示法 199
7.1.2 三地址代码 200
7.1.3 三地址语句的种类 201
7.1.4 语法制导翻译生成三地址代码 202
7.1.5 三地址代码的具体实现 202
7.2 类型检查 204
7.2.1 类型表达式 205
7.2.2 类型表达式的等价 207
7.2.3 类型检查 209
7.2.4 类型转换 211
7.3 说明语句 212
7.3.1 过程中的说明语句 212
7.3.2 保留作用域信息 213
7.3.3 记录中的域名 215
7.4 赋值语句 216
7.4.1 符号表中的名字 216
7.4.2 数组元素地址分配 217
7.4.3 访问数组元素的翻译模式 219
7.4.4 访问记录中的域 220
7.5 布尔表达式和控制流语句 221
7.5.1 翻译布尔表达式的方法 222
7.5.2 数值表示法 222
7.5.3 控制流语句 223
7.5.4 控制流语句中布尔表达式的翻译 225
7.6 CASE语句 227
7.7 回填 228
7.7.1 使用回填翻译布尔表达式 228
7.7.2 使用回填翻译控制流语句 231
7.7.3 标号和转移语句 235
7.8 过程调用 235
练习 237
第8章 代码生成 240
8.1 目标机器 241
8.2 运行存储管理 243
8.2.1 静态分配管理 244
8.2.2 栈式分配管理 245
8.2.3 名字的运行地址 246
8.3 基本块和流图 248
8.3.1 基本块 248
8.3.2 流图 249
8.4 下次引用信息 250
8.5 一个简单的代码生成器 251
8.5.1 寄存器描述器和地址描述器 252
8.5.2 代码生成算法 252
8.6 基本块的dag表示法 255
8.6.1 dag的构造 256
8.6.2 dag的应用 258
8.7 从dag生成目标代码 260
练习 263
第9章 中间代码的优化 265
9.1 引言 265
9.1.1 代码优化的标准 265
9.1.2 争取较好的性能 266
9.1.3 优化编译器的组织 267
9.2 优化的主要种类 269
9.2.1 公共子表达式 269
9.2.2 复写传播 270
9.2.3 死代码删除 270
9.2.4 循环优化 271
9.3 流图中的循环 273
9.3.1 必经结点 273
9.3.2 自然循环 276
9.3.3 内循环 276
9.3.4 前置结点 277
9.3.5 归约流图 278
9.4 全局数据流分析介绍 279
9.4.1 点和路径 280
9.4.2 到达＿定值 280
9.4.3 集合的表示 282
9.4.4 局部的到达＿定值 283
9.4.5 引用＿定值链 284
9.5 数据流方程的迭代求解 284
9.5.1 到达＿定值的迭代算法 284
9.5.2 可用表达式 286
9.5.3 活跃变量分析 288
9.5.4 定值＿引用链 289
9.5.5 流图结点的深度优先次序 290
9.5.6 用深度优先次序改进数据流求解算法 291
9.6 优化的实现 292
9.6.1 删除公共子表达式 292
9.6.2 复写传播 294
9.6.3 寻找循环不变计算 296
9.6.4 代码外提 296
9.6.5 代码外提后维持数据流信息 298
9.6.6 归纳变量 298
9.6.7 有循环不变计算的归纳变量 302
练习 302
参考文献 305