标准的学术文献对极端前端（解析）和极端后端（SSA、指令选择和代码生成）最有用，但忽略了中端。如果您想学习如何构建，例如下一个 LLVM：一个胖后端和一个非常瘦的前端，这很好。

但是如果你在 LLVM 之上构建一个编译器，这样它就是前端 和中间端呢？语义分析、类型检查和声明规则检查是现代编译器最重要的部分，因为这是进行所有重要诊断（除了语法错误）的地方。

本文包含我为 Austral 编写编译器时学到的一些经验， Austral是一种新的线性类型系统编程语言，我已经研究了一段时间。前几节是高级部分，其余部分最具体是使用 OCaml 编写编译器。

原型编译器

  1. 600 页解析理论。
  2. 三页的类型检查像 C 这样的一阶类型系统。
  3. 关于存储和检查声明正确性的零页（“符号表”）。
  4. 编译模型上的零页，高效实现单独编译。
  5. 450 页关于优化和代码生成。

内容

  1. 实施策略
  2. 只需使用 OCaml
  3. 只需使用 Menhir
  4. 什么测试有用
  5. 编译模型
  6. 代码组织
  7. 引导问题
  8. 环境
  9. 识别声明
  10. 错误
  11. 评论

实施策略

将编译器想象为 2D 网格。这些行是编译的阶段：从解析到中间端，再到后端。这些列是正在实现的编程语言的不同方面。对于像 C 这样较小的语言，不同的方面是：全局变量声明、枚举声明、类型声明、函数声明，仅此而已。更有特色的语言增加了额外的方面：C++ 中的接口和类定义， trait以及implRust 中的定义等。

如何编写一个 OCaml/Austral 编译器？插图

广义上，有两种实现编译器的方法。在瀑布 策略中，每个阶段一个接一个地实现：完整的解析器，然后是完整的语义分析过程，然后是完整的类型检查过程，最后是后端阶段。

如何编写一个 OCaml/Austral 编译器？插图1

可以在每个阶段完成后编写测试，这可能有助于捕获错误，因为较浅的管道意味着寻找错误来源的地方更少。当您只有端到端测试时，很难确定在具有数十个中间表示的编译器中发生错误的位置。

缺点是“你好，世界！” 需要很长时间。在为现有语言编写编译器时，这并不重要。但是在构建一门新语言时，你想要一些可以在早期阶段使用的东西，这样你就可以找到语言设计中突出的地方、需要完善的地方以及语言的语用学是什么。

然而，发展压力和权宜之计的现实意味着最终结果看起来更像：

如何编写一个 OCaml/Austral 编译器？插图2

通常会忽略错误诊断和语义分析检查。

另一种选择是垂直策略，在开发开始时，您实现编译的所有阶段，但它们什么都不做。解析器解析空文件，ASTs 类型是空的或只有敷衍的占位符情况，后端什么也不发出。然后你实现每个语言方面，一次一个。

如何编写一个 OCaml/Austral 编译器？插图3

这样做的好处是，从一开始您就有一个可以调用和测试的编译器。从一开始就进行端到端测试在确保编译器实现语言定义和识别回归方面都是一个巨大的好处。

在瀑布策略中，您可以专注于确保编译的每个阶段都是正确的，而在垂直策略中，您可以专注于确保正在实现的语言的每个方面都是正确的。

问题是您没有实现该语言，而是该语言的一系列同心子集，直到您实现功能完整性。

Austral 的编译器是用一种非常无原则的瀑布式策略编写的：我逐步进行，但省略了一些难以实现的功能、诊断和检查，然后返回并填充这些内容。我感觉垂直推进的策略更好，但我不能赞同这两种策略，因为我没有比较它们。

只需使用 OCaml

我的驱动器中有一个完整的半成品编译器项目和玩具解释器的墓地，从 C、C++、Common Lisp、标准 ML、Java、Haskell 和 OCaml 应有尽有。

OCaml 位于语言空间中用于构建编译器的舒适位置。它有足够的教程和实用文档来提高生产力。它具有您想要的所有函数式编程功能：代数数据类型和模式匹配以及穷举检查。但它并不太严格，如果你愿意，你可以编写命令式代码。

而且 OCaml 也不是很笨，所以你不必被推迟。您可以忽略大部分语言并编写简洁、熟练的 OCaml 来解决问题，并且不会让潜在的贡献者摸不着头脑。

与大多数现代应用程序不同，编译器的不同之处在于它们很少需要大型生态系统。一个好的解析器生成器就是你所需要的，所以使用像 OCaml 这样更晦涩的语言并不需要付出太多的成本，比如用 Haskell 和 Python 编写一个 Web 应用程序。您不会发现自己必须从头开始重新发明整个生态系统，因为您需要的依赖项很少不存在。

只需使用 Menhir

你需要一个解析器。这是编译器中最令人麻木的部分。手工编写解析器很棘手，不值得所谓的性能提升1。解析性能可能不会成为瓶颈。

解析器组合器非常流行。您可以通过将语法参数化为函数来将它们参数化，这很可爱。但是解析器组合器的问题在于它们实现了解析表达式语法。PEG 也很受欢迎，但它们太死板了。

在 PEG 中，析取或选择运算符（通常用管道字符 表示|）是有序选择。foo := a | b | c如果您有一个像

在 PEG 中——因此，在解析器组合器中——选择是按照它们列出的顺序来尝试的。这导致了巨大的头痛。

像左递归这样的东西会导致难以调试无限循环，你将不得不扭曲你的语法以适应 PEG 的规则。最终结果看起来不像 吸引所有人的可爱的解析器组合器单行器。

像 Menhir 或 ANTLR 这样的老式解析器生成器没有这个问题。选择是无序的，就像您在语言规范中找到的 EBNF 符号一样。左递归是“智能地”实现的，通常不需要你转换你的语法。

Menhir 是一个成熟的解析器生成器。它被集成到 OCaml 的构建系统中： dune。文档不错，但是有足够的实用教程可以帮助您入门。

什么测试有用

大致有两种测试：

  1. 单元测试是用与编译器相同的语言编写的。在我的例子中，OCaml。
  2. 端到端测试。在这里，您有一个将编译器视为黑盒的测试运行器：一个使用命令行参数调用的二进制文件。测试可以检查编译是否失败并产生一组预期的错误消息，或者编译成功并且生成的程序在执行时产生预期的输出。

您应该首先编写端到端测试。是的，它们是粗粒度的，它们可能无法帮助您准确找出错误在编译器中的位置。但好处是他们将编译器视为一个黑匣子，它允许您迭代编译器的内部而不导致测试中断。只要 CLI 界面保持不变，您就可以更改 AST 结构、中间表示、通道、环境表示、后端等所有内容。这对于事物快速变化的早期开发很有用。

花时间编写一个好的端到端测试运行程序对于 Austral 编译器的开发来说是一个巨大的福音。我希望我早点做到。

为通过的每个方面进行大量非常具体的单元测试主要在编译器达到其内部已修复的成熟阶段时很有用。如果您仍在对内部进行迭代，那么这些测试是一种负担：它们无法编译（由于您对编译器代码所做的更改）比捕获错误的频率更高。

警告：语言的不同之处在于它们编写测试的方便程度，而方便的是编写的内容。例如，我发现自己用 Python 编写的测试比用 OCaml 编写的测试多得多。部分原因是 Python 在编译时做出的保证较少，部分原因是 Python 的活力使测试自动发现等事情变得更容易。

编译模型

最简单的编译器是全程序编译器：它一个接一个地处理一组有序的文件，并为整个文件生成生成的代码。模块依赖 DAG 可以拓扑排序为线性顺序。

对于 MVP 语言，这很好，因为用该语言编写的代码很少。问题在于可扩展性：大型代码库的整个程序编译本质上很慢。

能够以高频率进行类型检查、编译和运行代码使开发不那么令人沮丧。必须等待十秒钟来构建数十万行代码，从头开始，因为您所做的每一次更改都令人沮丧。性能需要单独编译。

单独编译需要仔细考虑。这不能是语言设计的事后想法：您必须在设计语言的模块系统和编译模型时考虑到单独的编译。从一开始就弄清楚并勾勒出这一点是个好主意。

代码组织

将中间表示与 pass分开通常是好的。前者是类型，后者是一组函数。这有助于使模块保持简短和重点。此外，从 IR 到通道并不总是一对一的映射，您将在同一表示上运行多个不同的分析通道。

例外情况是它会破坏封装。有时您希望类型是不透明的，以便定义它们的模块可以强制它们的内容不变量。

引导问题

（本节仅适用于新的编程语言，不适用于 Fortran）

编译器通常是用它们编译的语言编写的。这表明该语言已经足够成熟，可以处理构建编译器这一不平凡的任务，而且它也使贡献变得更容易，因为贡献者只需要了解一种语言，而不是同时了解宿主语言和实现语言。

所以，你决定构建一种新的编程语言，但你不能用一种不存在的语言编写编译器。这里的基本思想是：

  1. 用 OCaml 之类的语言编写引导编译器。
  2. 用您的新语言编写自托管编译器，并使用引导编译器来构建它。

你什么时候从1转到2？编写最简单、最愚蠢的 MVP 编译器是一个好主意：它可以让您及早使用该语言进行迭代，看看什么是有意义的，什么是没有意义的。在这个阶段立即开始构建生产编译器是一个坏主意：构建编译器很困难，如果你唯一的工具是一个摇摇晃晃的 MVP 编译器，由 spit 和 bailing 线连接在一起，那么编写自托管编译器将花费更长的时间，而且比应有的更令人沮丧。

引导编译器没有设置到期日期。您可以迭代地改进它，直到对该语言有足够的兴趣和用户来证明编写第二个生产质量编译器的时间投资是合理的。

如果迭代改进太慢，可以走 Fred Brooks 的路线：扔掉第一个。在 OCaml 中构建一个脑残的简单引导编译器，然后从头开始将其重写为生产质量的编译器——但仍然在 OCaml 中。然后只有在语言足够成熟以至于值得这样做时才迁移到自托管编译器。

环境

环境（也称为符号表，尤其是在类 C 语言的编译器中）是存储用户声明（如类型定义和函数定义）的地方。这是编译器中的中心数据结构。

类型检查很容易成为现代语言编译器的最大部分，它需要对环境的普遍访问。例如，要对函数调用进行类型检查，您需要来自环境的函数签名。构造函数调用需要定义正在构造的类型，该类型来自环境。该环境也是存储额外信息的自然场所，这些信息并非编译所必需的，但可以让您提供更丰富的诊断信息，例如交叉引用图。API 文档生成器基本上可以从环境中提取它需要的所有信息。

尽管环境处于中心地位，但编译器文献通常会掩盖它，原因有两个：

  1. 首先，大多数教科书编译器都是针对相对简单的类 C 语言的。由于 C 没有显式模块和全局命名空间，并且只有四种声明（全局变量、枚举、类型和函数），因此环境可以非常简单：它实际上只是一个从声明名称到定义的哈希表。
  2. 编译器教科书通常关注源文本的可执行部分：函数体。这是大多数优化、控制流分析、SSA、代码生成等发生的地方。

语言决定了环境的复杂程度。C 和 C++ 可以有相对简单的环境。Ada 的模块系统比较复杂，相应的环境也比较复杂。因此，其中一些建议不能跨语言移植，并且可能缺少一种适用于另一种的环境数据结构。

Austral 是一种相对简单的语言。代码按模块组织，这些模块具有名称，并且是非分层的2。模块包含声明，其中有六种：常量、记录、联合、函数、类型类和类型类实例。除了类型类实例之外的所有声明都可以通过名称来标识。

在 Austral 编译器中，环境是一种只能通过 API 访问的不透明类型。在内部，它是一组表，其中每个表存储一种不同类型的语言对象。有一个模块表，其行如下所示：

type mod_rec = ModRec of {
      id: mod_id;
      name: module_name;
      interface_file: file_id option;
      interface_docstring: docstring;
      body_file: file_id;
      body_docstring: docstring;
      kind: module_kind;
      (** Whether or not the module is unsafe. *)
      imported_instances: DeclIdSet.t;
      (** The set of imported typeclass instances. *)
      imports_from: ModIdSet.t;
      (** The set of modules this module imports from. *)
    }

除此之外，还有一个声明表、一个类型类实例方法表和一个单态表（用于实现泛型）。

该环境有一个简单的 CRUD API，每个函数基本上都执行完整性检查，例如确保在同一个模块中没有两个同名的声明。

行由键入的 ID 索引，但可以在适用的情况下按名称检索，或者在必要时通过行上的谓词检索。

一个表中的行可以使用类型标识符引用另一个表中的行。CRUD 函数可以强制执行关系完整性，例如，确保如果您将类型类实例添加到环境中，它链接到的类型类已经存在。

因此，环境只是存储不同特定语言结构的表的记录。这个想法来自阅读 Coalton的源代码，这是一种类型化的、受机器学习启发的 Lisp，由Robert Smith构建在 Common Lisp 之上 ，您应该在 Twitter 上关注他。

在早期版本的 Austral 编译器中，环境与语言结构的结构相匹配：它是从模块名称到模块对象的映射，而模块对象基本上是从声明名称到声明对象的映射。但是对深度嵌套的结构进行更新是不方便的。所以这里的具体教训是：保持环境平坦。

如果我有时间重构环境，我想我会像这样构建它。首先，按照以下方式定义一个接口：

module type ENVIRONMENT = sig
    type id
    type row
    type row_input
    type table

    val empty : table

    (* Create *)
    val store : table -> row_input -> id

    (* Retrieve *)
    val get : table -> id -> row option
    val filter : table -> (row -> bool) -> row list

    (* Update *)
    val replace : table -> id -> row_input -> table

    (* Delete *)
    val delete : table -> id -> table
end

（row_input基本上是row但没有 ID。创建 ID 的唯一方法应该是向表中添加一行。因此表必须保留一个内部行 ID 计数器。）

这是最基本的接口，完全依赖 ID 来识别行。大多数（但不一定是所有）语言结构都可以通过名称来识别，因此创建一个更具体的接口是合理的：

module type NAME_ENVIRONMENT = sig
    include ENVIRONMENT

    type name

    val get_by_name : table -> name -> row option
end

然后我会像这样实现不同的环境（为简单起见省略一些细节）：

module ModuleEnv : NAME_ENVIRONMENT = sig
    type id = mod_id

    type name = module_name

    type row = { id: mod_id; name: module_name; docstring: string; }

    type row_input = { name: module_name; docstring: string; }

    type table = { next_row_id: int; rows: row list }

    (* ... functions implemented here ... *)
end

type decl =
  | ConstDecl of { name: identifier; type: ty; value: expr }
  | RecordDecl of { name: identifier; typarams: typarams; fields: field list }
  | ...

module DeclEnv : NAME_ENVIRONMENT = sig
    type id = decl_id

    type name = identifier

    type row = { id: decl_id; name: identifier; decl: decl; }

    type row_input = { name: identifier; decl: decl; }

    type table = { next_row_id: int; rows: row list }

    (* ... *)
end

最后将所有环境包装成一个env类型：

type env = Env of {
    module_env: ModuleEnv.table;
    decl_env: DeclEnv.table;
    ...
}

API 由围绕底层表模块中的env函数的薄包装器组成，以及您必须强制执行的任何完整性检查。对于函数式实现，插入声明的函数将：

  1. 将声明环境从env.
  2. 使用 对其进行变异DeclEnv.store。
  3. 将其替换回env实例。
  4. 退回新的env.

识别声明

您需要一种识别声明的方法，以便 AST 节点可以指向它们。大多数声明都可以通过它们的名称来识别。如果你有：

namespace foo {
    void bar();
}

然后函数bar可以通过字符串来识别foo::bar。在大多数语言中，这就是它所需要的。但是一些语言——Haskell、Rust、Austral——有没有识别名称的声明。即，键入类/特征实例：

class Foo a where
  foo :: a -> String

instance Foo Int where
  foo _ = "Int"

instance Foo Float where
  foo _ = "Float"

实例不是通过名称而是通过(typeclass name, type)对来标识的。

引用声明的统一、通用、类型安全的方法是简单地使用类型化的、不透明的标识符，如下所示：

type module_id
type decl_id

或者，如果您想更具体：

type module_id

type decl_id =
  | DeclIdConst of const_id
  | DeclIdType of type_id
  | DeclIdFunc of func_id
  | DeclIdClass of class_id
  | DeclIdInstance of instance_id

type const_id
type type_id
type func_id
type class_id
type instance_id

类型标识符的自由度比字符串少。此外，您可以设计您的 API，使声明标识符不能手动构造，而是只能通过在环境中存储声明来创建：

val store_constant_decl : env -> (name * type * value) -> (env * const_id)

错误

最初，我想有一些类似的东西：

open Identifier
open Type

type err =
  | NoSuchName of identifier
  (** No identifier with name found in the environment. *)
  | TypeMismatch of { expected: ty; got: ty; }
  (** Type error: expected a type other than what we got. *)
  |
  ...

错误只是不同错误情况的巨大变体。这样做的问题是依赖关系：模块必须从 模块Error中导入（表示 Austral 类型的类型） 。这意味着这些模块不会引发错误，因为导入 模块将是一个循环依赖。这是一个问题，因为添加了新类型的错误。identifierIdentifiertyTypeError

一种解决方案是将每个模块分成两个：一个具有类型的模块，另一个具有功能的模块，例如Type和TypeSystem。然后 Error可以只导入类型，并且其中包含实际代码（并且可能引发错误）的模块可以导入该Error模块。这打破了封装：有时，您想要隐藏在接口后面的不透明类型。是的，即使在函数式编程中也是如此。

我目前有一个更好的解决方案：

(** An Austral compiler error. The module name, span, and source context rarely
    have to be passed in explicitly: they are added where the error is throw in
    the context of {!adorn_error_with_span}. *)
type austral_error = AustralError of {
      module_name: module_name option;
      (** The name of the module where the error occurred, if available. *)
      kind: error_kind;
      (** The error kind. *)
      text: err_text list;
      (** The error text. *)
      span: span option;
      (** The source span where the error happened, if available. *)
      source_ctx: source_ctx option;
      (** The source code where the error happened, if available. *)
    }

(** Represents a category of errors. *)
type error_kind =
  | ParseError
  (** A parse error. *)
  | TypeError
  (** A type error. *)
  ...
  | InternalError
  (** An internal error in the compiler. *)

(** An individual error text element. *)
and err_text =
  | Text of string
  (** Human-readable prose. *)
  | Code of string
  (** Austral text, like the name of an identifier or a type. *)
  | Break
  (** A paragraph break. *)

Anaustral_error是一个相当通用的记录，它存储：

  1. 引发错误的模块的名称。
  2. 种类（本质上是打字的标题）。
  3. 发生错误的源范围（文件、行/列间隔）。
  4. 源上下文，即给定跨度的源代码加上前后几行。
  5. err_text最后，使用类型的错误信息。这本质上是一种非常简约的标记语言，因此我们可以将文本呈现到控制台和 HTML。

这是作为值的错误。您可以将其包装在异常中：

(** The exception that carries Austral errors. *)
exception Austral_error of austral_error

错误是这样构造的：

AustralError {
    module_name = None;
    span = None;
    source_ctx = None;
    kind = TypeError;
    text = [
        Text "Expected a value of type";
        Code (type_string a);
        Text ", but got a value of type";
        Code (type_string b);
    ];
}

然后被包裹在一个异常中抛出。

模块名称、跨度和源上下文是可选的，因为它们不必在引发错误的地方传递。相反，调用树更高的代码可以捕获错误，将上下文信息放入，然后重新抛出错误。这意味着您不必一直沿调用树向下传递上下文信息，只需将其添加到方便的位置即可：

(** Run the callback, and if it throws an error that doesn't have a span, put
    the given span in the error and rethrow it. *)
let adorn_error_with_span (new_span: span) (f: unit -> 'a): 'a =
  try
    f ()
  with Austral_error error ->
    let (AustralError { module_name; kind; text; span; source_ctx }) = error in
    (* Does the error we caught already have a span? *)
    match span with
    | Some _ ->
       (* The error already has a span, do nothing. *)
       raise (Austral_error error)
    | None ->
       (* Create a new AustralError object with the new span, and rethrow it *)
       let new_err = AustralError { module_name; kind; text; span = Some new_span; source_ctx } in
       raise (Austral_error new_err)

然后，拥有一个 ID 就是声明存在的证明。

评论

编写具有有用诊断功能的正确、生产质量的编译器是一项既困难又耗时的工作。然而，它可能是软件工程中最有价值的工作，因为编译器在开始时通过一个非常狭窄的接口与复杂的现实世界进行通信：解析器。除此之外，您有很大的自由来尝试组织软件的新方法，您可以随心所欲地保持原创和前卫。

脚注

  1. 如果您有一个带有自动生成解析器的工作编译器，并且分析表明您花费了大量时间进行解析，那么您是否可以手动编写一个更快的解析器可能值得研究。一如既往：测量。
  2. 与 Java、Common Lisp 和 Haskell 等语言一样，Austral 中的模块是“概念上”但“实际上”不是分层的。也就是说，您可以拥有一个名称类似于 的模块App.Core.Storage.Sql，并且这些点用于创建模块名称的概念层次结构。但是模块命名空间是从模块名称到模块的平面映射。