第1章 绪论 1
1.1语言翻译与编译程序 1
1.2编译器与解释器 1
1.3编译程序的工作原理与基本结构 2
1.3.1高级语言的主要成分 2
1.3.2编译的基本过程 4
1.3.3编译程序各阶段的工作 4
1.3.4编译程序的基本结构 6
1.3.5编译的前端和后端 7
1.3.6编译的遍数 7
1.4编译器的编写 8
1.5本章小结 8
习题1 9
第2章 词法分析 12
2.1词法分析概述 12
2.1.1相关问题 12
2.1.2词法分析器的功能和工作方式 14
2.1.3源程序的输入及预处理 15
2.2模式的形式化描述 16
2.2.1语言及其基本概念 16
2.2.2正规式与正规集 18
2.2.3记号的定义 20
2.3有限自动机 21
2.3.1有限自动机概述 21
2.3.2状态转换图 21
2.3.3非确定型有限自动机（NFA） 23
2.3.4确定型有限自动机（DFA） 24
2.4正规式到词法分析器 26
2.4.1由正规式构造等价的非确定型有限自动机（NFA） 26
2.4.2非确定型有限自动机（NFA）到确定型有限自动机（DFA）的变换 30
2.4.3确定型有限自动机（DFA）的化简 31
2.5词法分析器的自动生成 33
2.6本章小结 35
习题2 35
第3章 语法分析 38
3.1上下文无关文法（CFG） 38
3.1.1上下文无关文法的定义 38
3.1.2语法分析的基本术语 39
3.1.3语法树和二义性 41
3.1.4文法与语言的分类 42
3.2自上而下的语法分析 43
3.2.1自上而下语法分析的一般方法和基本问题 44
3.2.2消除文法的左递归 45
3.2.3消除回溯提取左因子 46
3.2.4递归下降分析法 47
3.2.5预测分析法 51
3.3自下而上的语法分析 56
3.3.1自下而上语法分析的一般方法和基本问题 56
3.3.2符号栈的使用 58
3.3.3 LR分析法 59
3.3.4 LR（0）项目集族和LR（0）分析表的构造 62
3.3.5 LR（0）项目集规范族的构造 65
3.3.6有效项目 66
3.3.7 LR（0）分析表的构造 67
3.3.8 SLR分析表的构造 68
3.3.9规范LR分析表的构造 73
3.3.10 LALR分析表的构造 76
3.4二义文法的应用 83
3.5语法分析器的自动生成工具YACC简介 86
3.6本章小结 87
习题3 88
第4章 语法制导翻译与中间代码生成 92
4.1语法制导翻译 92
4.1.1语法与语义 92
4.1.2属性文法 93
4.1.3语义规则 95
4.1.4 LR分析的翻译概述 97
4.1.5递归下降分析的翻译概述 98
4.2中间代码 99
4.2.1后缀式 100
4.2.2三地址码 100
4.2.3图形表示 104
4.3说明性语句的翻译 105
4.3.1变量和数组变量的声明 105
4.3.2过程的定义、声明和过程调用的处理 111
4.3.3记录中的域名 113
4.4执行性语句的翻译 113
4.4.1赋值语句的翻译 113
4.4.2布尔表达式的翻译 118
4.4.3控制语句的翻译 123
4.4.4过程调用 127
4.4.5类型检查 128
4.5本章小结 128
习题4 129
第5章 自动机的应用 132
5.1有限自动机在自动控制软件设计中的应用 133
5.1.1有限自动机的基本特征 133
5.1.2用有限自动机进行软件设计的方法 133
5.1.3自动控制程序设计举例 134
5.2对KMP算法的一个改进 135
5.2.1问题的提出 135
5.2.2对KMP算法的改进 136
5.2.3时间复杂度分析 137
5.3移动通信营业系统中的自动机模型 138
5.3.1系统概述 138
5.3.2数据库设计 138
5.4图形识别的有限自动机方法 140
5.4.1问题的提出 140
5.4.2使用DFA进行图形识别 140
5.4.3 DFA的实现 142
5.4.4应用效果 142
5.5基于广义有限自动机的图像压缩方法 142
5.5.1问题背景 142
5.5.2图像的有限自动机表示 142
5.5.3灰度图像及有限自动机的构造 143
5.5.4广义自动机（GFA）及压缩算法 144
5.5.5实验结果及结论 145
5.6本章小结 146
习题5 146
第6章 符号表与运行时环境 149
6.1符号表 149
6.1.1符号表的组织与作用 149
6.1.2符号表的建立与查找 151
6.1.3作用域规则 152
6.2目标程序运行时环境 153
6.2.1过程与活动 153
6.2.2活动记录 154
6.2.3名字绑定 155
6.3目标程序运行时存储器的划分及存储分配策略 157
6.3.1存储器的划分 157
6.3.2存储分配策略 157
6.4本章小结 164
习题6 164
第7章 代码优化与代码生成 166
7.1代码优化 166
7.1.1局部优化 166
7.1.2循环优化 169
7.1.3循环优化举例 171
7.2代码生成的实现过程 172
7.3简单的代码生成器 177
7.3.1基本块、流图和循环 177
7.3.2寄存器分配 180
7.3.3目标代码生成算法 181
7.4 DAG的代码生成 182
7.4.1基本块的DAG表示 182
7.4.2 DAG的代码生成 186
7.5本章小结 187
习题7 187
参考文献 192