目　录

第 1章　概论　1
1.1　编译程序概况　1
1.1.1　编译程序的引进　1
1.1.2　编译程序与程序设计语言的联系　3
1.1.3　编译原理课程的教学内容、教学目标和要求　6
1.2　编译程序的构造　6
1.2.1　编译程序的功能　6
1.2.2　编译程序的组成　7
1.2.3　编译程序的种类　8
1.3　编译程序的实现　9
1.3.1　编译程序实现要点　9
1.3.2　样本语言的轮廓　10
1.3.3　开发环境　11
本章小结　11
复习思考题　12

第 2章　编译程序构造的基础知识　13
2.1　符号串与符号串集合　13
2.2　文法与语言　16
2.2.1　文法及其应用　16
2.2.2　语言的概念　26
2.2.3　文法与语言的分类　27
2.3　句型分析　30
2.3.1　句型分析与语法分析树　30
2.3.2　二义性　33
2.3.3　分析技术及其分类　34
2.4　语法分析树的计算机生成　38
本章小结　40
复习思考题　41
习题　41

第3章　词法分析　42
3.1　概况　42
3.2　词法分析程序的手工实现　43
3.2.1　实现要点　43
3.2.2　属性字的设计　44
3.2.3　标识符的处理　47
3.2.4　词法分析程序的设计和编写　53
3.3　词法分析程序的自动生成　58
3.3.1　词法分析程序自动生成的基本思想　58
3.3.2　正则表达式　60
本章小结　70
复习思考题　71
习题　71

第4章　语法分析——自顶向下分析技术　72
4.1　自顶向下分析技术概况　72
4.1.1　讨论前提　72
4.1.2　自顶向下分析技术要解决的基本问题　73
4.1.3　自顶向下分析技术的实现思想与应用条件　73
4.1.4　消去左递归的文法等价变换　75
4.2　无回溯的自顶向下分析技术　79
4.2.1　应用条件　79
4.2.2　递归下降分析技术　80
4.2.3　预测分析技术　86
4.3　预测识别程序句型分析的计算机实现　94
4.3.1　预测分析表的存储表示　94
4.3.2　语法分析树的构造及输出　95
本章小结　97
复习思考题　97
习题　98

第5章　语法分析——自底向上分析技术　99
5.1　自底向上分析技术概况　99
5.1.1　讨论前提　99
5.1.2　基本实现方法　100
5.2　LR(1)分析技术　102
5.2.1　LR(1)分析技术与LR(1)文法　102
5.2.2　LR(1)识别程序的计算机实现　119
5.2.3　识别程序自动构造　122
5.3　其他的自底向上分析技术　126
5.3.1　算符优先分析技术概况　126
5.3.2　应用算符优先分析技术句型分析　128
5.3.3　优先函数　129
本章小结　130
复习思考题　130
习题　131

第6章　语义分析与目标代码生成　132
6.1　概况　132
6.1.1　语义分析的概念　132
6.1.2　属性与属性文法　134
6.1.3　语法制导定义与翻译方案的设计　141
6.1.4　类型表达式　149
6.2　说明部分的翻译　151
6.2.1　常量定义的翻译　152
6.2.2　变量说明的翻译　153
6.2.3　函数定义的翻译　156
6.2.4　结构类型的翻译　160
6.3　类型检查　161
6.3.1　表达式的类型检查　161
6.3.2　语句的类型检查　163
6.4　目标代码的生成　164
6.4.1　与目标代码生成相关的若干要点　165
6.4.2　虚拟机　168
6.4.3　控制语句的翻译　169
6.5　翻译方案的实现　195
6.5.1　实现要点　196
6.5.2　语义子程序及其执行　201
本章小结　205
复习思考题　206
习题　206

第7章　中间表示代码与代码优化　208
7.1　概况　208
7.1.1　代码优化与代码优化程序　208
7.1.2　代码优化的分类　209
7.2　源程序的中间表示代码　210
7.2.1　四元式序列　211
7.2.2　生成四元式序列的翻译方案的设计　213
7.2.3　从四元式序列生成目标代码　215
7.2.4　其他的中间表示代码　219
7.3　基本块的代码优化　222
7.3.1　基本块优化的种类　222
7.3.2　基本块优化的实现　225
7.4　与循环有关的优化　230
7.4.1　循环优化的种类　230
7.4.2　循环优化的基础　234
7.4.3　循环优化的实现　241
7.5　全局优化的实现思想　244
7.6　窥孔优化　245
7.6.1　冗余指令删除　246
7.6.2　控制流优化　247
7.6.3　代数化简　247
7.6.4　特殊指令的使用　247
本章小结　248
复习思考题　248
习题　248

第8章　程序错误的检查与校正　250
8.1　概述　250
8.1.1　程序错误检查的必要性　250
8.1.2　错误的种类　250
8.1.3　相关的基本概念　251
8.2　词法错误的复原与校正　252
8.2.1　词法错误的种类　252
8.2.2　词法错误的校正　253
8.3　语法错误的复原与校正　253
8.3.1　语法错误的复原　253
8.3.2　语法错误的校正　254
8.4　语义错误　255
8.4.1　语义错误的种类　255
8.4.2　语义错误检查措施　256
本章小结　258
复习思考题　258
习题　258

第9章　目标代码的运行　259
9.1　概述　259
9.2　运行时刻的存储管理　260
9.2.1　变量情况分析　260
9.2.2　静态存储分配　262
9.2.3　栈式存储分配　262
9.2.4　堆式存储分配　262
9.3　符号表　263
9.3.1　符号表的组织　263
9.3.2　符号表的数据结构　267
9.4　运行时刻支持系统　268
本章小结　269
复习思考题　269
习题　270

第 10章　虚拟机目标程序的解释程序的研制　271
10.1　虚拟机指令操作码种类　271
10.2　设计要点　273
10.2.1　操作数的处理　273
10.2.2　控制转移指令的处理　274
10.2.3　操作码的确定与模拟执行　275
10.2.4　输入输出指令的处理　275
10.3　数据结构设计　276
10.4　符号模拟执行虚拟机目标程序的解释程序　276
本章小结　281
复习思考题　281

参考文献　282