目 录 1
引论 1
0.1什么叫编译程序 1
0.2编译过程概述 1
0.3编译程序的结构 4
0.3.1编译程序总框 4
0.3.2表格与表格管理 5
0.3.3遍 7
0.4编译程序的生成 7
0.5学习构造编译程序 8
第一章高级程序语言概述 10
1.1程序语言的定义 10
1.1.1语言的词法和语法结构 10
1.1.2语义 11
1.2初等类型数据 12
1.2.1标识符和名字 13
1.2.2名字的属性和说明 13
1.3 数据结构 14
1.3.1数组 14
1.3.2记录结构 16
1.3.3字符串、表格和栈 17
1.4 表达式 17
1.5语句 19
1.5.1赋值句 19
1.5.2控制语句 20
1.5.3说明句 20
1.5.4简单句和复合句 20
1.6 程序段 20
1.6.1 FORTRAN 20
1.6.3 PASCAL 21
1.6.2 ALGOL 21
1.7 参数传递 22
1.7.1参数 22
1.7.2传地址 22
1.7.3传值 23
*1.7.4传名 24
1.8存储管理 24
1.8.1静态存储分配 24
1.8.2动态存储分配 24
1.8.3栈式动态存储分配 25
*1.8.4堆式动态存储分配 26
1.9 历史回顾 27
2.1.1词法分析器的功能和 29
输出形式 29
2.1对于词法分析器的要求 29
第二章词法分析 29
2.1.2词法分析器作为一个 30
独立子程序 30
2.2词法分析器的设计 30
2.2.1输入、预处理 31
2.2.2单词符号的识别： 32
超前搜索 32
2.2.3状态转换图 33
2.2.4 状态转换图的实现 36
*2.3正规表达式与有限自动机 38
2.3.1正规式与正规集 38
2.3.2确定有限自动机（DFA） 39
2.3.3非确定有限自动机（NFA） 41
2.3.4正规式与有限自动机的 41
等价性 41
2.3.5确定有限自动机的化简 45
*2.4词法分析器的自动产生 46
2.4.1语言LEX的一般描述 47
2.4.2超前搜索 49
2.4.3 LEX的实现 50
第三章程序语言的语法描述与 55
分析 55
3.1上下文无关文法 55
3.1.1文法与语言 55
3.1.2语法树与二义性 58
3.1.3形式语言鸟瞰 60
3.2 语法分析——自下而上 62
分析 62
3.2.1归约与分析树 63
3.2.2规范归约简述 65
3.2.3符号栈的使用与分析树的 67
表示 67
3.3算符优先分析法 68
3.3.1直观算符优先分析法 70
3.3.2算符优先文法和优先表构造 73
3.3.3算符优先分析算法的设计 76
3.3.4优先函数 78
3.4 语法分析——自上而下 80
分析 80
3.5递归下降分析法 82
3.5.1左递归的消除 83
3.5.2消除回溯、提左因子和递归 84
下降分析器 84
3.5.3文法的另一种表示法和转换图 86
3.5.4预测分析程序 88
3.5.5状态表 92
自动构造 98
4.1 LR分析器 98
*第四章语法分析程序的 98
4.1.1LR文法 101
4.1.2一些非LR结构 102
4.2 LR（0）项目集族和LR 103
（0）分析表的构造 103
4.2.1 LR（0）项目集规范族的构造 105
4.2.2有效项目 107
4.2.3 LR（0）分析表的构造 108
4.3SLR分析表的构造 109
4.4 规范LR分析表的构造 113
4.5 LALR分析表的构造 116
4.6二义文法的应用 123
4.7分析表的自动产生 126
4.7.1终结符和产生式的优先级 126
4.7.2结合规则 127
4.8 LR分析表的实际安排 128
第五章语法制导翻译和中间 132
代码产生 132
5.1语法制导翻译概说 132
5.2逆波兰表示法 135
5.2.1后缀式的计值 135
5.2.2后缀式的推广 136
5.2.3语法制导生成后缀式 137
5.3 三元式和树 137
5.3.1间接三元式 139
5.3.2树 139
5.4 四元式 140
5.5 简单算术表达式和赋值 141
句到四元式的翻译 141
5.6 布尔表达式到四元式的 144
翻译 144
5.6.1作为条件控制的布尔式翻译 145
5.7.1标号和转移语句 148
5.7控制语句的翻译 148
5.7.2条件语句 149
5.7.3循环语句 152
5.7.4分叉语句 154
5.8 数组元素引用 156
5.8.1数组元素引用的中间代码 157
5.8.2赋值句中数组元素的翻译 158
5.8.3按列为序存放数组元素 160
的情形 160
5.9过程调用 162
5.9.1过程调用的四元式产生 162
5.9.2过程调用和数组元素相混淆 163
的处理 163
5.10说明语句的翻译 163
*5.11记录结构 165
5.11.1记录说明的翻译 166
5.11.2记录结构的引用 167
5.12输入／输出语句的翻译 168
5.12.1 I/O语句的实现 168
5.12.2 I/O语句的翻译 170
5.12.3格式语句的处理 171
5.13 自上而下分析制导 172
翻译概说 172
第六章符号表 178
6.1 符号表的组织和使用 178
6.2整理与查找 180
6.2.1线性表 180
6.2.2对折查找与二叉树 181
6.2.3杂凑技术 183
6.3 名字的作用范围 185
6.3.1 FORTRAN的符号表组织 185
6.3.2 ALGOL的符号表组织 186
6.4符号表的内容 189
第七章运行时存储空间组织 193
7.1 静态存储管理——FORTRAN 193
存储分配 193
7.1.1数据区 194
7.1.2公用语句的处理 196
7.1.3等价语句的处理 197
7.1.4地址分配 200
7.1.5临时变量的地址分配 202
7.2一个简单的栈式存储分配 204
的实现 204
7.2.1 C的活动记录 205
7.2.2C的过程调用，过程进入， 205
数组空间分配和过程返回 205
7.3 嵌套过程语言的栈式实现 206
和活动记录 207
7.3.1 嵌套层次显示表DISPLAY 207
7.3.2过程调用，过程进入 208
7.3.3参数传递 209
7.4 ALGOL的实现 210
7.4.1分程序结构 211
7.4.2分程序的进入和退出 212
7.4.3过程调用，进入和返回 214
7.4.4参数子程序 215
7.5 分程序结构语言存储分配 216
拾遗 216
第八章错误的诊察和校正 219
8.1出错处理概述 219
8.1.1语法错误 220
8.1.2 语义错误 220
8.1.3错误处理 221
8.2词法分析阶段的错误诊察 222
8.1.4出错处理系统与编译程序 222
各阶段的联系 222
8.3 语法分析（自下而上）阶段 223
的错误诊察 223
8.3.1算符优先分析法的错误处理 223
*8.3.2 LR分析算法的错误处理 226
*8.4 自上而下分析的错误诊察 228
8.5语义错误诊察 231
8.5.1遏止株连信息 231
8.5.2遏止重复信息 231
第九章代码优化 233
9.1 优化概述 233
9.2 局部优化 236
其应用 237
9.3.1基本块的DAG表示 237
9.3 基本块的DAG表示及 237
9.3.2 DAG的应用 240
9.3.3 DAG构造算法讨论 242
9.4控制流程分析和循环 244
查找算法 244
9.4.1程序流图与循环 245
9.4.2必经结点集 246
9.4.3查找循环算法 248
9.4.4可归约流图 250
9.4.5深度为主查找及其算法 251
9.5 到达-定值与引用-定值链 253
9.5.1到达-定值数据流方程 253
9.5.2到达-定值数据流方程 255
的求解 255
9.5.3引用-定值链（ud链） 257
9.5.4 ud链的应用 257
9.6.1代码外提 258
9.6 循环优化 258
9.6.2强度削弱 261
9.6.3删除归纳变量 263
*第十章数据流分析 271
10.1 活跃变量与定值-引用链 271
（du链） 271
10.1.1活跃变量的数据流方程 271
10.1.2活跃变量数据流方程 272
的求解 272
10.1.3定值-引用链（du链） 273
10.1.4活跃变量与du链的应用 275
10.2 删除全局公共子表达式 275
10.2.1可用表达式及其数据流方程 275
的算法 278
10.2.3删除全局公共子表达式 278
10.2.2可用表达式数据流 278
方程的求解 278
10.3 复写传播 279
10.4 非常忙表达式和代码提升 281
10.4.1非常忙表达式数据流方程 283
10.4.2代码提升 284
10.5 四类数据流方程小结 285
10.6 实施各种优化的综合考虑 286
11.1一个计算机模型 293
第十一章代码生成 293
11.2一个简单代码生成器 294
11.2.1待用信息 294
11.2.2寄存器描述和地址描述 295
11.2.3代码生成算法 295
11.3寄存器分配 298
*11.4 DAG的目标代码 301
*11.5树的目标代码 303