从零开始构建编程语言的挑战与乐趣

译者 | 刘汪洋

审校 | 重楼

“这本书是经典之作，要好好拜读。”

大约 15 年前，当我刚开始职业生涯并偶然踏入编译器构建领域时，我的团队架构师递给我一本 《龙书》，并强调这是一部经典之作，需要倍加珍惜。不过不幸的是，有一天晚上我阅读时不慎睡着，书本从手中滑落，重重地落在地板上。还书的时候，我非常希望他没注意到封面上的那个小凹痕。

《龙书》首版发行于 1986 年，那时构建编译器是一项极具挑战性的任务，它集计算机科学和编程技术、艺术之大成。近四十年后，我再次面对这一挑战。如今，这项任务的难度又是怎样的呢？接下来，让我们深入探讨创建一种新语言所涉及的内容，以及现代工具如何简化这一过程。

目标语言

为了更明确我们的目标，我们会构建一个具体的语言。我发现用实际案例来说明，比理论模型更有效。因此，我选择了我们在  ZenStack 开发的 ZModel 语言作为例子。ZModel 是一种用于建模数据库表和访问控制规则的领域特定语言（DSL）。为了保持文章的简洁，我只展示其中的部分功能。我们的目标是编译下面的代码：

model User {
  id Int
  name String
  posts Post[]
}

model Post {
  id Int
  title String
  author User
  published Boolean

  @@allow('read', published == true)
}

这里简要说明几点：

• model 关键字用于定义一个数据库表，其字段对应表中的列。
• 模型可以相互引用，构建关系。在此例中，User 和 Post 模型构成了一对多关系。
• @@allow 关键字用于定义访问控制规则。它接受两个参数：一个是访问类型（“create”、“read”、“update”、“delete” 或 “all”），另一个是布尔表达式，用于判定是否允许该操作。

让我们开始动手编译这段代码吧！

注：ZModel 是  Prisma Schema Language 的扩展版本。

六个步骤构建编程语言

第 1 步：从文本到语法树

尽管多年来编译器的构建步骤基本保持不变，但一些高级语言构建工具已经能够简化这些步骤。这些工具可以直接将文本转换成语法树。构建过程首先需要一个词法分析器（lexer），它将文本分解成标记（tokens）。然后，解析器（parser）会将这些标记组织成解析树（parse tree）。现代工具往往可以将这两个步骤整合，直接从文本生成语法树。

我们采用了 Langium，这是一个基于 TypeScript 的开源软件工具包，专门用于语言构建。Langium 提供了直观的领域特定语言（DSL），让我们能够定义词法和解析规则。

值得一提的是，Langium DSL 本身也是用 Langium 构建的。这种自我递归的过程，在编译器领域被称为自举（bootstrapping）。通常，编译器的最初版本需要用另一种语言或工具来编写。

下面是我们的 ZModel 语言的正式语法定义：

grammar ZModel

entry Schema:
    (models+=Model)*;

Model:
    'model' name=ID '{'
        (fields+=Field)+
        (rules+=Rule)*
    '}';

Field:
    name=ID type=(Type | ModelReference) (isArray?='[' ']')?;

ModelReference:
    target=[Model];

Type returns string:
    'Int' | 'String' | 'Boolean';

Rule:
    '@@allow' '('
        accessType=STRING ',' condition=Condition
    ')';

Condition:
    field=SimpleExpression '==' value=SimpleExpression;

SimpleExpression:
    FieldReference | Boolean;

FieldReference:
    target=[Field];

Boolean returns boolean:
    'true' | 'false';

hidden terminal WS: /s+/;
terminal ID: /[_a-zA-Z][w_]*/;
terminal STRING: /"(\.|[^"\])*"|'(\.|[^'\])*'/;

这个语法定义清晰且易于理解，包含两个主要部分：

• 词法规则底部的终结符规则定义了如何将源文本分解为标记。我们的简单语言包含标识符（ID）和字符串（STRING）两种标记类型。空格字符在这里被忽略。
• 解析规则其他部分是解析规则，决定了如何将标记流组织成一棵树。解析规则中也包含关键字（如 Int、@@allow），这些关键字同样参与词法分析。在更复杂的语言中，可能会出现递归的解析规则（例如，嵌套表达式），这需要特别注意设计，但我们的示例语言结构较为简单，暂不涉及此类情况。

通过定义好的语言规则，我们可以利用 Langium 的 API 将示例代码转换成如下解析树：

第 2 步：从语法树构建链接树

解析树极大地帮助我们理解源代码的语义。但为了进一步完善解析树，我们还需要进行一些额外的步骤。

在我们的 ZModel 语言中，出现了“循环引用”的情况。例如，User 模型的字段被 Post 模型的 author 字段引用。当我们浏览解析树时，会遇到引用“Post”这个名字的节点，但无法直接得知“Post”具体指代什么。虽然可以进行特定的搜索来找到匹配的模型名称，但更系统的做法是执行一次“链接”操作，将这些引用解析并链接到它们的目标节点。完成这一链接后，我们的解析树将转变为如下所示（为了简化展示，这里只展示树的一部分）：

从技术角度看，此时的结构更像是图而非树，但我们依旧习惯性地称之为解析树。

Langium 在这方面有显著优势，它能自动完成大部分链接工作。这个工具遵循解析节点的嵌套层次，利用这一结构构建“作用域”。它解析遇到的名称，并将它们链接到正确的目标节点。在语言较为复杂的场景中，可能会遇到需要特别处理的情况。Langium 允许用户自定义实现几个服务，从而简化这个过程，让链接操作更加高效。

第 3 步：从链接树到语义正确性检查

如果源文件包含词法或解析错误，编译器会报错并终止处理。

例如：

model {
  id
  title String
}

编译器可能会报如下错误：

期望的是 'ID' 类型的标记，但实际发现 `{`。[第1行，第7列]

但是，代码即使没有词法或解析错误，也不一定在语义上正确。以以下代码为例，它在语法上是有效的，但在语义上却是错误的。原因是将 title 与 true 进行比较是无意义的操作。

model Post {

  id Int

  title String

  author User

  published Boolean

  @@allow('read', title == true) //