本书面向初学者，从编译器构造的角度进行分析，旨在帮助读者深入理解编译器的设计原理和方法。全书共14章，主要内容包括：词法分析和语法分析、语法制导翻译、符号表和声明处理、语义分析、虚拟机代码、运行时支持、目标代码生成等。全书内容安排紧凑合理，对编译器构造的基本知识与关键技术进行了深入浅出的讲解，并提供了详尽清晰的算法，倡导在实践中学习编译器构造的相关技术。本书不仅可作为计算机专业本科生或研究生的教材，也适合作为相关领域技术人员的参考书。

本书是一本经典的面向本科生理解编译原理和编译器构造的课程教材。本书以简洁、清晰的风格全面介绍了编译器构造的基本知识与关键技术。本书的三位原作者大学拥有30余年的编译器课程教学经验，根据他们丰富的教学经验和研究经验编写了这本教材。本书结合程序语言和编译技术的发展，以Java语言作为编译器的分析对象，并且采用面向对象的设计模式来组织编译器中的数据结构，在很大程度上降低了编译器构造的复杂程度，使初学编译器的读者能更加容易地上手实现自己的编译器。

前　　言
Crafting a Compiler

自1988年费希尔和勒布朗合著的Crafting a Compiler出版以来，情况已经发生了很大变化。虽然教师可能还记得那本书保存在5.25英寸软盘上的附带软件，但现在的大多数学生既未曾拥有过也没有见过这样的软盘。学生在课堂上和课外所体验的编程语言发生了许多变化。1991年，这本书以两种形式出现，其中的算法用C语言或Ada语言呈现。虽然现在C语言仍然是一种流行的语言，但Ada语言已经变得鲜为人知，没有达到预期的流行程度。C 语言从C语言发展而来，加入了面向对象的特性。Java是作为一种更简单的面向对象语言开发的，因其安全性和能在Web浏览器中运行而受到欢迎。美国大学理事会指定的大学先修课程已从Pascal改为C ，而后又改为Java。

虽然发生了很多变化，但学生还在继续学习、教师也还在继续教授编译器构造这一课程。编译器和编程语言翻译领域的研究继续快步前进，这是因为编译器以适应日益多样化的体系结构和编程语言为己任。软件开发环境也依赖于编译器与各种软件工具链组件（如语法感知编辑器、性能剖析工具和调试器）的成功互动。所有的现代软件都依赖于编译器来严格检查错误并忠实地翻译程序。

随着时间的推移，一些教科书经历了相对较小的变化，可能增加了一些新的习题或示例。而本书则反映了1988年到1991年期间素材的大量实质性的修订。虽然本书的重点仍然是讲授编译器结构的基本原理，但算法和方法层面已融入最新实践：

● 已经从实际应用中消失的主题（例如，属性文法）的相关内容已被尽量压缩或完全删除。
● 算法以伪代码（pseudocode）的形式呈现，这对于学习过本学科基本算法的学生来说应该很熟悉。伪代码使对算法的简明表述及对算法的目的和构造的合理讨论成为可能。
用特定语言实现这些算法的细节已归入Crafting a Compiler Supplement，该补充材料可在线获取，网址为http://www.pearsonhighered.com/fischer/。
● 调整了语法分析理论和实践的组织方式，以适用于各种教学方法。
有些学生可能会在较高层次上学习这部分内容，以获得自顶向下和自底向上语法分析的宽广视野。其他学生可以更详细地研究特定的方法。
● 编译器的前端和后端由抽象语法树（Abstract Syntax Tree，AST）衔接，AST是作为语法分析的主要产出而创建的。大多数编译器都会构建AST，但是鲜有教科书阐明AST的构造和用法。
引入了访问者模式（visitor pattern），以便在语义分析和代码生成期间遍历AST。
● 提供了实验室练习供教师使用。
教师可以将其中的一部分作为学生的练习，而其他部分则可从我们的课程支持网站
获得。

有些教科书经过修订，增加了更多的研究生水平的素材。虽然这些内容在高级课程中可能有用，但本书的主要读者仍然是学习编译器构造的本科生。研究生课程可以使用第13章和第14章的内容，并将前面的部分作为参考材料。

伪代码和缩写
本书的一个重要变化是，算法不再以任何特定的编程语言（如C或Ada）呈现，而是以伪代码的形式呈现，所使用的风格对于那些研究过最基本算法的人来说应该是熟悉的[CLRS01]。伪代码通过省略不必要的细节来简化算法的描述。然而，伪代码暗示了实际编程语言中使用的结构，因此实现应该是直接的。本书广泛使用缩写（包括首字母缩写）来简化描述，并帮助读者掌握编译器构造中使用的术语。例如，在前言中已经使用了AST作为抽象语法树的缩写。

本书的使用方法
关于编译器构造的入门课程可以从第1～3章开始。关于语法分析技术，可以选择自顶向下语法分析（第5章）或自底向上语法分析（第6章），但有些教师会选择同时介绍这两种方法。可以根据需要讲授第4章的内容，以支持将要学习的语法分析技术。第7章阐述了AST并给出了遍历AST的访问者模式。第8章和第9章介绍语义分析的各个方面，教师可自行决定讲授哪些内容。如果是一学期的课程，则可就此结束。如果是一学年的课时，则可继续学习代码生成，如下所述。

第10章介绍Java虚拟机（Java Virtual Machine，JVM），如果学生要在他们的项目中生成JVM代码，就应讲授这些内容。第11章介绍虚拟机代码生成。希望学生生成机器代码的教师可以跳过第10章和第11章，而只讲第12章和第13章。入门课程可以包括第14章开始部分有关自动程序优化的内容。

第4～6章中涉及语法分析技术的更多细节。第8章和第9章对类型检查和语义分析进行了广泛和深入的研究。第10章和第14章介绍高级概念，如静态单赋值（Static Single Assignment，SSA）形式等。第14章涉及程序分析和转换的高级主题，包括数据流框架。第13章和第14章可以作为研究生编译器课程的基础，辅以前面的章节作为参考材料。

各章概述

第1章　引言
该章首先概述了编译过程。强调从一组组件来构造编译器的概念。概述了编译器的历史，并介绍了生成编译器组件的工具的使用方法。

第2章　一个简单的编译器
该章介绍了简单语言ac，并讨论了将ac转换为另一种语言dc的编译器的每个组件。这些组件以伪代码的形式呈现，完整的代码可以在Crafting a Compiler Supplement中找到。

第3章　词法分析理论与实践
该章介绍了构建编译器词法分析组件的基本概念和技术。具体内容包括如何手工编写词法分析器以及使用词法分析器生成器来实现表驱动的词法分析器。

第4章　文法和语法分析
该章涵盖了形式语言的基本概念，包括上下文无关文法、文法表示、推导以及语法分析树，还介绍了第5章和第6章中将使用的文法分析算法。

第5章　自顶向下语法分析
自顶向下语法分析是构造相对简单的语法分析器的一种流行技术。该章展示了如何使用显式代码或通过构造供通用自顶向下语法分析引擎使用的分析表来编写这样的语法分析器。该章还讨论了语法错误的诊断、恢复和修复。

第6章　自底向上语法分析
大多数现代编程语言编译器使用该章介绍的某种自底向上语法分析技术。从上下文无关文法自动生成这种语法分析器的工具广泛可用。该章描述了构建这些工具的理论，包括一系列日益复杂的方法，这些方法用来解决阻碍从某些文法构建语法分析器的冲突（conflict）。该章还深入讨论了文法和语言的二义性（ambiguity），并提出了理解和解决二义性文法的启发式方法。

第7章　语法制导翻译
从编译器构成组件的角度，该章标志着本书的中点。前面的章节已经介绍了程序的词法分析和语法分析。这些章节的目标是构造AST。该章介绍AST并阐述用于构造、管理和遍历AST的接口。该章是非常关键的，因为后续章节既依赖于理解AST，也依赖于理解促进AST的遍历和处理的访问者模式。Crafting a Compiler Supplement包含了一个关于访问者模式的教程，包括从常见实践经验中提取的示例。

第8章　符号表和声明处理
该章强调使用符号表作为一个抽象组件，可在整个编译过程中使用。为符号表定义了一个精确的接口，并提出了各种实现问题和解决思路，其中包括对嵌套作用域实现的讨论。

该章还介绍了处理符号声明所需的语义分析，包括类型、变量、数组、结构和枚举，同时介绍了类型检查，包括面向对象类、子类和超类。

第9章　语义分析
对于在语法分析时不容易检查的语言规范，需要进行额外的语义分析，包括检查各种控制结构，如条件分支和循环。该章还讨论了异常及其在编译时所需的语义分析。

第10章　中间表示
该章介绍了编译器广泛使用的两种中间表示。第一种是JVM指令集和字节码格式，它已经成为表示Java程序编译结果的标准格式。对于有兴趣在编译器项目中使用JVM的读者，第10章和第11章提供了必要的背景知识和技术。另一种表示是SSA形式，它被许多优化编译器使用。该章定义了SSA形式，但要等到第14章才会介绍它的构造，并给出一些必要的定义和算法。

第11章　虚拟机代码生成
该章讨论针对虚拟机（Virtual Machine，VM）的代码生成。这种目标平台的优点是，运行时支持的许多细节都包含在VM中。例如，大多数VM提供无限数目的寄存器，因此尽管寄存器分配（register allocation）问题很有趣，但可以推迟到掌握了代码生成的基本知识之后再讨论。而且，虚拟机的指令集通常处于比机器码更高的级别。例如，一个方法调用通常由单个VM指令支持，而相同的调用用机器代码实现可能需要更多指令。

虽然对生成机器码感兴趣的读者可能会跳过第11章，但我们建议先学习这一章，然后再尝试生成机器码级别的代码。第11章的思想很容易应用于第12章和第13章，但从VM的角度来看，它们更容易理解。

第12章　运行时支持
在VM中嵌入的许多功能都是对运行时的支持（例如，对管理存储的支持）。该章讨论为现代编程语言提供所需的运行时支持的各种概念和实现策略。研究这些内容有助于理解虚拟机的构造。对于那些为目标体系结构编写代码生成器的人，必须提供运行时支持，因此学习第12章的内容对于创建一个可工作的编译器来说是必不可少的。
该章讨论了静态分配存储、栈分配存储和堆分配存储，还讨论了对非局部存储（nonlocal storage）的引用，以及支持此类引用的帧和显示表等实现结构。

第13章　目标代码生成
该章与第11章相似，区别是代码生成的目标与VM相比是相对低级的指令集。这一章全面讨论了代码生成中产生的主题，包括寄存器分配、临时变量管理、代码调度、指令选择和一些基本的窥孔优化。

第14章　程序优化
大多数编译器都包含一些改进它们生成的代码的功能。该章介绍编译器在程序优化中常用的一些实用技术，还介绍了进阶的控制流分析结构和算法。通过一些相对容易实现的基本优化，介绍了数据流分析（data flow analysis）。研究了此类优化的理论基础，并讨论了SSA形式的构造和使用。

查尔斯·N.费希尔 （Charles N.Fischer） 美国威斯康星大学计算机科学系教授，长期为本科生和研究生讲授编译原理相关课程。研究兴趣为编译器设计与实现。

罗恩·K.塞隆 (Ron K.Cytron) 美国圣路易斯华盛顿大学计算机科学与工程系教授，研究兴趣为实时系统与程序设计语言。

理查德·J.勒布朗 (Richard J.LeBlanc,Jr.) 美国佐治亚理工学院计算机系教授，主讲编译器与解释器方面的课程。曾任ACM教育委员会委员，是SE2004教育规范委员会副主席。

王刚，南开大学计算机学院教授、博士生导师。主要讲授程序设计、算法、编译、并行计算方面的课程。研究兴趣包括计算机理论、海量信息存储、并行与分布式计算、搜索引擎等，特别是在分布式存储系统可靠性技术、云存储用户数据隐私保护、搜索引擎性能优化等方向取得了一系列重要成果。近年来在计算机领域的国际顶尖学术期刊及国际顶级学术会议发表学术论文。主持国家863项目、国家自然科学基金项目、天津市自然科学基金项目等，主持与百度公司、奇虎360公司、华为公司等合作项目。现为IEEE/ACM/中国计算机学会会员、中国计算机学会信息存储专委会委员、中国计算机学会理论计算机专委会委员。

目　　录
Crafting a Compiler
前言
致谢
第1章　引言　1
1.1　编译技术历史　1
1.2　编译器的功能　2
1.2.1　编译器生成的机器代码　3
1.2.2　目标代码格式　4
1.3　解释器　5
1.4　语法和语义　6
1.4.1　静态语义　7
1.4.2　运行时语义　7
1.5　编译器的组织　9
1.5.1　词法分析器　10
1.5.2　语法分析器　10
1.5.3　类型检查器　10
1.5.4　翻译器　10
1.5.5　符号表　11
1.5.6　优化器　11
1.5.7　代码生成器　11
1.5.8　编译器编写工具　12
1.6　程序设计语言和编译器设计　12
1.7　计算机体系结构和编译器设计　13
1.8　编译器设计考虑　13
1.8.1　调试编译器　14
1.8.2　优化编译器　14
1.8.3　可重定位编译器　14
1.9　集成开发环境　15
习题　15
第2章　一个简单的编译器　18
2.1　ac语言的一个非形式化定义　18
2.2　ac的形式化定义　19
2.2.1　语法规范　19
2.2.2　单词规范　20
2.3　一个简单编译器的各阶段　21
2.4　词法分析　22
2.5　语法分析　23
2.5.1　预测语法分析例程　24
2.5.2　实现产生式　25
2.6　抽象语法树　25
2.7　语义分析　27
2.7.1　符号表　27
2.7.2　类型检查　27
2.8　代码生成　29
习题　31
第3章　词法分析理论与实践　32
3.1　词法分析器概述　32
3.2　正则表达式　34
3.3　示例　35
3.4　有限自动机与词法分析器　36
3.5　词法分析器生成器　39
3.5.1　在Lex中定义单词　40
3.5.2　字符集　40
3.5.3　使用正则表达式定义单词　41
3.5.4　使用Lex处理字符　43
3.6　其他词法分析器生成器　44
3.7　构建词法分析器的实际考虑　45
3.7.1　处理标识符和字面值　45
3.7.2　使用编译器指示以及列出
源码行　48
3.7.3　结束词法分析器　49
3.7.4　多超前字符　49
3.7.5　性能考虑　51
3.7.6　词法错误恢复　52
3.8　正则表达式和有限自动机　53
3.8.1　将正则表达式转换为NFA　54
3.8.2　创建DFA　54
3.8.3　优化有限自动机　56
3.8.4　将有限自动机转换为正则
表达式　58
3.9　总结　60
习题　61
第4章　文法和语法分析　64
4.1　上下文无关文法　64
4.1.1　最左推导　66
4.1.2　最右推导　66
4.1.3　语法分析树　66
4.1.4　其他类型的文法　67
4.2　CFG的性质　68
4.2.1　归约文法　68
4.2.2　二义性　68
4.2.3　错误的语言定义　69
4.3　转换扩展文法　69
4.4　语法分析器和识别器　70
4.5　文法分析算法　72
4.5.1　文法表示　72
4.5.2　推导空字符串　73
4.5.3　First集　74
4.5.4　Follow集　77
习题　79
第5章　自顶向下语法分析　82
5.1　概述　82
5.2　LL(k)文法　83
5.3　递归下降LL(1)语法分析器　85
5.4　表驱动LL(1)语法分析器　86
5.5　获得LL(1)文法　88
5.5.1　公共前缀　88
5.5.2　左递归　89
5.6　一个非LL(1)语言　90
5.7　LL(1)分析器的性质　92
5.8　分析表的表示　92
5.8.1　紧凑存储　93
5.8.2　压缩　94
5.9　语法错误恢复和修复　96
5.9.1　错误恢复　96
5.9.2　错误修复　96
5.9.3　LL(1)分析器中的错误检测　97
5.9.4　LL(1)分析器中的错误恢复　97
习题　98
第6章　自底向上语法分析　102
6.1　概述　102
6.2　移进归约语法分析器　103
6.2.1　LR语法分析器和最右推导　103
6.2.2　LR分析如针织　104
6.2.3　LR分析引擎　105
6.2.4　LR分析表　105
6.2.5　LR(k)分析　107
6.3　构造LR(0)分析表　109
6.4　冲突诊断　113
6.4.1　二义性文法　114
6.4.2　非LR(k)文法　116
6.5　冲突消解和表构造　117
6.5.1　SLR(k)分析表构造　117
6.5.2　LALR(k)分析表构造　120
6.5.3　LALR传播图　122
6.5.4　LR(k)表构造　125
习题　129
第7章　语法制导翻译　135
7.1　概述　135
7.1.1　语义动作和语义值　135
7.1.2　综合属性和继承属性　136
7.2　自底向上语法制导翻译　137
7.2.1　示例　137
7.2.2　 产生式克隆　139
7.2.3　强制执行语义动作　140
7.2.4　激进的文法重构　141
7.3　自顶向下语法制导翻译　142
7.4　抽象语法树　143
7.4.1　具体语法树与抽象语法树　144
7.4.2　一种高效的AST数据结构　144
7.4.3　创建AST的基础架构　145
7.5　AST设计和构造　146
7.5.1　设计　147
7.5.2　构造　148
7.6　左值和右值的AST结构　150
7.7　AST设计模式　152
7.7.1　节点类层次　152
7.7.2　访问者模式　153
7.7.3　反射访问者模式　154
习题　157
第8章　符号表和声明处理　160
8.1　构造符号表　160
8.1.1　静态作用域　161
8.1.2　符号表接口　162
8.2　块结构语言和作用域　163
8.2.1　处理作用域　163
8.2.2　单符号表还是多符号表　163
8.3　基本实现技术　164
8.3.1　插入和查找名字　164
8.3.2　名字空间　166
8.3.3　一个高效的符号表实现　166
8.4　高级特性　169
8.4.1　记录和类型名　169
8.4.2　重载和类型层次　170
8.4.3　隐式声明　170
8.4.4　导出指示和导入指示　171
8.4.5　改变搜索规则　171
8.5　声明处理基础　172
8.5.1　符号表中的属性　172
8.5.2　类型描述符结构　172
8.5.3　使用抽象语法树进行类型
检查　173
8.6　变量和类型声明　174
8.6.1　简单变量声明　174
8.6.2　处理类型名　175
8.6.3　类型声明　176
8.6.4　变量声明再探　178
8.6.5　静态数组类型　179
8.6.6　结构和记录类型　180
8.6.7　枚举类型　181
8.7　类和方法声明　183
8.7.1　处理类声明　184
8.7.2　处理方法声明　186
8.8　类型检查简介　188
8.8.1　简单标识符和字面量　190
8.8.2　赋值语句　190
8.8.3　检查表达式　191
8.8.4　检查复杂名字　191
8.9　总结　194
习题　195
第9章　语义分析　198
9.1　控制结构的语义分析　198
9.1.1　可达性和终止分析　199
9.1.2　if语句　200
9.1.3　while、do和repeat循环
语句　203
9.1.4　for循环语句　204
9.1.5　break、continue、return和
goto语句　205
9.1.6　switch和case语句　210
9.1.7　异常处理　214
9.2　方法调用的语义分析　218
9.3　总结　223
习题　223
第10章　中间表示　227
10.1　概述　227
10.1.1　示例　228
10.1.2　中端　229
10.2　Java虚拟机　230
10.2.1　简介和设计原则　230
10.2.2　类文件内容　231
10.2.3　JVM指令　232
10.3　静态单赋值形式　237
习题　239
第11章　虚拟机代码生成　241
11.1　代码生成访问者　241
11.2　类和方法声明　243
11.2.1　类声明　243
11.2.2　方法声明　245
11.3　MethodBodyVisitor　245
11.3.1　常量　245
11.3.2　局部存储引用　246
11.3.3　静态引用　246
11.3.4　表达式　247
11.3.5　赋值　248
11.3.6　方法调用　249
11.3.7　字段引用　250
11.3.8　数组引用　251
11.3.9　条件执行　252
11.3.10　循环　252
11.4　LHSVisitor　253
11.4.1　局部引用　254
11.4.2　静态引用　254
11.4.3　字段引用　255
11.4.4　数组引用　255
习题　256
第12章　运行时支持　258
12.1　静态分配　258
12.2　栈分配　259
12.2.1　类和结构中的字段访问　260
12.2.2　运行时访问帧　261
12.2.3　处理类和对象　262
12.2.4　处理多重作用域　263
12.2.5　块级分配　264
12.2.6　关于帧的更多讨论　265
12.3　数组　267
12.3.1　静态一维数组　267
12.3.2　多维数组　270
12.4　堆管理　272
12.4.1　分配机制　272
12.4.2　释放机制　274
12.4.3　自动垃圾收集　274
12.5　基于区域的内存管理　279
习题　280
第13章　目标代码生成　284
13.1　翻译字节码　285
13.1.1　分配内存地址　286
13.1.2　分配数组和对象　286
13.1.3　方法调用　288
13.1.4　字节码翻译过程的示例　290
13.2　翻译表达式树　291
13.3　寄存器分配　294
13.3.1　动态寄存器分配　294
13.3.2　使用图着色进行寄存器
分配　296
13.3.3　基于优先级的寄存器分配　300
13.3.4　过程间寄存器分配　301
13.4　代码调度　302
13.4.1　改进代码调度　305
13.4.2　全局和动态代码调度　306
13.5　指令自动选择　307
13.5.1　使用BURS选择指令　308
13.5.2　使用Twig选择指令　310
13.5.3　其他方法　310
13.6　窥孔优化　311
13.6.1　窥孔优化级别　311
13.6.2　自动生成窥孔优化器　313
习题　314
第14章　程序优化　318
14.1　概述　318
14.2　控制流分析　323
14.2.1　控制流图　323
14.2.2　程序和控制流结构　325
14.2.3　直接过程调用图　325
14.2.4　深度优先生成树　326
14.2.5　支配关系　329
14.2.6　简单的支配关系计算算法　330
14.2.7　快速的支配关系计算算法　332
14.2.8　支配前沿　339
14.2.9　区间　341
14.3　数据流分析介绍　349
14.3.1　可用表达式　349
14.3.2　活跃变量　351
14.4　数据流框架　352
14.4.1　数据流评估图　353
14.4.2　交格　354
14.4.3　转移函数　355
14.5　求解　356
14.5.1　迭代　356
14.5.2　初始化　359
14.5.3　终止和快速框架　360
14.5.4　满足分配律的框架　363
14.6　常量传播　364
14.7　SSA形式　366
14.7.1　放置函数　368
14.7.2　重命名　369
习题　371
参考文献　378