第一章 引论 1
1．1翻译程序 1
1．2为什么需要编译程序 3
1．2．1模块性 4
1．2．2静态解释与动态解释 5
1．2．3机器无关性 6
1．2．4程序语言特征 8
1．3编译程序的开销 8
1．4编译过程简介 9
1．5翻译程序的观点 15
1．6小结 16
第二章 形式语言理论介绍 18
2．1语言成分 18
2．1．1符号与字母表 19
2．1．2串 20
2．2产生式文法和语言 21
2．2．1产生式规则、文法 21
2．2．2文法分类 23
2．2．3文法分类的意义 28
2．2．4句型、句子和语言 29
2．2．5推导树和产生式树 30
2．2．6文法的一些特性 38
2．2．7规范推导 40
2．2．8二义性 44
2．3分析方法介绍 46
2．3．1自上而下分析 46
2．3．2确定的自上而下分析器 49
2．3．3确定的自下而上分析器 53
练习 56
第三章 有穷自动机 62
3．1概述 62
3．2 FSA的形式定义 66
3．2．1状态转换表 67
3．2．2状态转换图 68
3．2．3构形和移动 68
3．2．4自动机的等价性 69
3．2．5非确定的有穷自动机 70
3．3 NDFSA到DFSA的转换 72
3．3．1空移环路的寻找和删除 73
3．3．2消除空移 74
3．3．3从NDFSA到DFSA（确定化） 80
3．3．4消除不可达状态 83
3．3．5确定的有穷自动机的化简 84
3．3．6小结 88
3．4正规文法与有穷自动机 88
3．4．1从正规文法到FSA 89
3．4．2从FSA到正规文法 90
3．5正规表达式与FSA 91
3．5．1正规表达式的定义 91
3．5．2正规表达式的CFG 93
3．5．3正规表达式与FSA的对应性 94
3．5．4从正规文法到正规表达式 102
3．6 DFSA在计算机中的表示 106
3．7词法分析 109
3．7．1词法分析概述 109
3．7．2单词符号 110
3．7．3扫描程序的设计 111
3．7．4与设计扫描程序相关的几个问题 119
练习 120
第四章 语法分析——自上而下分析 125
4．1非确定的下推自动机 126
4．1．1 PDA的形式定义 126
4．1．2 PDA的构形和移动 129
4．1．3上下文无关语言与PDA 132
4．2 LL（k）文法 136
4．2．1有关LL（1）文法的转换技术 137
4．2．2 LL（1）文法的判断条件 141
4．3确定的LL（1）分析器的构造 145
4．3．1构造分析表M的算法 146
4．3．2 LL（1）分析器的总控算法 148
4．4 LL（k）文法的几个结论 150
4．5递归下降分析程序及其设计 150
练习 154
第五章 自下而上分析和优先分析方法 157
5．1概述 157
5．2短语和句柄 91
5．3非确定的自下而上分析器 161
5．3．1拓广的PDA与上下文无关语言的等价性 163
5．4有关文法的一些关系 167
5．4．1关系 167
5．4．2布尔矩阵和关系 170
5．4．3 Warshall算法 173
5．5简单优先分析方法 173
5．5．1优先关系 173
5．5．2优先关系的形式定义及构造 176
5．5．3简单优先文法及其分析算法 178
5．5．4优先函数及其构造 181
5．6算符优先分析方法 184
5．6．1算符优先文法 184
5．6．2 OPG优先关系的构造 186
5．6．3素短语及句型的分析 187
练习 189
第六章 自下而上的LR（k）分析方法 192
6．1 LR（k）分析法概述 192
6．2 LR（k）文法和LR（k）分析器 193
6．3 LR（0）项目集规范族 199
6．4有效项目 205
6．5 SLR分析表的构造 207
6．6规范LR分析表的构造 211
6．7 LALR分析表的构造 220
6．8无二义性规则的使用 226
6．9有关LR分析的几个结论 229
练习 229
第七章 语法制导翻译法 231
7．1一般原理 231
7．1．1树变换 236
7．2简单SDTS和自上而下翻译器 238
7．3简单后缀SDTS和自下而翻译器 243
7．4抽象语法树的构造 248
7．4．1自下而上构造AST 251
7．4．2 AST的拓广 252
7．5属性文法 253
7．6中间代码形式 255
7．6．1逆波兰表示 255
7．6．2逆波兰表示式的推广 256
7．6．3四元式 258
7．6．4三元式 260
7．7属性翻译文法的应用 262
7．7．1综合属性与自下而上定值 262
7．7．2继承属性和自上而下定值 263
7．7．3迭代语句的翻译 265
练习 269
第八章 运行时的存贮组织与管理 271
8．1数据区和属性字 272
8．2基本数据类型的存贮分配 275
8．3数组的存贮分配 275
8．3．1单块存贮方式 275
8．3．2信息向量与数组分配程序 278
8．3．3多块存贮方式 280
8．4记录结构的存贮分配 280
8．5参数传递方式及其实现 282
8．5．1换名 283
8．5．2传值 284
8．5．3传地址 284
8．5．4传结果 285
8．5．5数组名字用作实参 286
8．5．6过程名字用作实参 286
8．6栈式存贮分配法与ALGOL存贮管理 286
8．6．1概述 286
8．6．2现行DISPLAY和现行数据区 288
8．6．3标识符的作用域 290
8．6．4分程序的进口和出口工作 291
8．6．5过程调用时的存贮管理 295
8．7 FORTRAN存贮管理 298
8．8堆式存贮分配方法介绍 299
8．9临时工作单元的存贮分配 300
练习 305
第九章 符号表的组织与查找 308
9．1符号表的一般组织形式 308
9．2符号表中的数据 309
9．3符号表的构造与查找 311
9．3．1线性查找 311
9．3．2折半法 313
9．3．3杂凑技术 314
9．4分程序结构的符号表 318
练习 321
第十章 优化 323
10．1优化概述 323
10．2优化举例 324
10．3使用变量的定义点进行优化 328
10．3．1变量的定义点 328
10．3．2循环中不变式的外提 330
10．3．3运算强度削弱 330
10．3．4公共子表达式的消除 330
10．3．5常量合并 332
10．4窥孔优化 334
10．5小结 334
练习 335
第十一章 代码生成 337
11．1假想的计算机模型 338
11．2从四元式生成代码 339
11．3从三元式生成代码 341
11．4从树型表示生成代码 345
11．5从逆波兰表示生成代码 348
11．6寄存器的分配 350
练习 352
第十二章 翻译程序编写系统介绍 353
参考文献 355