第一章 引论 1
1.1 程序设计语言 1
1.2 编译过程概述 3
1.2.1 编译程序模型 4
1.2.2 分析 4
1.2.3 综合 6
1.2.4 符号表管理 10
1.2.5 错误检测和处理 11
1.3 编译器的构造 11
1.3.1 阶段的分组 11
1.3.2 编译器的运行环境 12
1.3.3 构造编译器的工具 15
第二章 形式语言的基本知识 17
2.1 引言 17
2.1.1 语法树 17
2.1.2 规则 18
2.1.3 推导 18
2.2 字母表、符号串及其集合的运算 19
2.2.1 字母表和符号串 20
2.2.2 符号串及其集合的运算 20
2.3 文法和语言的形式定义 22
2.3.1 文法的形式定义 22
2.3.2 推导的形式定义 24
2.4.1 分析树（Parse tree） 26
2.4 分析树和二义性 26
2.3.3 短语、直接短语和句柄 26
2.4.2 子树与短语 28
2.4.3 文法的二义性 29
2.5 文法和语言分类 30
第三章 词法分析 33
3.1 词法分析器的功能 33
3.1.1 词法分析器的作用 33
3.1.2 单词类别、构词规则和属性 34
3.1.3 词法错误 35
3.2 输入缓冲区 36
3.3.1 正规表达式与正规集 38
3.3 正规表达式与正规集 38
3.3.2 正规定义 39
3.4 词法分析器的设计 40
3.4.1 预处理 40
3.4.2 单词符号的识别 41
3.4.3 状态转换图 42
3.4.4 实现转换图 44
3.5 有穷自动机 51
3.5.1 确定有穷自动机 51
3.5.2 不确定有穷自动机 52
3.5.3 NFAN到DFAM的转换 54
3.5.4 从正规式构造NFAN 57
3.5.5 确定有穷自动机的化简 59
3.6 词法分析器的自动生成器 61
3.6.1 lex源程序 62
3.6.2 lex的实现 66
第四章 语法分析 68
4.1 自上而下分析 68
4.1.1 递归下降分析 69
4.1.2 预测分析器 75
4.1.3 预测分析器的转换图 78
4.1.4 非递归预测分析器 80
4.1.5 构造预测分析表 83
4.1.6 LL（1）文法 87
4.2 自下而上分析 88
4.2.1 句柄 89
4.2.2 剪句柄 90
4.2.3 用堆栈实现移进—归约分析 91
4.3 算符优先分析 93
4.3.1 使用算符优先关系的移进—归约分析 95
4.3.2 算法优先关系表的构造 97
4.3.3 优先函数 101
4.3.4 算符优先分析的错误恢复 103
4.4 LR分析器 103
4.4.1 LR分析算法 104
4.4.2 SLR分析表的构造 106
4.4.3 规范的LR分析表的构造 114
4.4.4 LALR分析表的构造 118
4.5 二义文法的应用 125
4.6 语法分析器的生成器 129
4.6.1 yacc源程序 130
4.6.2 使用二义文法的yacc应用示例 132
第五章 语法制导翻译和中间代码生成 137
5.1 概述 138
5.1.1 语法制导定义 138
5.1.2 语法制导翻译 143
5.2 逆波兰表示法 146
5.3 语法树 147
5.4 三地址代码 149
5.4.2 三地址语句的实现 150
5.4.1 三地址语句的种类 150
5.5 简单算术表达式和赋值语句到四元式的翻译 153
5.6 布尔表达式到四元式的翻译 169
5.6.1 数值表示法的语法制导翻译 170
5.6.2 布尔表达式的控制流翻译 172
5.7 控制语句的翻译 176
5.7.1 标号和转移语句 176
5.7.2 控制流语句的翻译 179
5.7.3 case语句的翻译 181
5.8 说明语句的翻译 183
5.8.1 简单变量说明语句的翻译 184
5.8.2 数组说明语句的翻译 185
5.8.3 记录结构说明语句的翻译 186
5.9.1 数组元素引用 189
5.9 数组元素和记录域的引用 189
5.9.2 记录域的引用 191
5.10 过程调用语句的翻译 192
5.11 自上而下分析语法制导翻译概述 193
第六章 运行环境 199
6.1 源语言问题 199
6.1.1 过程 200
6.1.2 活动树 200
6.1.3 控制栈 202
6.1.4 说明的作用域 203
6.1.5 名字的联编 203
6.2.1 运行时内存的划分 204
6.2 存储组织 204
6.2.2 活动记录 205
6.2.3 编译时局部数据的安排 206
6.3 存储分配策略 207
6.3.1 静态分配 207
6.3.2 栈式存储分配 209
6.3.3 堆式存储分配 213
6.4 访问非局部名字 214
6.4.1 块 214
6.4.2 没有嵌套过程的词法作用域 215
6.4.3 具有嵌套过程的静态作用域 216
6.4.4 动态作用域 221
6.5.1 值调用 222
6.5 参数传递 222
6.5.2 引用调用 223
6.5.3 复制恢复 224
6.5.4 换名调用 225
6.6 符号表 226
6.6.1 符号表的表项 227
6.6.2 线性符号表 228
6.6.3 散列符号表 229
6.6.4 作用域信息的表示 231
第七章 代码生成 235
7.1 目标机器 236
7.2 运行时的存储管理 238
7.2.1 静态分配 239
7.2.2 栈式分配 240
7.2.3 名字的运行地址 242
7.3 基本块和流图 243
7.3.1 基本块 243
7.3.2 基本块的变换 244
7.3.3 流图 245
7.4 下次引用信息 246
7.5 一个简单的代码生成器 247
7.5.1 寄存器和地址描述符 248
7.5.2 代码生成算法 248
7.5.3 函数getReg 249
7.5.4 为其它类型的语句生成目标代码 250
7.6 寄存器分配 251
7.6.1 全局寄存器分配 252
7.6.2 执行代价的节省 252
7.6.3 寄存器分配的图着色方法 254
7.7 基本块的dag表示及其应用 255
7.7.1 dag的构造 257
7.7.2 dag的应用 258
7.7.3 数组、指针和过程调用 259
7.8 从dag生成目标代码 260
7.8.1 重排序 261
7.8.2 dag的启发式排序 261
7.8.3 树的最优代码 263
7.9 窥孔优化 268
第八章 代码优化和数据流分析 272
8.1 控制流分析和循环查找算法 273
8.1.1 程序流图和循环 273
8.1.2 必经结点集 274
8.1.3 查找循环算法 276
8.1.4 可归约流图 277
8.2 到达一定值与引用一定值链 278
8.2.1 到达一定值数据流方程 278
8.2.2 到达一定值的迭代算法 279
8.2.3 引用一定值链（ud链） 281
8.3 循环优化 282
8.3.1 代码外提 282
8.3.2 强度削弱 284
8.3.3 删除归纳变量 285
8.4.1 活跃变量的数据流方程 289
8.4 活跃变量与定值一引用链（du链） 289
8.4.2 活跃变量数据流方程的迭代算法 290
8.5 删除全局公共子表达式 292
8.5.1 可用表达式及其数据流方程 292
8.5.2 可用表达式数据流方程的迭代算法 294
8.5.3 删除全局公共子表达式 295
8.6 复写传播 295
8.6.1 复写传播算法 295
8.6.2 代码优化的综合考虑 297
9.1 编译器的规划 301
9.1.1 源语言问题 301
第九章 编译器的设计与实现 301
9.1.2 目标语言问题 302
9.1.3 性能标准 302
9.2 编译器的开发方法 302
9.2.1 编译器的书写语言 303
9.2.2 自展 303
9.3 编译器的开发环境 306
9.4 测试和维护 308
9.5 几个编译器简介 308
9.5.1 Pascal编译器 308
9.5.2 C语言编译器 309
9.5.3 FORTRANH编译器 310
参考文献 313