软件工程/工具/编译器简介

一个典型的多语言、多目标编译器运行的示意图。

编译器是一个计算机程序（或一组程序），它将用编程语言编写的源代码（源语言）转换为另一种计算机语言（目标语言，通常以二进制形式称为目标代码）。想要转换源代码的最常见原因是创建可执行程序。

“编译器”这个名字主要用于将源代码从高级编程语言转换为低级语言（例如，汇编语言或机器代码）的程序。如果编译后的程序可以在其 CPU 或操作系统与编译器运行的计算机不同的计算机上运行，则编译器被称为交叉编译器。将低级语言转换为高级语言的程序称为反编译器。将高级语言之间进行转换的程序通常称为语言翻译器、源到源翻译器或语言转换器。语言重写器通常是一个程序，它在不改变语言的情况下转换表达式的形式。

编译器可能会执行许多或所有以下操作：词法分析、预处理、解析、语义分析（语法制导翻译）、代码生成和代码优化。

由编译器行为不正确引起的程序错误可能非常难以追踪和解决；因此，编译器实现者投入了大量时间来确保其软件的正确性。

术语“编译器编译器”有时用于指代解析器生成器，这是一种经常用来帮助创建词法分析器和解析器的工具。

历史

多年来，早期计算机的软件主要用汇编语言编写。直到能够在不同类型的 CPU 上重用软件的好处开始明显大于编写编译器的成本，高级编程语言才被发明。早期计算机的内存容量非常有限，这也给编译器的实现带来了很多技术问题。

在 20 世纪 50 年代末，机器无关编程语言首次被提出。随后，开发了几个实验性的编译器。第一个编译器是由 Grace Hopper 于 1952 年为 A-0 编程语言编写的。IBM 的 John Backus 领导的 FORTRAN 团队通常被认为是在 1957 年引入了第一个完整的编译器。COBOL 是第一个在 1960 年在多个架构上编译的早期语言。

在许多应用领域，使用高级语言的想法迅速流行起来。由于更新的编程语言支持的功能不断扩展，以及计算机架构的复杂性不断增加，编译器变得越来越复杂。

早期的编译器是用汇编语言编写的。第一个自托管编译器——能够用高级语言编译自己的源代码——是由麻省理工学院的 Tim Hart 和 Mike Levin 在 1962 年为 Lisp 创建的。 自 20 世纪 70 年代以来，用它编译的语言实现编译器已成为惯例，尽管 Pascal 和 C 都是流行的实现语言。构建自托管编译器是一个引导问题——针对一种语言的第一个此类编译器必须通过用另一种语言编写的编译器编译，或者（如 Hart 和 Levin 的 Lisp 编译器）通过在解释器中运行编译器来编译。

编译器在教育中的应用

编译器构造和编译器优化作为计算机科学课程的一部分在大学和学校教授。这些课程通常辅以针对教育性编程语言的编译器实现。一个有据可查的例子是 Niklaus Wirth 的 PL/0 编译器，Wirth 在 20 世纪 70 年代用它来教授编译器构造。 尽管 PL/0 编译器很简单，但它为该领域引入了几个有影响力的概念

1. 逐步求精的程序开发（也是 Wirth 1971 年的一篇论文的标题）
2. 使用递归下降解析器
3. 使用 EBNF 指定语言语法
4. 生成可移植 P-code 的代码生成器
5. 使用 T-图 正式描述引导问题

编译

编译器促成了机器无关程序的开发。在 20 世纪 50 年代开发出第一种高级语言 FORTRAN（FORmula TRANslator）之前，机器相关的汇编语言被广泛使用。虽然汇编语言比在相同架构上的机器代码生成更可重用和可重定位的程序，但如果要在不同的硬件架构上执行程序，它必须被修改或重写。

随着 FORTRAN 之后不久高级编程语言的发展，如 COBOL、C、BASIC，程序员可以编写机器无关的源程序。编译器将高级源程序翻译成针对特定硬件的机器语言的目标程序。目标程序生成后，用户可以执行该程序。

编译器的结构

编译器连接高级语言中的源程序与底层硬件。编译器需要 1) 确定程序语法上的正确性，2) 生成正确高效的目标代码，3) 运行时组织，以及 4) 根据汇编器和/或链接器的约定格式化输出。编译器由三个主要部分组成：前端、中间端和后端。

前端检查程序在编程语言语法和语义方面是否正确编写。这里识别合法和非法程序。如果有错误，则以有用的方式报告错误。类型检查也通过收集类型信息来执行。然后前端为中间端处理生成源代码的中间表示或IR。

中间端是进行优化的部分。优化典型的转换是删除无用或不可达代码，发现和传播常量值，将计算重新定位到执行频率较低的地方（例如，循环之外），或根据上下文专门化计算。中间端为后面的后端生成另一个 IR。大多数优化工作都集中在这个部分。

后端负责将中间端来的 IR 翻译成汇编代码。为每个 IR 指令选择目标指令。变量也为寄存器选择。后端利用硬件通过弄清楚如何保持并行 FU 繁忙，填充延迟槽，等等。尽管大多数优化算法都在 NP 中，但启发式技术已经得到了很好的发展。

编译器输出

编译器的一种分类是根据其生成代码执行的平台。这被称为目标平台。

本地或托管编译器是指其输出旨在直接运行在与编译器本身运行的相同类型的计算机和操作系统上的编译器。交叉编译器的输出旨在运行在不同的平台上。交叉编译器通常用于为不支持软件开发环境的嵌入式系统开发软件。

编译器生成的虚拟机（VM）代码的输出，可能或可能不会在与生成该代码的编译器相同的平台上执行。因此，此类编译器通常不归类为原生编译器或交叉编译器。

编译型语言与解释型语言

为了方便起见，高级编程语言通常被划分为编译型语言和解释型语言。然而，在实践中，很少有语言会要求它只能被编译或解释，尽管可以设计依赖于运行时重新解释的语言。这种分类通常反映了语言最流行或最广泛的实现——例如，BASIC有时被称为解释型语言，C被称为编译型语言，尽管存在BASIC编译器和C解释器。

现代趋势，即即时编译和字节码解释，有时会模糊编译器和解释器的传统分类。

一些语言规范明确规定实现必须包含编译功能；例如，Common Lisp。然而，Common Lisp 的定义中并没有任何固有的东西阻止它被解释。其他语言具有在解释器中很容易实现但使编写编译器变得更加困难的功能；例如，APL、SNOBOL4 和许多脚本语言允许程序在运行时使用常规字符串操作构造任意源代码，然后通过将其传递给一个特殊的评估函数来执行该代码。为了在编译语言中实现这些功能，程序通常必须与包含编译器本身版本的运行时库一起交付。

硬件编译

一些编译器的输出可能会以非常低的级别针对硬件，例如现场可编程门阵列（FPGA）或结构化专用集成电路（ASIC）。此类编译器被称为硬件编译器或综合工具，因为它们编译的源代码有效地控制了硬件的最终配置及其操作方式；编译的输出不是按顺序执行的指令——只是晶体管或查找表的互连。例如，XST 是用于配置 FPGA 的 Xilinx 综合工具。Altera、Synplicity、Synopsys 和其他供应商提供了类似的工具。

编译器构建

在早期，编译器设计采用的方法会直接受到处理复杂度、设计人员的经验和可用资源的影响。

由一个人为相对简单的语言编写的编译器可能是一块单一的、整体的软件。当源语言庞大而复杂，并且需要高质量的输出时，设计可能会被分成几个相对独立的阶段。拥有独立的阶段意味着开发可以被分成小部分，并分配给不同的人。这样，用改进的阶段替换单个阶段，或者在后期插入新的阶段（例如，额外的优化）也变得更加容易。

将编译过程划分为阶段的做法是由卡内基梅隆大学的产品级编译器编译器项目 (PQCC) 提倡的。该项目引入了前端、中间端和后端这些术语。

除最小的编译器之外，所有编译器都具有两个以上的阶段。但是，这些阶段通常被认为是前端或后端的一部分。这两个端相遇的点存在争议。前端通常被认为是在执行语法和语义处理的地方，以及将代码转换为比源代码更低级的表示形式。

中间端通常被设计用于对除源代码或机器代码之外的形式进行优化。这种源代码/机器代码独立性旨在使通用优化能够在支持不同语言和目标处理器的编译器版本之间共享。

后端接收来自中间端的输出。它可能会执行更多针对特定计算机的分析、转换和优化。然后，它会为特定处理器和操作系统生成代码。

这种前端/中间/后端方法使得能够将不同语言的前端与不同 CPU 的后端结合起来。这种方法的实际例子包括 GNU 编译器集合、LLVM 和阿姆斯特丹编译器套件，它们具有多个前端、共享分析和多个后端。

单遍编译器与多遍编译器

根据遍数对编译器进行分类，其背景是计算机的硬件资源限制。编译涉及执行大量工作，早期的计算机没有足够的内存来容纳一个执行所有这些工作的程序。因此，编译器被分成更小的程序，每个程序对源代码（或其某种表示）进行一次遍，执行一些必要的分析和转换。

能够单遍编译传统上被视为一项优势，因为它简化了编写编译器的任务，并且单遍编译器通常比多遍编译器编译得更快。因此，在一定程度上受早期系统资源限制的驱动，许多早期的语言是专门为单遍编译而设计的（例如，Pascal）。

在某些情况下，语言特征的设计可能要求编译器对源代码执行多次遍。例如，考虑在源代码第 20 行出现的声明，它会影响对第 10 行出现的语句的转换。在这种情况下，第一遍需要收集有关出现在受其影响的语句之后的声明的信息，实际的转换将在后续遍中进行。

单遍编译的缺点是无法执行生成高质量代码所需的许多复杂优化。很难准确计算优化编译器执行的遍数。例如，优化的不同阶段可能会多次分析一个表达式，但可能只分析另一个表达式一次。

将编译器分成更小的程序是研究人员感兴趣的技术，旨在生成可证明正确的编译器。证明一组小程序的正确性通常比证明一个更大的、单一的、等效程序的正确性需要更少的努力。

虽然典型的多遍编译器在其最后一次遍中输出机器代码，但还有几种其他类型

• “源到源编译器”是一种编译器类型，它以高级语言作为输入，并输出高级语言。例如，自动并行化编译器通常会接收高级语言程序作为输入，然后转换代码并使用并行代码注释（例如 OpenMP）或语言结构（例如 Fortran 的DOALL 语句）对其进行标注。
• 阶段式编译器，编译为理论机器的汇编语言，如一些 Prolog 实现
  • 这种 Prolog 机器也被称为 Warren 抽象机 (WAM)。
  • Java、Python 和更多语言的字节码编译器也是这种类型的子类型。
• 即时编译器，用于 Smalltalk 和 Java 系统，以及 Microsoft .NET 的通用中间语言 (CIL)
  • 应用程序以字节码的形式交付，该字节码在执行之前立即被编译为本地机器代码。

前端

前端分析源代码以构建程序的内部表示，称为中间表示或IR。它还管理符号表，这是一种将源代码中的每个符号映射到相关信息（如位置、类型和范围）的数据结构。这在几个阶段内完成，包括以下一些阶段

1. 行重建。将关键字截断或允许标识符中出现任意空格的语言需要在解析之前进行一个阶段，该阶段将输入字符序列转换为解析器可用的规范形式。1960 年代使用的自顶向下、递归下降、表驱动的解析器通常一次读取一个字符，并且不需要单独的标记化阶段。Atlas Autocode 和 Imp（以及 ALGOL 和 Coral 66 的一些实现）是截断语言的例子，其编译器将具有行重建阶段。
2. 词法分析将源代码文本分解成称为词法单元的小片段。每个词法单元是语言的单个原子单元，例如关键字、标识符或符号名称。词法单元语法通常是正则语言，因此可以从正则表达式构建的有限状态自动机用于识别它。此阶段也称为词法分析或扫描，进行词法分析的软件称为词法分析器或扫描器。
3. 预处理。某些语言（例如 C）需要预处理阶段，该阶段支持宏替换和条件编译。通常，预处理阶段发生在语法分析或语义分析之前；例如，在 C 的情况下，预处理器操纵词法单元而不是语法形式。但是，一些语言（如 Scheme）支持基于语法形式的宏替换。
4. 语法分析涉及解析词法单元序列以识别程序的语法结构。此阶段通常会构建一个解析树，该解析树用根据定义语言语法的形式语法的规则构建的树结构替换词法单元的线性序列。解析树通常会被编译器后面的阶段进行分析、增强和转换。
5. 语义分析是编译器向解析树添加语义信息并构建符号表阶段。此阶段执行语义检查，例如类型检查（检查类型错误）或对象绑定（将变量和函数引用与其定义相关联）或确定性赋值（要求所有局部变量在使用前初始化），拒绝不正确的程序或发出警告。语义分析通常需要完整的解析树，这意味着此阶段在逻辑上遵循解析阶段，并在逻辑上先于代码生成阶段，尽管在编译器实现中通常可以将多个阶段折叠成对代码的一次遍历。

后端

由于生成汇编代码的功能重叠，术语后端有时会与代码生成器混淆。一些文献使用中间端来区分后端中的通用分析和优化阶段与机器相关的代码生成器。

后端的主要阶段包括以下内容

1. 分析：这是从输入派生的中间表示中收集程序信息的过程。典型的分析是数据流分析以构建使用-定义链、依赖关系分析、别名分析、指针分析、逃逸分析等。准确的分析是任何编译器优化的基础。调用图和控制流图通常也在分析阶段构建。
2. 优化：中间语言表示被转换为功能上等效但更快（或更小）的形式。流行的优化包括内联扩展、死代码消除、常量传播、循环转换、寄存器分配甚至自动并行化。
3. 代码生成：将转换后的中间语言翻译成输出语言，通常是系统的本机机器语言。这涉及资源和存储决策，例如决定将哪些变量放入寄存器和内存，以及选择和调度适当的机器指令以及它们相关的寻址模式（另见 Sethi-Ullman 算法）。

编译器分析是任何编译器优化的先决条件，它们紧密地协同工作。例如，依赖关系分析对于循环转换至关重要。

此外，编译器分析和优化的范围差异很大，从小到一个基本块到过程/函数级别，甚至整个程序（跨过程优化）。显然，编译器可以使用更广阔的视野来更好地完成工作。但这种广阔的视野并非免费的：大范围分析和优化在编译时间和内存空间方面成本很高；对于跨过程分析和优化尤其如此。

跨过程分析和优化在来自 HP、IBM、SGI、英特尔、微软和 Sun Microsystems 的现代商业编译器中很常见。开源 GCC 长期以来一直因缺乏强大的跨过程优化而受到批评，但它在这方面正在发生变化。另一个具有完整分析和优化基础设施的开源编译器是 Open64，它被许多组织用于研究和商业目的。

由于编译器分析和优化需要额外的時間和空間，因此一些编译器默认情况下会跳过它们。用户必须使用编译选项明确告诉编译器应启用哪些优化。

编译器正确性

编译器正确性是软件工程的一个分支，它涉及试图证明编译器是否按照其语言规范运行。 这些技术包括使用形式化方法开发编译器，以及对现有编译器进行严格测试（通常称为编译器验证）。

相关技术

汇编语言是一种低级语言，编译它的程序更常被称为汇编器，而反向程序被称为反汇编器。

将低级语言翻译成高级语言的程序称为反编译器。

将高级语言相互翻译的程序通常称为语言翻译器、源到源翻译器、语言转换器或语言重写器。最后一个术语通常用于不涉及语言更改的翻译。

国际会议和组织

每年，欧洲软件理论与实践联合会议（ETAPS）都会赞助国际编译器构造会议（CC），其中包含来自学术界和工业界的论文。

参考文献

• 编译器教科书参考 一系列主流编译器构建教科书的参考文献
• Aho，Alfred V.；Sethi，Ravi；Ullman，Jeffrey D.，Compilers: Principles, Techniques and Tools ISBN 0-201-10088-6 链接到出版商。也被称为“龙书”。
• Allen，Frances E.，"IBM 语言处理器技术的历史"，IBM 研究与开发杂志，第 25 卷，第 5 期，1981 年 9 月。
• Allen，Randy；Kennedy，Ken，Optimizing Compilers for Modern Architectures，Morgan Kaufmann 出版社，2001 年。 ISBN 1-55860-286-0
• Appel，Andrew Wilson
  • Modern Compiler Implementation in Java，第二版。剑桥大学出版社，2002 年。 ISBN 0-521-82060-X
  • Modern Compiler Implementation in ML，剑桥大学出版社，1998 年。 ISBN 0-521-58274-1
• Bornat，Richard，理解和编写编译器：一个 DIY 指南，Macmillan 出版社，1979 年。 ISBN 0-333-21732-2
• Cooper，Keith D.，和 Torczon，Linda，Engineering a Compiler，Morgan Kaufmann，2004 年，ISBN 1-55860-699-8。
• Leverett；Cattel；Hobbs；Newcomer；Reiner；Schatz；Wulf，An Overview of the Production Quality Compiler-Compiler Project，在Computer 13(8):38-49 (1980 年 8 月)
• McKeeman，William Marshall；Horning，James J.；Wortman，David B.，A Compiler Generator，Englewood Cliffs，N.J.：Prentice-Hall，1970 年。 ISBN 0-13-155077-2
• Muchnick，Steven，高级编译器设计与实现，Morgan Kaufmann 出版社，1997 年。 ISBN 1-55860-320-4
• Scott，Michael Lee，编程语言实践，Morgan Kaufmann，2005 年，第二版，912 页。 ISBN 0-12-633951-1 (本书作者网站).
• Srikant，Y. N.；Shankar，Priti，编译器设计手册：优化和机器代码生成，CRC 出版社，2003 年。 ISBN 0-8493-1240-X
• Terry，Patrick D.，编译器和编译器生成器：使用 C++ 的入门，国际汤姆森计算机出版社，1997 年。 ISBN 1-85032-298-8,
• Wirth，Niklaus，编译器构建 ISBN 0-201-40353-6，Addison-Wesley，1996 年，176 页。2005 年 11 月修订。

外部链接

• comp.compilers 新闻组和 RSS 订阅
• 硬件编译邮件列表
• "如何创建编译成 JavaScript 的语言". HackerNoon. 检索于 2021-12-19.
• 使用 flex 和 yacc 的编译器构建实践介绍
• 书籍 "编译器设计基础" 作者：Torben Ægidius Mogensen