第1章 引论 1
1.1 程序设计语言 1
1.2 程序设计语言的翻译 4
1.3 编译程序的总体结构 8
1.4 编译程序的组织 15
1.5 编译程序的生成 17
1.6 本章小结 22
习题 22
第2章 高级语言及其文法 24
2.1 语言概述 24
2.2 基本定义 26
2.3 文法的定义 31
2.4 文法的分类 40
2.5 CFG的语法树 46
2.6 CFG的二义性 53
2.7 本章小结 57
习题 58
第3章 词法分析 64
3.1 词法分析器的功能 64
3.1.1 单词的分类与表示 65
3.1.2 词法分析器的输出 67
3.1.3 源程序的输入缓冲与预处理 68
3.1.4 词法分析阶段的错误处理 70
3.1.5 词法分析器的位置 72
3.2 单词的描述 73
3.2.1 正则文法 73
3.2.2 正则表达式 74
3.2.3 正则表达式与正则文法的等价性 77
3.2.4 有穷状态自动机 83
3.2.5 状态转换图 86
3.2.6 正则表达式转换为状态转换图 87
3.3 单词的识别 89
3.3.1 有穷状态自动机与单词识别的关系 89
3.3.2 单词识别的状态转换图表示 93
3.3.3 几种典型的单词识别问题 96
3.3.4 状态转换图的实现 98
3.3.5 词法分析程序的编写 103
3.4 词法分析程序的自动生成 106
3.4.1 Lex源程序 106
3.4.2 Lex的实现原理 111
3.5 本章小结 111
习题 112
第4章 自顶向下的语法分析 118
4.1 语法分析概述 118
4.2 自顶向下的语法分析面临的问题与文法的改造 119
4.2.1 自顶向下分析面临的问题 120
4.2.2 对上下文无关文法的改造 123
4.2.3 LL（1）文法 127
4.3 预测分析法 131
4.3.1 预测分析器的构成 131
4.3.2 预测分析表的构造 134
4.3.3 预测分析中错误的处理 134
4.4 递归下降分析法 137
4.4.1 递归下降分析法的基本思想 137
4.4.2 语法图和递归子程序法 138
4.4.3 基于语法图的语法分析器的工作方式 140
4.4.4 语法图的化简与实现 140
4.4.5 递归子程序法的实现步骤 143
4.5 本章小结 143
习题 144
第5章 自底向上的语法分析 147
5.1 自底向上的语法分析概述 147
5.1.1 移进-归约分析 148
5.1.2 优先法 150
5.1.3 状态法 151
5.2 算符优先分析法 154
5.2.1 算符优先文法 154
5.2.2 算符优先矩阵的构造 156
5.2.3 算符优先分析算法 160
5.2.4 优先函数 163
5.2.5 算符优先分析的出错处理 166
5.3 LR分析法 168
5.3.1 LR分析算法 168
5.3.2 LR（0）分析表的构造 172
5.3.3 SLR（1）分析表的构造 180
5.3.4 LR（1）分析表的构造 183
5.3.5 LALR（1）分析表的构造 188
5.3.6 二义性文法的应用 195
5.3.7 LR分析中的出错处理 199
5.4 语法分析程序的自动生成工具Yacc 201
5.4.1 Yacc源程序的结构 201
5.4.2 Yacc源程序的声明部分 203
5.4.3 Yacc源程序的规则部分 204
5.4.4 Yacc源程序的例程部分 205
5.4.5 Yacc对二义性文法的处理 205
5.4.6 Yacc的出错处理 207
5.5 本章小结 208
习题 209
第6章 语法制导翻译与属性文法 213
6.1 语法制导翻译概述 213
6.2 语法制导定义 215
6.3 属性计算 220
6.3.1 依赖图 220
6.3.2 属性的计算顺序 222
6.3.3 S-属性定义 223
6.3.4 L-属性定义 223
6.3.5 属性计算示例 225
6.4 翻译模式 229
6.4.1 翻译模式与语义动作的执行时机 229
6.4.2 S-属性定义的自底向上翻译 233
6.4.3 L-属性定义的自顶向下翻译 236
6.4.4 L-属性定义的自底向上翻译 242
6.5 本章小结 247
习题 247
第7章 语义分析与中间代码生成 250
7.1 中间代码的形式 250
7.1.1 逆波兰表示 250
7.1.2 三地址码 251
7.1.3 图表示 255
7.2 声明语句的翻译 258
7.2.1 类型表达式 258
7.2.2 类型等价 260
7.2.3 声明语句的文法 260
7.2.4 过程内声明语句的翻译 260
7.2.5 嵌套过程中声明语句的翻译 262
7.2.6 记录的翻译 264
7.3 赋值语句的翻译 265
7.3.1 简单赋值语句的翻译 265
7.3.2 数组元素的寻址 266
7.3.3 带有数组引用的赋值语句的翻译 268
7.3.4 记录域的访问 270
7.4 类型检查 271
7.4.1 类型检查的规则 271
7.4.2 类型转换 272
7.5 控制结构的翻译 274
7.5.1 布尔表达式的翻译 275
7.5.2 常见控制结构的翻译 277
7.5.3 布尔表达式的控制流翻译 279
7.5.4 混合模式的布尔表达式翻译 281
7.6 回填 283
7.6.1 布尔表达式的回填式翻译 283
7.6.2 常用控制流语句的回填式翻译 286
7.6.3 for循环语句的回填式翻译 291
7.6.4 repeat语句的回填式翻译 292
7.6.5 break、continue及goto语句的翻译 292
7.7 switch语句的翻译 293
7.7.1 switch语句翻译的基本思想 293
7.7.2 switch语句的语法制导翻译 294
7.8 过程调用和返回语句的翻译 296
7.9 输入输出语句的翻译 298
7.10 本章小结 300
习题 300
第8章 符号表管理 305
8.1 符号表的作用 305
8.2 符号表中存放的信息 307
8.2.1 符号表中的名字 307
8.2.2 符号表中的属性 309
8.2.3 符号的地址属性 310
8.3 符号表的组织结构 311
8.3.1 符号表的线性表实现 311
8.3.2 符号表的散列表实现 312
8.4 符号表与作用域 315
8.4.1 程序块结构的符号表 316
8.4.2 程序块结构符号表的其他实现 318
8.4.3 C语言的符号表 321
8.4.4 嵌套过程的符号表 322
8.5 本章小结 323
习题 323
第9章 运行时的存储组织 325
9.1 与存储组织有关的源语言概念与特征 325
9.1.1 名字及其绑定 325
9.1.2 声明的作用域 326
9.1.3 过程及其活动 329
9.1.4 参数传递方式 330
9.1.5 对变长数据及用户自由申请空间的支持 332
9.2 存储组织 333
9.2.1 运行时内存的划分 333
9.2.2 活动记录 334
9.2.3 局部数据的组织 335
9.2.4 全局存储分配策略 335
9.3 静态存储分配 336
9.4 栈式存储分配 338
9.4.1 调用序列和返回序列 339
9.4.2 C语言的过程调用和过程返回 340
9.4.3 栈中的可变长数据 341
9.5 栈中非局部数据的访问 342
9.5.1 无嵌套过程的静态作用域的实现 343
9.5.2 包含嵌套过程的静态作用域的实现 344
9.5.3 动态作用域的实现 349
9.6 本章小结 350
习题 351
第10章 代码优化 354
10.1 优化的种类 354
10.1.1 公共子表达式删除 355
10.1.2 复制传播 357
10.1.3 无用代码删除 357
10.1.4 代码外提 358
10.1.5 强度削弱和归纳变量删除 358
10.2 控制流分析 360
10.2.1 基本块 360
10.2.2 流图 361
10.2.3 循环 362
10.3 数据流分析 365
10.3.1 数据流方程的一般形式 365
10.3.2 到达-定义分析 366
10.3.3 活跃变量分析 368
10.3.4 可用表达式分析 369
10.4 局部优化 371
10.4.1 基本块的DAG表示 371
10.4.2 局部公共子表达式删除 372
10.4.3 无用代码删除 373
10.4.4 代数恒等式的使用 373
10.5 循环优化 374
10.5.1 循环不变计算的检测 374
10.5.2 代码外提 375
10.5.3 归纳变量删除和强度削弱 377
10.5.4 带有循环不变表达式的归纳变量 380
10.6 全局优化 381
10.6.1 全局公共子表达式的删除 381
10.6.2 复制传播 382
10.7 本章小结 384
习题 385
第11章 代码生成 388
11.1 代码生成器设计中的问题 388
11.1.1 代码生成器的输入 388
11.1.2 目标代码的形式 388
11.1.3 指令选择 389
11.1.4 寄存器分配 389
11.1.5 计算顺序选择 390
11.2 目标语言 390
11.2.1 目标机模型 390
11.2.2 程序和指令的开销 391
11.2.3 变量的运行时刻地址 392
11.3 一个简单的代码生成器 392
11.3.1 后续引用信息 393
11.3.2 寄存器描述符与地址描述符 394
11.3.3 代码生成算法 394
11.3.4 常用三地址码的代码生成 396
11.4 寄存器分配与指派 397
11.4.1 全局寄存器分配 398
11.4.2 引用计数 398
11.4.3 外层循环的寄存器指派 400
11.5 本章小结 400
习题 400
附录 “编译原理”课程教学设计 403
缩写符号 413
词汇索引 414
参考文献 428