编译器

文档摘要

编译器用于将程序从一种形式转换为另一种形式，它们也可以视为使用各种算法和数据结构的大型软件系统。通过研究编译器获得的知识，可以用于设计其他可扩展的软件系统。另一方面，编译器也是一项活跃的科学研究课题，有许多未探索的领域和主题可以研究。可以在以下链接找到有关编译器内部结构的基本信息。我们将保持尽可能简单，以便信息适用于其他编译器，而不仅仅是Clang。我们将简要介绍编译的所有阶段，这将有助于理解Clang在整体编译器架构中的位置。编译器的主要功能是，将用特定编程语言（如C/C++或FORTRAN）编写的程序，转换为可以在目标平台上执行的格式。这一过程涉及使用编译器，其接受源文件和编译标志，并产生一个构建文件，例如可执行文件或对象文件，如图2.1所示。

编译器用于将程序从一种形式转换为另一种形式，它们也可以视为使用各种算法和数据结构的大型软件系统。通过研究编译器获得的知识，可以用于设计其他可扩展的软件系统。另一方面，编译器也是一项活跃的科学研究课题，有许多未探索的领域和主题可以研究。

可以在以下链接找到有关编译器内部结构的基本信息。我们将保持尽可能简单，以便信息适用于其他编译器，而不仅仅是Clang。我们将简要介绍编译的所有阶段，这将有助于理解Clang在整体编译器架构中的位置。

编译器的主要功能是，将用特定编程语言（如C/C++或FORTRAN）编写的程序，转换为可以在目标平台上执行的格式。这一过程涉及使用编译器，其接受源文件和编译标志，并产生一个构建文件，例如可执行文件或对象文件，如图2.1所示。

术语“目标平台”的含义很宽泛，通常是指的是在同一主机上执行的机器代码。但它也可指的是交叉编译，即编译器为与主机不同的计算机架构生成代码。例如，可以使用Intel机器作为主机，为在ARM上运行的移动应用程序或嵌入式应用程序生成的代码。此外，目标平台不限于机器代码。例如，一些早期的C++编译器（如"cc"）会产生纯C代码作为输出。这是因为在当时，C是最广泛使用和最成熟的编程语言，C编译器是最可靠的方式来生成机器代码。因为大多数系统已经配备了C编译器，这种方式让早期的C++程序在主流的平台上运行。可以使用主流的C编译器生成的C代码，如GCC或LCC，编译成机器代码。

我们将专注于产生二进制代码的编译器，此类编译器的典型编译工作流程如图2.2所示。编译阶段的描述如下：

前端：前端执行词法分析和解析，包括语法分析和语义分析。语法分析假设程序按照语言语法规则组织良好。语义分析对程序的含义进行检查，并拒绝无效程序，例如使用错误类型的程序。
中端：中端对中间表示（IR）代码（对于Clang为LLVM-IR）进行各种优化。
后端：编译器的后端将经过优化或转换的IR，生成目标平台可以执行的机器代码或汇编代码。

源程序在通过各个阶段时会转换为不同的形式。例如，前端产生IR代码，然后中端对其进行优化，最后后端将其转换为本地代码（见图2.3）。

输入数据包括源代码和编译选项，源代码由前端转换为IR。中端对IR进行不同的优化，并将最终（优化后的）结果传递给后端，后端生成目标代码。前端、中端和后端使用编译选项作为代码转换的设置。先来了解一下编译器前端，其作为编译器工作流程的第一部分。

前端的主要目标是将给定的源代码转换为中间形式，前端在生成IR之前还将源代码转换为各种形式。前端将是本书的主要关注点，因此将检查其组件。前端的第一部分是词法分析器（Lexer）（见图2.4）。

它将源代码转换为一组token，这些token用于创建一个称为抽象语法树（AST）的特殊数据结构。前端最终的组件，代码生成器（Codegen），遍历AST并从其中生成IR。

我们将使用一个简单的C/C++程序来演示前端的工作原理。该程序计算两个数字中的最大值：

int max(int a, int b) if (a > b) return a; return b;

图2.5：编译器前端测试程序

前端的第一部分是词法分析器。

前端过程始于词法分析器，将输入源转换为一组token流。示例程序（见图2.5）中，第一个token是关键字int，表示整数类型。这之后是标识符max，用于函数名称。接下来的token是左括号(，依此类推（见图2.6）。

解析器是紧跟在词法分析器之后的组件，解析器的主要输出称为抽象语法树（AST）。这个树代表了编程语言编写的源代码的抽象句法结构。解析器通过将词法分析器产生的token流作为输入，并将其组织成类似树的结构来生成AST。树中的每个节点代表源代码中的一个构造，例如语句或表达式。节点之间的边，表示这些构造之间的关系。

示例程序的AST如图2.7所示，函数（max）有两个参数（a和b）和一个主体。主体在图2.7中标记为复合语句。图2.40中，提供了复合语句的定义，来自C++标准。复合语句由其他语句组成，如return和if。这些语句中使用了a和b变量。可能有读者对Clang为复合语句生成的真实AST感兴趣，其结果如图2.8所示。

解析器进行两种分析：

语法分析：解析器通过分析程序的语法来构建AST。
语义分析：解析器对程序进行语义分析。

解析器的工作是，如果语法分析或语义分析阶段的解析失败，则产生错误消息。如果没有错误发生，那么在语法分析阶段得到一个解析树（或AST），语义分析阶段得到一个语义验证的解析树。可以通过考虑哪些类型的错误在语法分析阶段检测到，哪些在语义分析阶段检测到，来了解这一点。

语法分析，假设程序应该在语言指定的语法规则上是正确的。例如，以下程序在语法上是无效的，因为最后return语句中缺少分号：

int max(int a, int b) if (a > b) return a; return b // missing ;

图2.9：带语法错误的程序代码列表

Clang为该程序产生的输出如下：

max_invalid_syntax.cpp:4:11: error: expected ’;’ after return statement
return b // missing ; ^ ;

图 2.10: 带有语法错误的程序的编译器输出

程序可能在语法上是正确的，但在语义上没有意义。这种情况下，解析器应该检测到语义错误。例如，以下程序在返回值类型使用错误：

int max(int a, int b) if (a > b) return a; return &b; // invalid return
type

图2.11：带有语义错误的程序代码列表

Clang为该程序产生的输出如下：

max_invalid_sema.cpp:4:10: error: cannot initialize return object of
type ’int’ with an rvalue of type ’int *’ return &b; // invalid return
type ^

图 2.12: 带有语义错误的程序的编译器输出

AST主要是在语法分析阶段构建的，但对于某些语言，例如C++，语义分析对于构建AST也是至关重要的，特别是在C++模板实例化方面。

语法分析阶段，编译器验证模板声明是否符合语言的语法和语法规则，包括正确使用关键字，如"template"和"typename"，以及模板参数和主体的形成。另一方面，语义分析涉及编译器执行模板实例化，为模板的特定实例生成AST。模板的语义分析可能相当复杂，因为编译器必须为每个模板实例执行类型检查、名称解析等任务。此外，实例化过程可能是递归的，导致大量代码重复，即代码膨胀。为了对抗代码膨胀，C++编译器采用了模板实例化缓存等技术，最小化生成的冗余代码。

代码生成器是编译器前端最后的组件，其主要目标是生成中间表示（IR）。为此，编译器遍历由解析器生成的AST，并将其转换为称为中间表示或IR的其他源码。IR是语言无关的表示，允许同一中端组件用于不同的前端（FORTRAN与C++）。使用中间表示（IR）的另一个原因是，如果明天有新的架构可用，可以为该架构生成特定的目标代码。由于源语言保持不变，导致IR的所有步骤都将保持不变。IR提供了这种灵活性。

编译器中使用IR的概念已经有几十年的历史了。将源代码的中间表示用于编译过程中的程序源代码的想法随着时间的推移而发展，IR首次在编译器中引入的确切日期并不清楚。

已知在20世纪50年代和60年代的第一代编译器中并没有使用IR，而是直接将源代码翻译成机器代码。到了20世纪60年代和70年代，研究人员开始尝试在编译器中使用IR来提高编译过程的效率和灵活性。

第一个广泛使用的IR是三地址代码，它于20世纪60年代中期在IBM/360的FORTRAN编译器中使用。其他早期的IR示例包括在20世纪70年代引入的寄存器传输语言（RTL）和在20世纪80年代引入的静态单分配（SSA）形式。

今天，在编译器中使用IR已成为标准做法，许多编译器在整个编译过程中使用多个IR。这使得可以应用更强大的优化和代码生成技术。