可变目标C编译器

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

出版者的话
译者序
前言
第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.5dag操作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.4FIRST和FOLLOW集合102
7.5编写分析函数104
7.6处理语法错误106
深入阅读110
练习111
第8章表达式112
8.1表达式的表示112
8.2表达式分析115
8.3C语言表达式的分析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.4if语句173
10.5标号和goto语句174
10.6循环176
10.7switch语句178
10.8return语句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章MIPSR3000代码的生成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

前    言A Retargetable C Compiler: Design and Implementation编译器是程序员使用的关键工具，程序员每天都在使用编译器，并且非常依赖于其正确性和可靠性。编译器必须接受程序语言的所有标准定义，以便源代码可以实现跨平台的可移植性。编译器必须生成高效的目标代码，但更重要的是，编译器必须生成正确的目标代码，只有可靠的编译器才能生成可靠的应用程序。
    编译器本身是一个大而复杂的应用程序，值得我们深入分析研究。本书介绍了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程序浏览器，或者根据