第1章 引论 1
1.1 程序设计语言的发展 1
1.1.1 程序设计语言 1
1.1.2 翻译程序 1
1.2 为什么需要编译程序 2
1.3 编译程序的工作过程 4
1.3.1 分析部分 5
1.3.2 综合部分 6
1.4 编译程序的结构 6
1.4.1 编译程序的典型结构 6
1.4.2 编译程序的前端和后端 6
1.4.3 编译程序的分遍 7
1.4.4 源程序中的错误及出错处理 8
1.5 编译程序的组织方式 8
1.6 编译程序的其他技术 9
1.6.1 编译程序的自展技术 9
1.6.2 编译程序的移植技术 9
1.6.3 编译程序的自动化技术 10
1.6.4 程序的可再入性 10
1.7 翻译程序的编写系统 11
1.8 并行编译程序 12
1.9 小结 13
习题 14
第2章 形式语言概论 15
2.1 语言成分 15
2.2 文法和语言 17
2.2.1 产生式文法 17
2.2.2 上下文无关文法 17
2.2.3 推导与直接推导 18
2.3 文法的分类 19
2.3.1 文法分类 19
2.3.2 文法分类的意义 21
2.3.3 文法举例 22
2.4 语言和语法 23
2.4.1 句型、句子和语言 23
2.4.2 语法树 24
2.4.3 产生式树和产生式图 25
2.5 文法和语言的一些特性 26
2.5.1 无用非终结符号 26
2.5.2 不可达文法符号 26
2.5.3 可空非终结符 27
2.5.4 最左推导、最右推导和规范推导 28
2.5.5 二义性 29
2.6 分析方法简介 30
2.6.1 自顶向下分析方法 30
2.6.2 确定的自顶向下分析方法 32
2.6.3 自底向上分析方法 33
2.6.4 文法在内存中的表示 34
2.7 小结 36
习题 36
第3章 有穷自动机 38
3.1 概述 38
3.2 有穷自动机的定义 40
3.2.1 状态转换表 40
3.2.2 状态转换图 41
3.2.3 构形和移动 42
3.2.4 自动机的等价性 42
3.2.5 非确定有穷自动机 42
3.3 NDFSA到DFSA的转换 44
3.3.1 空移环路的寻找和消除 44
3.3.2 确定化——子集法 45
3.3.3 确定化——造表法 46
3.3.4 消除不可达状态 48
3.3.5 确定有穷自动机的化简 48
3.3.6 从化简后的DFSA到程序表示 50
3.4 正规文法与有穷自动机 51
3.4.1 从正规文法到FSA 52
3.4.2 从FSA到正规文法 52
3.5 正规表达式与FSA 53
3.5.1 正规表达式的定义 53
3.5.2 正规表达式到NDFSA的转换 55
3.5.3 NDFSA M到正规表达式的转换 56
3.5.4 从正规文法到正规表达式 57
3.6 DFSA在计算机中的表示 58
3.6.1 矩阵表示法 58
3.6.2 表结构表示法 58
3.6.3 程序表示法 59
3.7 小结 59
习题 60
第4章 词法分析 62
4.1 单词符号 62
4.2 词法分析程序的设计 63
4.2.1 预处理 63
4.2.2 状态转换图 63
4.2.3 根据状态转换图设计词法分析程序 64
4.2.4 由正规文法设计词法分析程序 66
4.2.5 由正规表达式设计词法分析程序 66
4.2.6 设计词法分析程序的直接方法 67
4.3 标识符的处理 68
4.3.1 类型的机内表示 68
4.3.2 标识符的语义表示 68
4.3.3 符号表 68
4.3.4 标识符处理的基本思想 68
4.4 词法错误及其处理 69
4.5 小结 69
习题 70
第5章 自顶向下语法分析 71
5.1 非确定的下推自动机 71
5.1.1 PDA的形式定义 72
5.1.2 PDA的构形和移动 73
5.1.3 上下文无关语言与PDA 74
5.2 消除左递归的方法 76
5.2.1 文法的左递归性 76
5.2.2 用扩展的BNF表示法消除左递归 77
5.2.3 直接改写法 78
5.2.4 消除左递归的算法 79
5.3 LL（k）文法 80
5.3.1 LL（l）文法的判断条件 80
5.3.2 集合FIRST、FOLLOW与SELECT的构造 81
5.4 确定的LL（l）分析器的构造 83
5.4.1 分析表M的构造算法 84
5.4.2 LL（l）分析器的总控算法 86
5.5 递归下降分析程序及其设计 87
5.5.1 递归下降分析程序 87
5.5.2 流程图设计 88
5.5.3 程序设计 89
5.6 小结 90
习题 90
第6章 自底向上分析和优先分析方法 93
6.1 短语和句柄 93
6.2 移进-归约方法 95
6.3 非确定的自底向上分析器 96
6.4 有关文法的一些关系 100
6.4.1 关系 100
6.4.2 布尔矩阵和关系 101
6.4.3 Warshall算法 102
6.4.4 关系FIRST与LAST 103
6.5 简单优先分析方法 105
6.5.1 简单优先关系 105
6.5.2 简单优先关系的形式化构造方法 107
6.5.3 简单优先文法及其分析算法 108
6.5.4 简单优先分析方法的局限性 110
6.6 算符优先分析方法 111
6.6.1 算符优先文法 111
6.6.2 OPG优先关系的构造 111
6.6.3 素短语及句型的分析 113
6.6.4 算符优先分析算法 113
6.7 优先函数及其构造 115
6.7.1 Bell方法 116
6.7.2 Floyd方法 117
6.7.3 两种方法的比较 118
6.8 小结 119
习题 120
第7章 自底向上的LR（k）分析方法 122
7.1 LR（k）文法和LR（k）分析器 122
7.2 LR（0）分析表的构造 125
7.2.1 规范句型的活前缀和LR（0）项目 125
7.2.2 拓广文法和CLOSURE（I）函数 126
7.2.3 goto（I,X）函数和LR（0）项目集规范族 126
7.2.4 有效项目 128
7.2.5 举例 129
7.2.6 LR（0）文法和构造LR（0）分析表的算法 132
7.3 SLR分析表的构造 133
7.4 规范LR（l）分析表的构造 136
7.5 LALR分析表的构造 140
7.6 无二义性规则的使用 144
7.7 小结 145
习题 146
第8章 语法制导翻译法 147
8.1 基本原理和树变换 147
8.1.1 基本原理 147
8.1.2 树变换 149
8.2 简单SDTS和自顶向下翻译器 150
8.3 简单后缀SDTS和自底向上翻译器 152
8.3.1 后缀翻译 153
8.3.2 条件语句的处理 153
8.3.3 函数调用的处理 154
8.4 抽象语法树的构造 155
8.4.1 自底向上构造AST 156
8.4.2 AST的拓广 157
8.5 属性文法 157
8.5.1 L属性文法 158
8.5.2 S属性文法 158
8.6 中间代码形式 158
8.6.1 逆波兰表示法 159
8.6.2 逆波兰表示法的推广 159
8.6.3 四元式 160
8.6.4 三元式 161
8.7 属性翻译文法的应用 162
8.7.1 综合属性与自底向上定值 162
8.7.2 继承属性和自顶向下定值 163
8.7.3 布尔表达式到四元式的翻译 164
8.7.4 条件语句的翻译 164
8.7.5 迭代语句的翻译 165
8.8 小结 167
习题 168
第9章 运行时的存储组织与管理 170
9.1 存储分配基础知识 170
9.1.1 运行时刻的存储区域 170
9.1.2 过程活动与过程的活动记录 170
9.1.3 静态层次、静态外层和动态外层 171
9.1.4 名字的作用域和生存期 172
9.1.5 名字的静态属性和动态属性 173
9.1.6 常见数据类型的存储分配 173
9.2 典型的存储分配方案 174
9.2.1 静态存储分配方案 174
9.2.2 动态存储分配方案 175
9.2.3 存储分配时需考虑的问题 175
9.3 参数传递方式及其实现 176
9.3.1 传地址 176
9.3.2 传值 177
9.3.3 传结果 177
9.3.4 传名 177
9.4 栈式存储分配 178
9.4.1 概述 178
9.4.2 简单栈式存储分配 179
9.4.3 嵌套结构语言的栈式存储分配 180
9.4.4 过程调用时的存储管理 183
9.4.5 PL/0栈式存储分配 183
9.5 堆式存储分配方法 184
9.6 小结 185
习题 185
第10章 符号表 187
10.1 概述 187
10.1.1 符号表的地位与作用 187
10.1.2 符号表的生存期 188
10.2 符号表的内容 188
10.3 符号表的组织 189
10.3.1 符号表的数据结构 189
10.3.2 符号表的内容组织 189
10.4 栈式符号表 190
10.4.1 栈式符号表概述 190
10.4.2 栈式符号表举例 191
10.5 小结 194
习题 194
第11章 优化 196
11.1 控制流图 197
11.2 常见的冗余 199
11.2.1 公共子表达式 200
11.2.2 复制传播 201
11.2.3 活跃变量分析及死代码删除 202
11.3 循环优化 203
11.3.1 代码外提 203
11.3.2 归纳变量与强度削弱 206
11.3.3 循环展开 208
11.3.4 指令调度 209
11.4 小结 210
习题 211
第12章 代码生成 213
12.1 概述 213
12.1.1 目标代码形式 213
12.1.2 目标代码生成的主要问题 213
12.1.3 寄存器分配的原则 214
12.2 PL/0抽象计算机模型 214
12.2.1 PL/0抽象计算机的代码 214
12.2.2 PL/0语言目标代码举例 215
12.3 目标代码结构 216
12.3.1 目标代码结构的设计 216
12.3.2 常见语法成分目标代码结构设计 217
12.4 PL/0编译程序的目标代码生成 218
12.4.1 PL/0编译程序中的相关定义 218
12.4.2 基本语句的翻译 219
12.4.3 过程的翻译 221
12.4.4 目标代码生成举例 223
12.5 小结 228
习题 229
附录 PL/0编译程序源程序 230
参考文献 247