第一章 引论 1
1．1 翻译程序 1
1．2 为什么需要编译程序 3
1．2．1 模块性 4
1．2．2 静态解释与动态解释 6
1．2．3 机器无关性 6
1．2．4 语言标准化 7
1．2．5 程序语言特征 8
1．3 编译程序的开销 8
1．4 编译程序的工作过程 9
1．4．1 分析 10
1．4．2 综合 11
1．5 编译程序的结构 11
1．6 编译程序的组织方式 14
1．7编译程序的位置 15
1．8 程序的移植与可移植性 16
1．9 程序的可再入性 16
1．10 编译自动化 17
1．11 小结 18
第二章 形式语言理论介绍 19
2．1 语言成份 19
2．1．1 符号与字母表 20
2．1．2 符号串 21
2．2 产生式文法和语言 22
2．2．1 形式语言理论历史简述 23
2．2．2 产生式文法 24
2．2．3 文法 24
2．2．4 上下文无关文法 25
2．2．5 上下文无关文法的形式定义 26
2．2．6 如何用上下文无关文法定义语言 28
2．3 文法分类 30
2．3．1 0型文法 30
2．3．2 1型文法 30
2．3．3 上下文无关文法（2型文法） 32
2．3．4 右线性文法和正规言语法（3型文法） 33
2．3．5 文法分类的意义 34
2．4 语言和语法树 36
2．4．1 句型、句子和语言 36
2．4．2 树形表示 36
2．4．3 语法树 40
2．4．4 产生式树 42
2．5 文法的一些特性 45
2．5．1 无用非终结符号 45
2．5．2 不可达文法符号 46
2．5．3 可空非终结符号 48
2．5．4 最左、最右推导，规范推导 48
2．5．5 二义性 51
2．5．6 文法举例 54
2．6 分析方法简介 56
2．6．1 自上而下分析 56
2．6．2 确定的自上而下分析器 59
2．6．3 确定的自下而上分析器 63
2．6．4 文法在内存中的表示 66
练习 68
第三章 有穷自动机 73
3．1 概述 73
3．2 有穷自动机的形式定义 77
3．2．1 状态转换表 79
3．2．2 状态转换图 79
3．2．3 构形和移动 81
3．2．4 自动机的等价性 82
3．2．5 非确定的有穷自动机 82
3．3 NDFSA到DFSA的转换 87
3．3．1 空移环路的寻找和消除 87
3．3．2 消余空移 89
3．3．3 利用状态转换表消除空移 92
3．3．4 确定化——子集法 95
3．3．5 确定化——造表法 100
3．3．6 消余不可达状态 105
3．3．7 确定的有穷自动机的化简 106
3．3．8 从化简后的DFSA到程序表示 111
3．3．9 小结 113
3．4 正规文法与有穷自动机 113
3．4．1 从正规文法到FSA 113
3．4．2 从FSA到正规文法 115
3．5 正规表达式与FSA 116
3．5．1 正规表达式的定义 116
3．5．2 正规表达式的CFG 118
3．5．3 正规表达式与FSA的对应性 119
3．5．4 正规表达式到NDFSA M的转换 119
3．5．5 NDFSA M到正规表达式的转换 125
3．5．6 从正规文法到正规表达式 128
3．6 DFSA在计算机中的表示 132
第四章 词法分析 135
4．1 词法分析概述 135
4．2 单词符号 137
4．3 扫描程序的设计 139
4．4 标识符的处理 146
4．4．1 类型的机内表示 147
4．4．2 标识符的语义表示 152
4．4．3 符号表（标识符表） 156
4．4．4 标识符处理的基本思想 157
4．5 设计词法分析程序的直接方法 159
4．6 与设计扫描程序相关的几个问题 161
练习 162
第五章 语法分析——自上而下分析 167
5．1 非确定的下推自动机 168
5．1．1 PDA的形式定义 168
5．1．2 PDA的构形和移动 171
5．1．3 上下文无关语言与PDA 174
5．2 消余左递归方法 178
5．2．1 文法的左递归性 178
5．2．2 用扩展的BNF表示法消除左递归 179
5．2．3 直接改写法 182
5．2．4 消余所有左递归的算法 183
5．3 LL（k）文法 185
5．3．1 LL（1）文法的判断条件 186
5．3．2 FIRST，FOLLOW，SELECT的构造方法 187
5．4 确定的LL（1）分析器的构造 190
5．4．1 构造分析表M的算法 191
5．4．2 LL（1）分析器的总控算法 193
5．5 LL（k）文法的几个结论 195
5．6 递归下降分析程序及其设计 196
5．6．1 框图设计 198
5．6．2 程序设计 201
练习 204
第六章 自下而上分析和优先分析方法 207
6．1 概述 207
6．2 短语和句柄 208
6．3 移进——归约方法 210
6．4 非确定的自下而上分析器 213
6．4．1 拓广的PDA与上下文无关语言的等价性 215
6．5 有关文法的一些关系 219
6．5．1 关系 219
6．5．2 布尔矩阵和关系 222
6．5．3 Warshall 算法 224
6．6 简单优先分析方法 225
6．6．1 优先关系 225
6．6．2 简单优先关系的直接构造方法 227
6．6．3 简单优先关系的形式化构造方法 229
6．6．4 简单优先文法及其分析算法 230
6．6．5 简单优先分析方法的局限性 235
6．7 简符优先分析方法 236
6．7．1 算符优先文法 236
6．7．2 OPG优先关系的构造 238
6．7．3 素短语及句型的分析 240
6．7．4 算符优先分析算法 242
6．8 优先函数及其构造 244
6．8．1 Bell方法 245
6．8．2 Floyd方法 247
6．8．3 两种方法的比较 248
6．9 两种优先分析方法的比较 250
练习 250
第七章 自下而上的LR（K）分析方法 253
7．1 LR（k）分析方法概述 253
7．2 LR（k）文法和LR（k）分析器 254
7．3 LR（0）分析表的构造 260
7．3．1 规范句型的活前缀 260
7．3．2 LR（0）项目 261
7．3．3 文法G的拓广文法 262
7．3．4 CLOSURE（I）函数 262
7．3．5 goto（I，X）函数 263
7．3．6 LR（0）项目集规范族 264
7．3．7 有效项目 267
7．3．8 例子 269
7．3．9 LR（0）文法 273
7．3．10 构造LR（0）分析表的算法 273
7．3．11 构造LR（0）分析表的步骤小结 275
7．4 SLR分析表的构造 275
7．5 规范LR分析表的构造 281
7．6 LALR分析表的构造 290
7．7 无二义性规则的使用 295
7．8 LR分析方法小结 299
7．8．1 LR分析程序 299
7．8．2 LR分析表的自动构造 299
7．8．3 文法间的关系 300
7．8．4 LR文法之区别举例 301
7．8．5 有关LR言语法的几个结论 304
练习 304
第八章 语法制导翻译法 306
8．1 一般原理 306
8．1．1 树变换 311
8．2 简单SDTS和自上而下翻译器 313
8．3 简单后缀SDTS和自下而上翻译器 318
8．3．1 后缀翻译 319
8．3．2 IF-THEN-ELSE控制语句 320
8．3．3 函数调用 321
8．4 抽象语法树的构造 323
8．4．1 自下而上构造AST 326
8．4．2 AST的拓广 327
8．5 属性文法 328
8．5．1 L属性文法 329
8．5．2 S属性文法 330
8．6 中间代码形式 330
8．6．1 逆波兰表示 330
8．6．2 逆波兰表示的推广 331
8．6．3 四元式 334
8．6．4 三元式 336
8．7 属性翻译文法的应用 337
8．7．1 综合属性与自下而上定值 337
8．7．2 继承属性和自上而下定值 338
8．7．3 布尔表达式到四元式的翻译 340
8．7．4 条件语句的翻译 342
8．7．5 迭代语句的翻译 344
练习 349
第九章 运行时的存贮组织与管理 350
9．1 数据区和属性字 351
9．2 基本数据类型的存贮分配 354
9．3 数组的存贮分配 354
9．3．1 单块存贮方式 354
9．3．2 信息向量与数组分配程序 357
9．3．3 多块存贮方式 359
9．4 记录结构的存贮分配 359
9．5 参数传递方式及其实现 361
9．5．1 换名 362
9．5．2 传值 363
9．5．3 传地址 363
9．5．4 传结果 364
9．5．5 数组名用作实参 365
9．5．6 过程名用作实参 365
9．6 栈式存贮分配法 365
9．6．1 概述 365
9．6．2 现行DISPLAY和现行数据区 367
9．6．3 标识符的作用域 370
9．6．4 分程序的入口和出口工作 371
9．6．5 过程调用时的存贮管理 375
9．7 FORTRAN存贮管理 379
9．8 堆式存贮分配方法 379
9．9 临时工作单元的存贮分配 381
练习 386
第十章 符号表的组织和查找 389
10．1 符号表的一般组织形式 389
10．2 符号表中的数据 390
10．3 符号表的构造与查找 392
10．3．1 线性查找 392
10．3．2 折半法 394
10．3．3 杂凑技术 395
10．4 分程序结构的符号表 399
练习 403
第十一章 优化 404
11．1 优化概述 404
11．2 基本块及其求法 404
11．3 优化举例 407
11．4 利用变量的定义点进行优化 411
11．4．1 变量的定义点 411
11．4．2 循环中不变式的外提 413
11．4．3 运算强度削弱 413
11．4．4 公共表达式的消除 414
11．4．5 常量合并 415
11．5 循环优化 417
11．6 借助DAG进行优化 418
11．7 并行分支的优化 421
11．8 窥孔优化 422
11．9 小结 423
练习 424
第十二章 化码生成 426
12．1 概述 426
12．2 假想的计算机模型 427
12．3 从四元式生成代码 428
12．4 从三元式生成代码 430
12．5 从树型表示生成代码 434
12．6 从逆波兰表示生成代码 438
12．7 寄存器的分配 440
练习 441
第十三章 翻译程序编写系统及并行编译系统 443
13．1 翻译程序编写系统 443
13．2 并行编译系统 445
习题解答 448