本书系统地介绍了可变目标ANSI C编译器lcc的设计方法和实现技术。lcc是一个实用的编译器，能够为不同的目标机器（如MIPS R3000、SPARC、Intel 386及其后续产品）生成代码。本书结合lcc的具体实现，详细讲述了存储管理、符号表、词法分析、语法分析、中间代码生成、优化、目标代码产生等编译程序的各个部分。全书共分19章，各章之后均附有练习。
本书特色鲜明，实用性强，适合作为高等院校计算机专业的编译原理课程的教材或参考书，对从事编译相关工作的技术人员也有很好的参考价值。

lcc编译器是一个具有产品级质量的可变目标C编译器，由AT&T贝尔实验室和普林斯顿大学为ANSI C编程语言设计，在UNIX界广为流行。本书称得上是一个文本程序（literate program），包括lcc的源代码及说明，在代码级对系统的设计和实现进行了详细的介绍。本书全面而真实地展示了一个大型软件系统，介绍了C编译器的一种实现方法，而不是只针对编译过程中遇到的问题给出解决方案，非常适合自学使用，也适合在需要使用或实现基于语言的工具和技术的应用领域（如用户接口）工作的专业人员使用。

本书特色
只给出了理解lcc的实现所需的编译器理论，重点关注实际应用问题。
从编译器设计者的角度讲解C语言的特性，引导C程序员更好地掌握语言本身及其在现代计算机上的高效实现。
介绍了完整的代码生成器，代码生成面向MIPS R3000、SPARC和Intel 386及其后续产品等不同的平台。
提供了lcc编译器的完整源代码、3个后端以及代码生成器。

作者简介
克里斯多夫 W. 弗雷泽（Christopher W. Fraser） 从1975年就开始研究编译技术，尤其对于从紧缩规范自动产生代码生成器这一技术有深入的研究，在该领域发表了多篇论文。他提出了可变目标的窥孔优化方法，该方法被广为流行的C编译器——GCC所采纳。从1977年到1985年，他在亚利桑那大学从事计算机科学（包括编译技术）的教学工作。1986年以后，他先后在AT&T贝尔实验室、微软研究院和谷歌公司任职，目前致力于独立项目的咨询和研究工作。
戴维 R. 汉森（David R. Hanson） 谷歌公司软件工程师，于2012年退休。在加入谷歌公司之前，曾任职于微软研究院、普林斯顿大学、亚利桑那大学和耶鲁大学。他主持了与贝尔实验室的合作研究，是lcc的开发者之一。他的研究兴趣包括编程语言、编译器、软件工具和编程环境。

编译器是程序员使用的关键工具，程序员每天都在使用编译器，并且非常依赖于其正确性和可靠性。编译器必须接受程序语言的所有标准定义，以便源代码可以实现跨平台的可移植性。编译器必须生成高效的目标代码，但更重要的是，编译器必须生成正确的目标代码，只有可靠的编译器才能生成可靠的应用程序。
编译器本身是一个大而复杂的应用程序，值得我们深入分析研究。本书介绍了ANSI C语言编译器lcc的大部分实现，对编译器的介绍方式与B. W. Kernighan和P. J. Plauger合著的《Software Tools》（Addison-Wesley，1976）一书对文本处理（例如文本编辑和宏处理）的介绍类似。研究实用的工具软件，是学习软件设计和实现技术的最好方法。本书在代码级详细介绍了一个实用的编译器，该编译器的完整源代码可在ftp.cs.princeton.edu（128.112.152.13）服务器的pub/lcc目录下，通过匿名ftp服务得到。
lcc不是一个研究系统，而是一个实用的编译器产品。从1988年开始，lcc就用于编译实际程序，现在每天都有数百名C程序员在使用它。由于本书详细分析了lcc编译器的设计与实现，因此用于介绍相关支撑材料的篇幅较少，仅展示了涉及的理论知识，而更为系统的编译技术的介绍可以参见其他教材。本书有意省略一些涉及琐碎和重复实现的语言特征，而将这部分内容作为练习。
显然，本书将使读者对编译器的构造有更多的了解。然而只有少数程序员需要了解编译器的设计与实现，大多数程序员从事的是应用程序或其他系统程序的开发。但是，基于以下4个原因，大多数C程序员都可以从本书中受益。
第一，一般来说，如果程序员能够理解C编译器的工作原理，通常可以成为较好的程序员，特别是较好的C程序员。编译器设计者必须全面准确地理解C语言的每一个特性，程序员通过学习这些特性的实现，能够更好地掌握语言本身及其在现代计算机上的高效实现。
第二，大多数程序设计教材都是通过一些精简的示例来说明编程技巧的，但大多数程序员都是在从事大型程序的开发，在开发过程中需要不断修改程序，很少有带详细说明的示例可以作为大型程序设计的参考。lcc不是完美的，但是本书详细说明了该程序的优缺点，可以作为大型程序开发的参考。
第三，编译器是计算机科学中理论与实践相结合的最好典范。lcc展示了理论与实践的相互作用及其精美的结果，展示了实践需求牵引理论的发展，这些都可以清楚地从代码中找到。通过一个真实的程序来研究这些相互作用，可以帮助程序员理解何时、何地以及如何运用不同的技术。此外，lcc也阐明了众多的C编程技术。
第四，这本书本身是一个文本程序（literate program），如同D. E. Knuth所著的《TeX: The Program》（Addison-Wesley，1986）一样，本书包括lcc的源代码及说明。为了方便读者理解，本书并未按源程序的顺序对程序代码进行讲解，而是有意进行了调整。
无论是对于在校学生还是专业技术人员，本书都非常适合自学使用。本书为lcc提供了说明完整的源代码，希望进行编译技术实践的人员，以及在需要使用或实现基于语言的工具和技术的应用领域（如用户接口）中工作的专业人员，将会对本书感兴趣。lcc的相关信息可通过以下地址获得：www.cs.princeton.edu/software/lcc。
本书全面而真实地展示了一个大型软件系统，可作为软件工程课程的分析实例。
对于编译课程来说，本书弥补了传统编译教材的不足。本书介绍了C编译器的一种实现方法，而传统教材主要介绍编译过程中遇到的各种问题的解决算法，因此传统教材受篇幅限制只能介绍一些实验性的编译器，代码生成也通常面向较高的级别，以避免与具体的机器相关。
因此，许多教师要求学生完成接近实际的编译器项目，使学生获得实践经验。通常，教师必须从头开始编写编译程序，而学生复制其中的大部分，修改后利用其余的部分。然而，由于编译器只是实验性的，文档往往显得不够充分，这种情形使教学双方都不满意。本书通过对一个实际编译器的大部分程序进行文档说明，并提供源代码，为教师提供了一种新的选择。
本书介绍了完整的代码生成器，代码生成面向MIPS R3000、SPARC和Intel 386及其后续体系结构等不同的平台。本书利用了最新的研究成果，根据目标机器的紧缩规范（compact specification）生成代码生成器。这些方法使得我们能够针对多种机器展示完整的代码生成器，这是其他书籍无法做到的。通过介绍多个代码生成器，既避免了本书依赖于单一的机器，又有助于学生了解如何设计可变目标的软件。
教师布置的作业可以是增加编译器接受的语言特征、优化、改变目标机器等。本书如果与传统教材配合使用，也可以要求学生使用不同的算法代替现有的模块作为实践作业。如果以实现一个实验编译器作为实践作业，则可能在低级基础结构和重复的语言特征上花费大量的时间。采取上述方法，就能够更接近实际的编译器工程实践。本书的许多练习都涉及编译器工程问题。
除传统的编译目的外，lcc也有其他用途。例如，它可以用于构建一个C程序浏览器，或者根据声明来生成远程过程调用的桩函数（stub），也能用于语言扩充、新的计算机体系结构和代码生成技术的实验。
本书假设读者熟悉某种计算机的C和汇编语言，了解编译器的概念，理解编译器的工作原理，同时要求读者的数据结构和算法知识达到一般本科水平，例如，R. Sedgewick所著的《Algorithms in C》（Addison-Wesley，1990）一书中的内容对于理解lcc就足够了。
致谢
感谢众多lcc用户，他们来自于AT&T贝尔实验室、普林斯顿大学和其他地方，他们忍受了许多程序中的错误，并提供了有价值的反馈。感谢Hans Boehm、Mary Fernandez、Michael Golan、Paul Haahr、Brian Kernighan、Doug McIlroy、Rob Pike、Dennis Ritchie和Ravi Sethi。Ronald Guilmette、David Kristol、David Prosser和Dennis Ritchie在ANSI标准的许多细节及其解释方面提供了非常有价值的信息。David Gay帮助我们改造了PFORT数值计算软件库，以作为lcc代码生成的测试用例，非常有价值。
Jack Davidson、Todd Proebsting、Norman Ramsey、William Waite和David Wall仔细阅读了我们的代码和文字，大大提高了二者的质量。还要感谢Steve Beck，他安装并改进了书中用到的字体；感谢Maylee Noah，他使用Adobe Illustrator制作完成了本书的图片。

Christopher W. Fraser
David R. Hanson

计算机\程序设计

lcc编译器是一个具有产品级质量的可变目标C编译器，由AT&T贝尔实验室和普林斯顿大学为ANSI C编程语言设计，在UNIX界广为流行。本书称得上是一个文本程序（literate program），包括lcc的源代码及说明，在代码级对系统的设计和实现进行了详细的介绍。本书全面而真实地展示了一个大型软件系统，介绍了C编译器的一种实现方法，而不是只针对编译过程中遇到的问题给出解决方案，非常适合自学使用，也适合在需要使用或实现基于语言的工具和技术的应用领域（如用户接口）工作的专业人员使用。
本书特点
 只给出了理解lcc的实现所需的编译器理论，重点关注实际应用问题。
 从编译器设计者的角度讲解C语言的特性，引导C程序员更好地掌握语言本身及其在现代计算机上的高效实现。
 介绍了完整的代码生成器，代码生成面向MIPS R3000、SPARC和Intel 386及其后续产品等不同的平台。
 提供了lcc编译器的完整源代码、3个后端以及代码生成器。

[美] 克里斯多夫 W. 弗雷泽（Christopher W. Fraser）戴维 R. 汉森（David R. Hanson） 著：克里斯多夫 W. 弗雷泽（Christopher W. Fraser）　从1975年就开始研究编译技术，尤其对于从紧缩规范自动产生代码生成器这一技术有深入的研究，在该领域发表了多篇论文。他提出了可变目标的窥孔优化方法，该方法被广为流行的C编译器—一GCC所采纳。从1977年到1985年，他在亚利桑那大学从事计算机科学（包括编译技术）的教学工作。1986年以后，他先后在AT&T贝尔实验室、微软研究院和谷歌公司任职，目前致力于独立项目的咨询和研究工作。
戴维 R. 汉森（David R. Hanson）　谷歌公司软件工程师，于2012年退休。在加入谷歌公司之前，曾任职于微软研究院、普林斯顿大学、亚利桑那大学和耶鲁大学。他主持了与贝尔实验室的合作研究，是lcc的开发者之一。他的研究兴趣包括编程语言、编译器、软件工具和编程环境。

王挺 黄春 等译：暂无简介

编译器构造原理和技术可以说是计算机科学中理论与实践相结合的最好典范。到目前为止，大多数教材都是介绍编译器构造原理的，很少有详细介绍实用编译器构造的专门书籍。在编译原理课程的教学过程中，如何设计和组织实验一直是一个难题。这主要是因为，任何实用的编译器往往都是庞大的程序，而小的实验编译器又难以反映编译程序构造的许多重要技术。本书可以说是弥补了传统编译教材在实践方面的缺陷，如果希望向学生展示实用编译器是如何设计的，本书应该是最佳选择。
lcc编译器是一个具有产品级质量的用于研究的C编译器，在UNIX界广为流行。本书深入到lcc编译器的内部，在代码级对该系统的设计和实现进行了详细的介绍。全书共分19章，详细讲述了存储管理、符号表、词法分析、语法分析、中间代码生成、优化、目标代码产生等编译程序的各个部分。本书特别针对3种目标机器（MIPS、SPARC和Intel 386）介绍了代码生成器的设计。通过学习上述内容，读者可以深入了解产品级编译程序设计中的许多关键技术，对于如何设计和实现一个实用的编译器有具体、真切的认识，这是其他教材无法达到的效果。
本书的两位作者都具有深厚的教学和研究背景。Christopher W. Fraser从1975年就开始研究编译技术，尤其对于从紧缩规范自动产生代码生成器这一技术有深入的研究，在该领域发表了多篇论文。他提出了可变目标的窥孔优化方法，该方法被广为流行的C编译器——GCC所采纳。从1977年到1986年，Fraser在亚利桑那大学从事计算机科学（包括编译技术）的教学工作。1986年以后，他在AT&T贝尔实验室主持计算技术的研究工作。David R. Hanson是普林斯顿大学计算机科学教授，具有20多年的研究程序语言的经验，主持了与贝尔实验室的合作研究，是lcc的开发者之一。
本书是作者的教学、科研和开发思想以及经验的总结，读者可以从字里行间体会到两位作者在编译器的研究和设计方面的造诣。
国防科学技术大学计算机学院从事编译原理课程教学和科研工作的几位教师共同完成了本书的翻译工作。全书由王挺、黄春、刘金红、张晓燕和陈耀东负责翻译，由王挺和黄春通篇整理。由于时间和水平有限，翻译错误在所难免，恳请读者指正。

出版者的话
译者序
前言
第1章　引论　1
1.1　文本程序　1
1.2　如何使用本书　2
1.3　概述　3
1.4　设计　7
1.5　公共声明　11
1.6　语法规范　13
1.7　错误　14
深入阅读　15
第2章　存储管理　16
2.1　内存管理接口　16
2.2　分配区的表示　17
2.3　空间分配　18
2.4　空间释放　20
2.5　字符串　20
深入阅读　23
练习　23
第3章　符号管理　26
3.1　符号的表示　27
3.2　符号表的表示　29
3.3　作用域的改变　32
3.4　查找和建立标识符　32
3.5　标号　33
3.6　常量　34
3.7　产生的变量　37
深入阅读　38
练习　38
第4章　类型　40
4.1　类型表示　40
4.2　类型管理　42
4.3　类型断言　45
4.4　类型构造器　46
4.5　函数类型　48
4.6　结构和枚举类型　49
4.7　类型检查函数　52
4.8　类型映射　56
深入阅读　56
练习　57
第5章　代码生成接口　59
5.1　类型度量　59
5.2　接口记录　60
5.3　符号　60
5.4　类型　61
5.5　dag操作　61
5.6　接口标志　65
5.7　初始化　67
5.8　定义　67
5.9　常量　69
5.10　函数　70
5.11　接口绑定　72
5.12　上行调用　73
深入阅读　75
练习　75
第6章　词法分析器　77
6.1　输入　77
6.2　单词的识别　81
6.3　关键字的识别　85
6.4　标识符的识别　86
6.5　数字的识别　87
6.6　字符常量和字符串的识别　92
深入阅读　95
练习　95
第7章　语法分析　97
7.1　语言和语法　97
7.2　二义性和分析树　98
7.3　自上而下的语法分析　100
7.4　FIRST和FOLLOW集合　102
7.5　编写分析函数　104
7.6　处理语法错误　106
深入阅读　110
练习　111
第8章　表达式　112
8.1　表达式的表示　112
8.2　表达式分析　115
8.3　C语言表达式的分析　117
8.4　赋值表达式　119
8.5　条件表达式　121
8.6　二元表达式　122
8.7　一元表达式和后缀表达式　124
8.8　基本表达式　127
深入阅读　130
练习　130
第9章　表达式语义　132
9.1　转换　132
9.2　一元操作符和后缀操作符　136
9.3　函数调用　141
9.4　二元操作符　147
9.5　赋值操作　150
9.6　条件操作　154
9.7　常量折叠　156
深入阅读　165
练习　165
第10章　语句　167
10.1　代码的表示　167
10.2　执行点　170
10.3　语句的识别　171
10.4　if语句　173
10.5　标号和goto语句　174
10.6　循环　176
10.7　switch语句　178
10.8　return语句　188
10.9　管理标号和跳转指令　191
深入阅读　194
练习　194
第11章　声明　196
11.1　转换单元　196
11.2　声明　197
11.3　声明符　206
11.4　函数声明符　210
11.5　结构说明符　215
11.6　函数定义　222
11.7　复合语句　229
11.8　结束处理　236
11.9　主程序　238
深入阅读　240
练习　241
第12章　中间代码的生成　243
12.1　消除公共子表达式　244
12.2　构建节点　248
12.3　控制流　250
12.4　赋值语句　256
12.5　函数调用　259
12.6　强制计算顺序　261
12.7　驱动代码生成　263
12.8　删除多次引用的节点　267
深入阅读　272
练习　273
第13章　构造代码生成器　275
13.1　代码生成器的组织　276
13.2　接口扩展　277
13.3　上行调用　279
13.4　节点扩展　280
13.5　符号扩展　282
13.6　帧的布局　284
13.7　生成块复制的代码　287
13.8　初始化　289
深入阅读　290
练习　290
第14章　选择和发送指令　291
14.1　规范　292
14.2　标记树　294
14.3　化简树　295
14.4　代价函数　302
14.5　调试　303
14.6　发送器　304
14.7　寄存器定位　309
14.8　指令选择的协调　313
14.9　共享规则　314
14.10　编写规范　315
深入阅读　316
练习　316
第15章　寄存器分配　318
15.1　组织结构　318
15.2　寄存器状态跟踪　319
15.3　寄存器分配　322
15.4　寄存器溢出　327
深入阅读　334
练习　334
第16章　MIPS R3000代码的生成　335
16.1　寄存器　336
16.2　指令的选取　339
16.3　函数的实现　349
16.4　数据的定义　355
16.5　块的复制　359
深入阅读　360
练习　360
第17章　SPARC代码的生成　362
17.1　寄存器　363
17.2　指令的选取　366
17.3　函数的实现　378
17.4　数据的定义　384
17.5　块的复制　386
深入阅读　387
练习　387
第18章　X86代码的生成　389
18.1　寄存器　390
18.2　指令的选取　394
18.3　函数的实现　407
18.4　数据的定义　409
深入阅读　412
练习　412
第19章　回顾　413
19.1　数据结构　413
19.2　接口　414
19.3　句法和语义分析　415
19.4　代码生成和优化　416
19.5　测试和验证　416
深入阅读　417
参考文献　419