本书主要介绍设计和构造编译程序的基本原理和方法，内容包括适合于计算机高级程序设计语言翻译的形式语言和自动机理论、常用的词法分析方法、各种经典的语法分析方法、语法制导翻译方法、存储器的组织与管理方法、符号表的组织与造查表方法、代码优化和代码生成方法、并行编译程序及编译自动化技术等。
编译原理
何炎祥 伍春香 王汉飞 编著
本书主要内容
编译程序是计算机最重要的系统软件之一，是高级程序设计语言的支撑基础。本书主要介绍设计和构造编译程序的基本原理和典型方法。特别注重理论与实践、原理与方法的互通，而且基本概念清晰，深入浅出，循序渐进，系统性强。各章之后还附有难度不一的习题供读者复习、思考和探索。本书既可作为高等院校计算机专业的教材，也可供有关师生和科技工作者及软件研发人员学习和参考。
作者简介
何炎祥 教授、博士生导师，武汉大学计算机学院院长。主要研究方向为：分布并行处理（含移动计算与Web服务）、可信软件、数据挖掘和软件工程等。主持和主要承担的科研项目包括863高技术计划项目、国家自然科学基金重大研究计划项目、国家自然科学基金面上项目、省市科技攻关项目等40余项，发表论文200多篇，出版著作和教材15部。主讲课程“编译原理”于2005年被评为国家精品课。获包括湖北省科技进步一等奖在内的省部级科技成果和教学成果奖多项，并获国家教学名师、宝钢优秀教师奖、湖北省青少年科技教育工作先进个人、湖北省优秀研究生导师等。享受国务院政府特殊津贴。
伍春香 副教授，硕士生导师。主要从事与编译、人工智能相关的教学和科研工作。
王汉飞 武汉大学计算机学院副教授。主要研究方向为程序设计理论。长期从事“编译原理”课程教学。
编译程序(Compiler)是计算机的重要系统软件，是高级程序设计语言的支撑基础。本书主要介绍设计和构造编译程序的基本原理和方法。
本书共分12章。第1章讲述编译程序的功能、结构、工作过程、组织方式、编译程序与高级语言的关系以及编译自动化方面的基本知识。
第2章介绍形式语言理论，我们仅仅给出了便于理解、有助于研究各种分析方法和设计构造编译程序的形式语言理论，并着重介绍上下文无关文法。
有穷自动机是描述词法的有效工具，也是进行词法分析的主要理论基础。因此，第3章专门介绍有穷状态自动机，它与正规文法、正规表达式之间的对应关系以及它的确定化和最小化方面的知识。第4章讨论词法分析程序的设计方法。
上下文无关文法可用于描述现今大多数高级程序设计语言的语法，也是语法分析的主要理论支柱。为此，在接下来的几章里，主要讨论与上下文无关文法相关的各类语法分析方法。
第5章介绍自顶向下分析方法，包括LL(k)文法、LL(1)分析方法和应用十分广泛的递归下降分析方法。第6章讨论自底向上分析方法的一般原理和优先分析方法，包括简单优先分析技术和算符优先分析方法。第7章专门讨论自底向上的LR(k)分析方法，包括LR(0)、SLR(1)、规范LR(1)以及LALR(1)分析表的构造算法。
第8章介绍语法制导翻译方法（SDTS），主要讨论SDTS的基本原理、属性翻译文法及其在中间代码生成中的应用。
第9章讨论运行时的存储组织与管理，其中考虑了一些重要的语言特征，如过程调用、参数传递、数组和记录的存取方式以及多种存储分配技术。
第10章讨论符号表的组织和存取符号表的各种方法。第11章介绍常用的优化方法。第12章主要通过与具体机器无关的PL/0语言的目标代码生成过程，讨论了代码生成的原理。考虑到完整性，我们在附录中给出了PL/0编译程序源程序。
“编译原理”这门课程是计算机专业的主干课和必修课，也是计算机专业高年级课程中较难学习的一门课程，其先导课程是汇编语言程序设计、计算机组成原理、数据结构、高级语言程序设计和离散数学等。
本课程的参考学时数72，教师可根据具体情况对教材内容进行取舍，例如，工科院校的学生可略过第7、8章并可精减第2、3章的内容，从而使授课学时数减至54。教师在讲授本课程的同时应加强并引导学生做好该课程实践方面的规划和检验。
本书特别注重设计和构造编译程序的理论与实践、原理与方法的互通，而且基本概念清晰，深入浅出，循序渐进，系统性强。每章之后还附有难度不一的习题供学生复习、思考和探索。本书既可作为高等院校计算机专业的教材，也可供有关师生和科技工作者及软件开发人员学习和参考。
本书的第9、10、12章和附录由伍春香编写，第11章由王汉飞编写，其余各章由何炎祥编写。何炎祥和王汉飞最后统稿。本书是在我们已经出版的几本编译原理教材的基础上经过适当修订而成。在修订过程中得到了原合作者的全力支持。此外，书中引用了一些专家学者的论著和研究成果，以及一些公司的产品介绍，在此一并表示真诚的感谢。
限于水平，书中错误难免，敬请读者指正。
何炎祥
2008年8月修订于江西庐山，2009年8月审改于武汉珞珈山
本书主要内容
编译程序是计算机的最重要系统软件之一，是高级程序设计语言的支撑基础。本书主要介绍设计和构造编译程序的基本原理和典型方法。特别注重理论与实践、原理与方法的互通，而且基本概念清晰，深入浅出，循序渐进，系统性强。各章之后还附有难度不一的习题供读者复习、思考和探索。本书既可作为高等院校计算机专业的教材，也可供有关师生和科技工作者及软件研发人员学习和参考。
作者简介
何炎祥 教授、博士生导师，武汉大学计算机学院院长。主要研究方向为：分布并行处理（含移动计算与Web服务）、可信软件、数据挖掘和软件工程等。主持和主要承担的科研项目包括863高技术计划项目、国家自然科学基金重大研究计划项目、国家自然科学基金面上项目、省市科技攻关项目等40余项，发表论文200多篇，出版著作和教材15部。主讲课程“编译原理”于2005年被评为国家精品课。获包括湖北省科技进步一等奖在内的省部级科技成果和教学成果奖多项，并获国家教学名师、宝钢优秀教师奖、湖北省青少年科技教育工作先进个人、湖北省优秀研究生导师等。享受国务院政府特殊津贴。
伍春香 副教授，硕士生导师。主要从事与编译、人工智能相关的教学和科研工作。
王汉飞 武汉大学计算机学院副教授。主要研究方向为程序设计理论。长期从事“编译原理”课程教学。
近20年里，计算机学科有了很大的发展，人们普遍认为，“计算机科学”这个名字已经难以涵盖该学科的内容，因此，改称其为计算学科（Computing Discipline）。在我国本科教育中，1996年以前曾经有计算机软件专业和计算机及应用专业，之后被合并为计算机科学与技术专业。2004年以来，教育部计算机科学与技术专业教学指导分委员会根据我国计算机专业教育和计算学科的现状，为更好地满足社会对计算机专业人才的需求，发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称《规范》），提出在计算机科学与技术专业名称之下，构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类，在于鼓励办学单位根据自己的情况设定不同的培养方案，以培养更具针对性和特色的计算机专业人才。
为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：
（1） 体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。
（2） 围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。
（3） 教材内容的组织科学、合理，体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。
（4） 教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。
（5） 开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。
我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。
“面向计算机科学与技术专业规范系列教材”编委会
出版者的话
序 言
前 言
教学建议
第1章 引论1
1.1 程序设计语言的发展1
1.1.1 程序设计语言1
1.1.2 翻译程序1
1.2 为什么需要编译程序2
1.3 编译程序的工作过程4
1.3.1 分析部分5
1.3.2 综合部分6
1.4 编译程序的结构6
1.4.1 编译程序的典型结构6
1.4.2 编译程序的前端和后端6
1.4.3 编译程序的分遍7
1.4.4 源程序中的错误及出错处理8
1.5 编译程序的组织方式8
1.6 编译程序的其他技术9
1.6.1 编译程序的自展技术9
1.6.2 编译程序的移植技术9
1.6.3 编译程序的自动化技术10
1.6.4 程序的可再入性10
1.7 翻译程序的编写系统11
1.8 并行编译程序12
1.9 小结13
习题14
第2章 形式语言概论15
2.1 语言成分15
2.2 文法和语言17
2.2.1 产生式文法17
2.2.2 上下文无关文法17
2.2.3 推导与直接推导18
2.3 文法的分类19
2.3.1 文法分类19
2.3.2 文法分类的意义21
2.3.3 文法举例22
2.4 语言和语法23
2.4.1 句型、句子和语言23
2.4.2 语法树24
2.4.3 产生式树和产生式图25
2.5 文法和语言的一些特性26
2.5.1 无用非终结符号26
2.5.2 不可达文法符号26
2.5.3 可空非终结符27
2.5.4 最左推导、最右推导和规范推导28
2.5.5 二义性29
2.6 分析方法简介30
2.6.1 自顶向下分析方法30
2.6.2 确定的自顶向下分析方法32
2.6.3 自底向上分析方法33
2.6.4 文法在内存中的表示34
2.7 小结36
习题36
第3章 有穷自动机38
3.1 概述38
3.2 有穷自动机的定义40
3.2.1 状态转换表40
3.2.2 状态转换图41
3.2.3 构形和移动42
3.2.4 自动机的等价性42
3.2.5 非确定有穷自动机42
3.3 NDFSA到DFSA的转换44
3.3.1 空移环路的寻找和消除44
3.3.2 确定化——子集法45
3.3.3 确定化——造表法46
3.3.4 消除不可达状态48
3.3.5 确定有穷自动机的化简48
3.3.6 从化简后的DFSA到程序表示50
3.4 正规文法与有穷自动机51
3.4.1 从正规文法到FSA52
3.4.2 从FSA到正规文法52
3.5 正规表达式与FSA53
3.5.1 正规表达式的定义53
3.5.2 正规表达式到NDFSA的转换55
3.5.3 NDFSA M到正规表达式的转换56
3.5.4 从正规文法到正规表达式57
3.6 DFSA在计算机中的表示58
3.6.1 矩阵表示法58
3.6.2 表结构表示法58
3.6.3 程序表示法59
3.7 小结59
习题60
第4章 词法分析62
4.1 单词符号62
4.2 词法分析程序的设计63
4.2.1 预处理63
4.2.2 状态转换图63
4.2.3 根据状态转换图设计词法分析程序64
4.2.4 由正规文法设计词法分析程序66
4.2.5 由正规表达式设计词法分析程序66
4.2.6 设计词法分析程序的直接方法67
4.3 标识符的处理68
4.3.1 类型的机内表示68
4.3.2 标识符的语义表示68
4.3.3 符号表68
4.3.4 标识符处理的基本思想68
4.4 词法错误及其处理69
4.5 小结69
习题70
第5章 自顶向下语法分析71
5.1 非确定的下推自动机71
5.1.1 PDA的形式定义72
5.1.2 PDA的构形和移动73
5.1.3 上下文无关语言与PDA74
5.2 消除左递归的方法76
5.2.1 文法的左递归性76
5.2.2 用扩展的BNF表示法消除左递归77
5.2.3 直接改写法78
5.2.4 消除左递归的算法79
5.3 LL(k)文法80
5.3.1 LL(1)文法的判断条件80
5.3.2 集合FIRST、FOLLOW与SELECT的构造81
5.4 确定的LL(1)分析器的构造83
5.4.1 分析表M的构造算法84
5.4.2 LL(1)分析器的总控算法86
5.5 递归下降分析程序及其设计87
5.5.1 递归下降分析程序87
5.5.2 流程图设计88
5.5.3 程序设计89
5.6 小结90
习题90
第6章 自底向上分析和优先分析方法93
6.1 短语和句柄93
6.2 移进归约方法95
6.3 非确定的自底向上分析器96
6.4 有关文法的一些关系100
6.4.1 关系100
6.4.2 布尔矩阵和关系101
6.4.3 Warshall算法102
6.4.4 关系FIRST与LAST103
6.5 简单优先分析方法105
6.5.1 简单优先关系105
6.5.2 简单优先关系的形式化构造方法107
6.5.3 简单优先文法及其分析算法108
6.5.4 简单优先分析方法的局限性110
6.6 算符优先分析方法111
6.6.1 算符优先文法111
6.6.2 OPG优先关系的构造111
6.6.3 素短语及句型的分析113
6.6.4 算符优先分析算法113
6.7 优先函数及其构造115
6.7.1 Bell方法116
6.7.2 Floyd方法117
6.7.3 两种方法的比较118
6.8 小结119
习题120
第7章 自底向上的LR(k)分析方法122
7.1 LR(k)文法和LR(k)分析器122
7.2 LR(0)分析表的构造125
7.2.1 规范句型的活前缀和LR(0)项目125
7.2.2 拓广文法和CLOSURE(I)函数126
7.2.3 goto(I,X)函数和LR(0)项目集规范族126
7.2.4 有效项目128
7.2.5 举例129
7.2.6 LR(0)文法和构造LR(0)分析表的算法132
7.3 SLR分析表的构造133
7.4 规范LR(1)分析表的构造136
7.5 LALR分析表的构造140
7.6 无二义性规则的使用144
7.7 小结145
习题146
第8章 语法制导翻译法147
8.1 基本原理和树变换147
8.1.1 基本原理147
8.1.2 树变换149
8.2 简单SDTS和自顶向下翻译器150
8.3 简单后缀SDTS和自底向上翻译器152
8.3.1 后缀翻译153
8.3.2 条件语句的处理153
8.3.3 函数调用的处理154
8.4 抽象语法树的构造155
8.4.1 自底向上构造ＡＳＴ156
8.4.2 ＡＳＴ的拓广157
8.5 属性文法157
8.5.1 Ｌ属性文法158
8.5.2 Ｓ属性文法158
8.6 中间代码形式158
8.6.1 逆波兰表示法159
8.6.2 逆波兰表示法的推广159
8.6.3 四元式160
8.6.4 三元式161
8.7 属性翻译文法的应用162
8.7.1 综合属性与自底向上定值162
8.7.2 继承属性和自顶向下定值163
8.7.3 布尔表达式到四元式的翻译164
8.7.4 条件语句的翻译164
8.7.5 迭代语句的翻译165
8.8 小结167
习题168
第9章 运行时的存储组织与管理170
9.1 存储分配基础知识170
9.1.1 运行时刻的存储区域170
9.1.2 过程活动与过程的活动记录170
9.1.3 静态层次、静态外层和动态外层171
9.1.4 名字的作用域和生存期172
9.1.5 名字的静态属性和动态属性173
9.1.6 常见数据类型的存储分配173
9.2 典型的存储分配方案174
9.2.1 静态存储分配方案174
9.2.2 动态存储分配方案175
9.2.3 存储分配时需考虑的问题175
9.3 参数传递方式及其实现176
9.3.1 传地址176
9.3.2 传值177
9.3.3 传结果177
9.3.4 传名177
9.4 栈式存储分配178
9.4.1 概述178
9.4.2 简单栈式存储分配179
9.4.3 嵌套结构语言的栈式存储分配180
9.4.4 过程调用时的存储管理183
9.4.5 PL/0栈式存储分配183
9.5 堆式存储分配方法184
9.6 小结185
习题185
第10章 符号表187
10.1 概述187
10.1.1 符号表的地位与作用187
10.1.2 符号表的生存期188
10.2 符号表的内容188
10.3 符号表的组织189
10.3.1 符号表的数据结构189
10.3.2 符号表的内容组织189
10.4 栈式符号表190
10.4.1 栈式符号表概述190
10.4.2 栈式符号表举例191
10.5 小结194
习题194
第11章 优化196
11.1 控制流图197
11.2 常见的冗余199
11.2.1 公共子表达式200
11.2.2 复制传播201
11.2.3 活跃变量分析及死代码删除202
11.3 循环优化203
11.3.1 代码外提203
11.3.2 归纳变量与强度削弱206
11.3.3 循环展开208
11.3.4 指令调度209
11.4 小结210
习题211
第12章 代码生成213
12.1 概述213
12.1.1 目标代码形式213
12.1.2 目标代码生成的主要问题213
12.1.3 寄存器分配的原则214
12.2 PL/0抽象计算机模型214
12.2.1 PL/0抽象计算机的代码214
12.2.2 PL/0语言目标代码举例215
12.3 目标代码结构216
12.3.1 目标代码结构的设计216
12.3.2 常见语法成分目标代码结构设计217
12.4 PL/0编译程序的目标代码生成218
12.4.1 PL/0编译程序中的相关定义218
12.4.2 基本语句的翻译219
12.4.3 过程的翻译221
12.4.4 目标代码生成举例223
12.5 小结228
习题229
附录 PL/0编译程序源程序230
参考文献247
