张幸儿，南京大学计算机科学与技术系教授，长期从事教学和科研工作，参与多个编译程序和软件项目的研制，长期从事编译原理、程序设计等课程的教学。有丰富的教学经验和计算机软件开发经验。多次获得省部级科研与优秀教材奖，其中《计算机编译理论》和《计算机编译原理》分别获得教育部普通高校优秀教材二等奖。
    戴新宇，南京大学计算机科学与技术系副教授，博士，研究方向是自然语言处理，多次讲授计算机编译原理课程。

    《编译原理：编译程序构造与实践教程》系统而简洁地介绍编译程序的构造原理，内容主要包括概论、编译程序构造的基础知识、词法分析、语法分析、语义分析与目标代码生成、中间表示代码与代码优化、程序错误的检查与校正、目标代码的运行，以及虚拟机目标程序的解释程序的编制。各章开始于本章导读，各章末有本章小结、复习思考题以及习题。《编译原理：编译程序构造实践教程》突出实践性，在编译程序构造的各个环节中，提供了具体可行的实现方法和技巧，供读者参考。
    《编译原理：编译程序构造与实践教程》可作为计算机及相关专业的编译原理课程教材，也可作为计算机软件技术人员、研究生及广大计算机爱好者的参考用书。

    ②语法分析。词法分析时识别开各个符号之后，由语法分析部分根据程序设计语言的语法规则，识别出各个语法成分，最终识别出完整的程序。在识别各类语法成分的同时，也就检查了语法的正确性。当识别出是语法上正确的程序时，生成相应的内部中间表示（通常是语法分析树或其他内部中间表示），如果存在错误，则给出相应的报错信息。
    完成语法分析的部分称为语法分析程序，或称为识别程序。概括起来，语法分析程序的功能是识别出各个语法成分，生成相应的内部中间表示，同时进行语法正确性的检查。
    ③语义分析。编译程序继语法分析之后进行语义分析，即基于语法分析时输出的内部中间表示，依据各个语法成分的含义进行语义分析。由于一个程序通常由数据结构和控制结构两部分组成，必然对这两部分进行语义分析。对于数据结构，语义分析部分进行的语义分析工作是确定类型和类型检查，确切地说，检查标识符是否有定义，确定标识符所对应数据对象的数据类型等属性，检查运算的合法性及运算分量数据类型的一致性；对于控制结构，根据程序设计语言所规定的语义，对它们进行相应的语义处理，这时可以生成相应的目标代码。例如，对于一个加法运算，当检查了两个运算分量都有定义，它们都能进行加法运算（运算是合法的），且两个运算分量的类型一致（相容）时，可以生成进行加法的目标代码。不言而喻，执行语义分析的同时，还进行一些语义检查，当然这只是静态语义检查，即在编译时刻所能进行的语义检查，例如，检查是否从循环外通过控制转移语句把控制转入循环体。在运行时刻才能进行的语义检查称为动态语义检查，如检查数组元素下标是否越界，以及指针变量是否有初值等，自然不在语义分析时刻进行。为了改进目标程序质量，语义分析时可能不生成目标代码，而是生成另外一种内部中间表示，或称中间表示代码。代码优化阶段就是基于这种中间表示代码进行优化，然后再从优化了的中间表示代码生成目标代码。语义分析工作通常由语义子程序完成。
    完成语义分析的部分称为语义分析程序。概括起来，语义分析程序的功能是确定类型、类型检查、识别含义与相应语义处理，以及其他一些静态语义检查等。
    ④代码优化。代码优化指的是为改进目标程序质量而在编译时刻进行的各项优化工作。代码优化通常基于语义分析部分生成的中间表示代码进行，把它变换成功能相同、但功效更高的优化了的中间表示代码。本书的中间表示代码主要是四元式序列。代码优化有与机器无关的优化和与机器有关的优化之分。本书重点讨论与机器无关的优化。除了对中间表示代码进行优化外，也可以对目标代码进行优化，这种优化通常称为窥孔优化。窥孔优化是机器语言级上仅在一个很小的范围内进行的、不太复杂因而代价不是很高的一类优化。
    当前的很多高级程序设计语言的编译程序都进行代码优化，c语言编译程序是突出的优化典型。
    完成代码优化的部分称为代码优化程序。概括起来，代码优化程序的功能是：在编译时刻基于中间表示代码进行目标程序质量的改进。
    ⑤目标程序生成。如前所述，语义分析时可以直接生成目标程序，这里的目标程序生成指的是基于优化了的中间表示代码（也即四元式序列）生成目标程序。目标程序的生成与运行目标程序的计算机密切相关。为了学习的目的，本书避免把大量的时间花在对具体计算机细节的了解上，将基于一种所谓的虚拟机来讨论目标程序的生成。

第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