编译器构造

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

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

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

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

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

目　　录
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<

前　　言
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转换为另一种