Software 2.0

编写 Tree-sitter 语法

admin -

在过去的几个月里，我一直在做一个新项目，一个专注于米兰市的仪表板/博客/数据可视化实验，并在此过程中开始关注自动化和验证 WebAssembly、DuckDB SQL、JS、Markdown 和其他东西集成的方法。

我在做这件事时反复遇到的一个概念是解析。我使用工具来解析 Markdown，将 Typescript 转译为浏览器能理解的东西，将模式从 JSON 转换为 Parquet 再转换为 Vega-lite 图表，以及许多其他转换。

我还有一个小毛病，就是尽可能早地验证一切，例如，发现我是否试图显示一个在 DuckDB 查询生成的 Parquet 文件产生的图表中不存在的值。或者可能自动化某些步骤，比如检测哪些值可以显示以及如何显示。这类自动化很难。

不管怎样，这样做我经常想到一个点，那就是能够以编程方式解析和操作代码会很棒。发现类型和函数，允许用户输入可执行的脚本作为配置，报告错误，为还没有宏的语言添加宏（yet）。

但最重要的是，我认为执行这类操作会很有趣（即使它们可能是个坏主意），谁知道呢，有一天甚至可能创建另一种编程语言。你知道的，世界需要另一种！

所以，我开始研究语法、解析器和解析器生成器。这是我多年前在大学的语言和编译器课程中学到的概念，我甚至写了我自己的自顶向下解析器来注释自然语言，但一个完整的语法呢？

1、什么是语法？

生成语法是描述形式语言的一种方式。这里的"形式"意味着语言的规则是明确的，与西班牙语等"自然"语言相反，并且通常可以证明一个字符串是否根据规则有效。作为副产品，我们还可以了解字符串的结构，在其内容中分配标签并找到层次结构（例如，在编程语言中，我们可以有一个包含循环的函数，循环包含语句）。

然而，编写一个实际上能做到这一点的程序是完全不同的事情，这是一个令人着迷的话题，如果你对理论计算机科学感兴趣，我推荐它。从现在开始，我将专注于软件开发中实际使用的语法子集。

让我们想象我们有符号 )、(、+ 和 8。我们可以看到一些字符串是有效的：

  • 8
  • 8 + 8
  • 8 + (8 + (8 + 8)) + 8

而其他的不是：

  • 8 + + 8
  • 8 +
  • 8 + ( 8

生成语法基于一组生成规则，每条规则定义了我们如何用其他符号或终结符（即字母表中的符号，如这里的 +，之所以这样称呼是因为它们不会被任何东西替换）的序列替换一个符号。给定一个特殊的起始符号 S，你可以按任何顺序应用规则，用其他符号替换符号，直到你得到一个只有终结符的序列。以这种方式获得的每个终结符字符串都是有效的。

在这种情况下，我们可以定义这些规则：

  1. S -> E
  2. E -> 8
  3. E -> E + E
  4. E -> ( E )

让我们以表达式 8 + (8 + (8 + 8)) + 8 为例：

  1. 我们从符号 S 开始
  2. 应用规则 3，变成 E + E
  3. 对第一个 E 应用规则 2，得到 8 + E
  4. 对第二个 E 再次应用规则 3，得到 8 + E + E
  5. 对最后一个 E 应用规则 2，得到 8 + E + 8
  6. 对唯一的 E 应用规则 4，得到 8 + ( E ) + 8
  7. 应用规则 3，得到 8 + ( E + E ) + 8
  8. 应用规则 2 两次，得到 8 + (8 + (8 + 8)) + 8

最终字符串仅由终结符组成，因此根据此语法是有效的。

跟踪什么被扩展成什么，我们可以将每个表达式转换为一棵树，称为 AST（抽象语法树）。

给定存储在文件中的语法，解析器生成器（如 ANTLR）可以生成代码来解析该语言并构建 AST。

对于大多数形式语言，如 SQL 或 Python，某处存在生成语法。在 Python 中，你甚至可以使用标准库中的 ast 模块来解析 Python 代码。

其他语言如 Postgres SQL 实现则不太清楚，你必须使用他们的内部解析器或者本质上手工重写语法，因为解析器集成在应用程序的代码中或者是特定于它的（参见 SQLLite's Lemon）。

意识到这一点让我很困惑：形式语言和语法已经存在了几十年，几乎每种语言都有某种语法，所以我一直假设有一些或几个库被所有人使用，同样有一种主流语法格式。事实并非如此！

另一个需要提到的方面是，通常语法是不够的，你还需要一个 lexer。这是一个将大块内容分割成"标记"的工具，这些标记就是终结符。你可以将每个字符作为标记，但实际上通常最好以智能方式分割文本。

例如，Python 和 YAML 使这一点变得至关重要：Python 中的缩进具有语义作用，编写语法来处理每行与前一行具有相同缩进或它是不同块的事实极其复杂。语法在扩展符号时无法真正"记住"缩进。所以，通常解析器生成器附带一个词法分析器（这是编译器人员对分词器的称呼），以及一些语法糖来将其集成到语法定义中。

除此之外，还有大量的解析算法：LR(1)、LALR、Earley、LL 等。

2、计划：首先为 Monicelli 编写语法

为了深入研究这个话题（顺便说一下，我在 ChatGPT 之前就使用了"delve"这个词，这篇文章是由现实世界中的人类撰写的），我决定为一种简单的语言编写语法，看看这个过程是如何工作的。

一旦我有了这个语法，我就可以为它生成一个解析器，并尝试将其集成到网页中（即使用 JS 或 WASM 在客户端运行）或 Python 应用程序中。稍后，我可以尝试为它实现一个解释器或编译器。

我决定继续使用 Monicelli 进行我的实验。Monicelli 是

一种基于意大利喜剧杰作《Amici Miei》中所谓的"supercazzole"的深奥编程语言

如果你不会说意大利语并且不理解这个参考，只知道这是一种非常简单的语言。它支持几种变量类型、函数、循环、switch-case、打印、输入、注释、断言和 panic。

由于该语言已经存在，我可以找到一些 Monicelli 代码示例，我可以只关注语法。此外，任何结果都可能引起其他对该语言好奇的人的兴趣。

3、好的，但我实际上如何创建解析器？？

有很多解析器生成器，据我所知，没有一个被认为是"主流"的。如前所述，许多语言和工具实现自己的东西。不仅如此，甚至没有标准的语法格式！有 Backus-Naur 形式，但即使如此，也有很多方言和变体。

我研究了 ANTLR、Parsimonious、Peggy、Lark、Tree-sitter，可能还有其他五个我记不清的。

ANTLR 是其中最强大的之一，它可以生成 Javascript 或 Typescript，这意味着它可以集成到网页中，甚至可以在 PWA 中离线运行，我认为这是必不可少的。ANTLR 的另一个优点是有一个丰富的现有语法集合，可用于参考和重用。

然而，最终我决定选择 Tree-sitter，主要是因为增量更新功能、文档和庞大的社区。

4、Tree-sitter 简介

Tree-sitter 是一个解析器生成器，它有一个有趣的特性：它可以对输入的变化做出反应并增量更新 AST。然后它可以用于编辑器中以对用户所做的更改做出反应。

事实上，它最初是为 Atom 文本编辑器开发的，并且有 neovim、Emacs、Helix 等的集成。

与 ANTLR 一样，它有大量现有语法，并且可以在浏览器中运行。Python 绑定也非常易于使用（事实上，每种语法开箱即用就是 Python、Javascript、Swift 和 Go 包）。

Tree-sitter 特别专注于在编辑器内的使用，并提供了开箱即用的基于语法的语法高亮机制。

5、编写语法的乐趣

尝试 Tree-sitter 并使用它编写语法后，我可以说我对整个体验的质量感到惊喜，考虑到手头的任务并不常见且传统上是低级的。

安装它就像 npm install -g tree-sitter 一样简单。tree-sitter 命令有一个 init 函数和测试及构建所需的一切。

tree-sitter 语法本质上是一个 grammar.js 文件，以及一些可选的 C 逻辑来定义词法分析器（如 Python 的做法）来处理缩进，如前所述。

语法用 javascript 编写可能听起来很奇怪，但本质上这种语言允许轻松地将语言的重复部分脚本化。

语法规则可以像这样：

non_main_function: $ => seq(
    choice('blinda la supercazzola', 'blinda la supercazzora'),
    optional($.variable_type),
    field('function_name', $.variable_name),
    optional(seq('con', $.function_arguments_def)),
    'o scherziamo?',
    repeat($.statement),
    prec(3, $.return),
),

这定义了一个符号 non_main_function 作为元素的序列（seq），有些是字面字符串（如 o scherziamo? 部分），其他可以重复或命名（使用 field 辅助函数）或成为几个选项之一（choice）。

命令 tree-sitter generate 运行 JS 代码并生成相应的语法作为 JSON 文件以及词法分析器的一些绑定。

测试语法

编写语法的过程相当抽象，你需要测试它。在开始之前，我预计回归将是一个大问题，需要编写一些脚本来针对我的语法测试代码片段。

我很高兴发现 tree-sitter 附带一个 test 命令，它将语法应用于一组给定的输入字符串，并将 AST 与预期的进行比较。

查询

Tree-sitter 附带一个强大的查询函数，允许在 AST 中匹配模式。这对 linter 和重构工具非常有用，但我到目前为止还没有太多使用。

构建语法和高亮

tree-sitter 语法本质上是一个可以从一开始就安装的包。tree-sitter build 命令准备它，它可以作为 Python 包导入（例如）。

由于 Tree-sitter 专注于在 IDE 内的使用，它还允许定义语法高亮。AST 查询可以与标签（例如 comment）匹配，以告诉编辑器可以对文本跨度使用哪种样式。

此外，命令 tree-sitter parse 可以立即为给定的代码片段生成并显示 AST。

结果

我的语法在这里，花了几个小时编写。Tree-sitter 产生的错误相当易读，特别是在处理歧义和优先级时。

6、下一步

到目前为止，这是语法和解析的一个实验。我计划稍后尝试使用这个来编写工具，并希望编写一个到 WebAssembly 的编译器。如果有有趣的结果，我会报告。

原文链接：Writing a Tree-sitter grammar, I found the UX is great!

汇智网翻译整理，转载请标明出处