webmaster@21cto.com

登录注册

构建一种编程语言需要多少工作？

场长

编程语言 0 555 2024-04-18 07:52:02

导读：如果上天给个机会创建一门新语言，你该怎么办？有理由说“不”吗？

“这本书是部经典，请尊重它”。

我的团队架构师递给我一本称为《龙之书》的书时这么说道。

大概在 15 年前，在职业生涯的早期阶段，我无意中进入了构建语言编译器的领域。不幸的是，我晚上读它的时候睡着了，把它重重地扔在了地板上。我非常希望在归还它时，没有被发现封面上的小凹痕。

《龙之书》

这本书写于 1986 年。当时构建编译器极具挑战性，它凝聚了计算机科学和编程中的许多艺术和技术。差不多四十年后，我再次胜任了这份工作。现在有多难？让我们探讨一下创建语言涉及哪些内容以及现代工具在多大程度上简化了它。

目标语言

我们需要构建一些具体的语言来帮助理解事物。我一直觉得现实世界的例子比玩具更有效，所以我将使用我们在ZenStack构建的 ZModel 语言作为示例。

它是一种用于对数据库表和访问控制规则进行建模的 DSL。为了使帖子简短，我将仅使用一小部分功能进行演示。

我们的目标是编译以下的代码片段：

model User {  User {
    id Int
    name String
    posts Post []  }
model Post { 
   id Int   title String   author User   published
   Boolean @@   allow ( '   read ' ,published== true ) }

有必要向大家做一些快速说明：

模型语法表示数据库表；它的字段映射到表格的列。
模型可以相互引用以形成关系。在上面的代码示例中，User和模型Post形成一对多关系。
语法@@allow表示访问控制规则。它有两个参数：一个用于访问类型（“创建”、“读取”、“更新”、“删除”或“全部”），另一个指示是否允许访问的布尔表达式。

就是这样。让我们卷起袖子编译这个东西吧！

ZModel 是Prisma Schema Language的超集。

六步创建新编程语言

第 1 步：从文本到语法树

多年来，构建编译器的一般步骤没有太大变化。你首先需要一个词法分析器将文本分解为“标记”，然后需要一个解析器将标记流构造成“解析树”。

高级语言构建工具倾向于将这两个步骤结合起来，并允许你一步从文本到树。

下面使用Langium OSS 工具包来帮助我们构建该语言。它是一个优秀的基于 TypeScript 的语言工程工具，可以简化语言构建的整个过程。Langium 提供了直观的 DSL 供你定义词法分析和解析规则。

Langium DSL 本身是用 Langium 构建的。这种递归在编译器术语中称为引导。编译器的初始版本必须使用另一种语言/工具编写。

我们的 ZModel 语言，语法可以形式化如下：

grammar ZModelZModel

entry Schema:
    (models+=Model)*;

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

Field:
    name=IDtype=(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模型的posts字段引用Post模型。模型Post引用其作者字段。当我们遍历解析树时，如果我们到达一个ModelReference节点，我们会看到它引用了一个名称“Post”，但无法直接知道它的含义。

您可以进行临时查找来查找具有匹配名称的模型，但更系统的方法是执行“链接”传递来解析所有此类引用并将它们链接到目标节点。完成此类链接后，我们的解析树如下所示（为简洁起见，仅显示了树的一部分）：

从技术上讲，它现在是一个图而不是一棵树，但按照惯例，我们将继续将其称为解析树。

Langium 的优点在于，在大多数情况下，该工具可以帮助自动完成链接过程。它遵循解析节点的嵌套层次结构，并使用它构建“范围”来解析遇到的名称并将其链接到适当的目标节点。对于复杂的语言，在某些情况下您需要有特殊的解析行为。Langium 允许您通过自定义实现多个服务来挂钩链接过程，从而使这一切变得简单。

步骤 3. 从链接树到语义正确性

如果输入源文件包含词法分析器或解析器错误，编译器将报错并停止运行。

model {
  id
  title StringString
}

Expecting token of type 'ID' but found `{`. [Ln1, Col7]

但是呢，没有此类错误并不意味着代码在语义上是正确的。

例如，以下内容在语法上是有效的，但在语义上是错误的。title跟它比较，true表示并无意义。

model Post { Post {
    id Int
    title Stringauthor
    User published Boolean @@   allow   ( ' read ' , title== true ) //<-比较应该无效}

语义规则通常是特定于语言的，并且工具也不能自动执行任何操作。Langium 让你做到这一点，它的方式是提供用于验证不同节点类型的钩子。如下代码：

exportfunctionregisterValidationChecks(services: ZModelServices) {
  const registry = services.validation.ValidationRegistry;
  const validator = services.validation.ZModelValidator;
  constchecks: ValidationChecks<ZModelAstType> = {
    SimpleExpression: validator.checkExpression,
  };
  registry.register(checks, validator);
}

exportclassZModelValidator {
  checkExpression(expr: SimpleExpression, accept: ValidationAcceptor) {
   if (isFieldReference(expr) && expr.target.ref?.type !== 'Boolean') {
     accept('error', 'Only boolean fields are allowed in conditions', {
       node: expr,
     });
   }
  }
}

我们现在可以得到一个关于语义问题方面很好的错误：

Only boolean fields are allowed in conditions [Ln 7, Col 19]

与词法分析、解析和链接不同，语义检查过程不是声明性或系统性的。对于复杂的语言，你需要使用命令式代码编写一些规则。

步骤 4. 完善开发者体验

如今的创建开发工具门槛在提高。一项技术创新想要发挥有效的作用，需要让人感觉良好才能有机会蓬勃发展。

从语言和编译器方面来说，开发者体验在以下3个方面展现：

IDE 支持

出色的 IDE 支持，包括语法突出显示、格式化、自动完成等，可以极大地降低了学习曲线，能够有效提高了开发人员“生活质量”。

我喜欢 Langium 的一件事是它对语言服务器协议的内置支持。解析规则和验证检查会自动成为一个不错的默认 LSP 实现，直接与 VSCode 和最新的JetBrains IDE配合使用（虽然有限制）。

然而，为了提供出色的 IDE 体验，我们仍然需要通过覆盖 Langium 的 LSP 相关服务的默认实现来进行大规模改进。

错误报告

在大多数情况下，你的验证逻辑会生成错误消息，这个消息的准确性和有用性，将在很大程度上决定开发者理解错误并采取行动修复错误的速度。

调试

如果你的语言想要“运行”，那么调试经验是要必须要具备的。调试取决于编程语言的性质，如果它是涉及语句和控制流的命令式语言，则需要单步执行与状态检查。如果它是声明性的，调试可能意味着可视化有助于理清复杂性（规则、表达式等）。

步骤5：让它变得有用

导出一个已解析且无错误的解析树非常酷，但它本身并不是很有用。

我们有几个选项可以从那里继续并从中生成实际值：

就停在那里
你可以让运行停在这里，并抛出声明解析树的结果，然后让你的用户决定如何处理它。
将其转换成其它语言
通常，一种语言会有一个“后端”来将解析树转换为较低级别的语言。比如，Java编译器的后端生成JVM字节码。TypeScript 的后端生成 Javascript 代码。在我的ZenStack，我们将 ZModel 转换为 Prisma Schema Language。然后，目标语言的工具/运行时可以将它作为输入。
实现可插拔的转换机制
你还可以实现插件机制，让你的语言用户提供后端转换。这是一种更具结构性的方法来实现。
构建一个运行时来执行解析树。
这是构建语言最“完整”的路线。你可以实现一个解释器来“运行”已解析的代码。无论“运行”意味着什么，完全取决于你自己。
在我的 ZenStack里，除了将 ZModel 转换为 Prisma Schema Language 之外，我们还有一个运行时来解释访问控制规则，以便在数据访问期间强制执行它们。