创建 Tree-sitter 语法

Neovim 中我最喜欢的功能之一就是 Tree-sitter 集成。它既能提供快速、即使在出错状态也能正常工作的语法高亮（在编辑代码时这种情况很常见），又带有额外的语义（可以区分函数参数和局部变量）。

借助 nvim-treesitter-textobjects，你还可以在节点之间跳转（例如用 ]c 跳到下一个类）或精确删除（用 cif 删除函数体并进入插入模式）。这是一个非常棒的功能，因为它跨语言通用——只要语言有 Tree-sitter 语法（大多数语言都有），无论语法长什么样都能工作。

不过，你可能会好奇 Tree-sitter 语法到底长什么样，又如何为一种语言创建它？

我开始思考这个问题，不知不觉间就开始为 Djot（一种类似于 Markdown 的标记语言）尝试编写自己的解析器。网上有一些不错的入门教程，但更深入的内容就找不到了。

我花了不少时间摸索——同时刷新了我 10 年前学过的语法知识——并决定把一些心得记录下来。

这篇文章稍微有点刹不住车，会涉及以下内容：

如何使用外部扫描器
使用 Tree-sitter 内置的冲突消解
语言注入实现语法高亮
在 Neovim 中使用该语法进行语法高亮和文本对象操作
把语法嵌入到本博客中实现语法高亮

我们将要开发的完整语法的源代码可以在 Codeberg 上找到。

1、我们的子集

为了这篇博客文章，我们将实现 Djot 的一个小子集，支持：

段落
Div
代码块
强调

这样我们就能解析如下这样的标记：

This is a
multiline _paragraph_

:::
This is a paragraph inside a div
:::

```gleam
let x = 2;
```

（没错，sdjot 的高亮用的就是我们的语法。）

乍一看，这么简单的内容似乎不需要比几条简单语法规则更复杂的东西，但后面我们会发现，即使是这些简单规则，要完整支持也需要多花不少功夫。

2、简单的开端

这篇文章的目的不是讲解 grammar.js 中的 Tree-sitter 语法描述是如何工作的。 Tree-sitter 文档介绍了如何入门。我把项目命名为 sdjot，下面是我们起步用的 grammar.js：

module.exports = grammar({
  name: "sdjot",

  // Skip carriage returns.
  // We could skip spaces here as well, but the actual markup language
  // has significant spaces in some places, so let's remove them here too.
  extras: (_) => ["\r"],

  rules: {
    document: ($) => repeat($._block),

    // All blocks should end with a newline, but we can also parse multiple newlines.
    _block: ($) => choice($.div, $.code_block, $.paragraph, "\n"),

    // A div contains other blocks.
    div: ($) =>
      prec.left(seq($.div_marker, "\n", repeat($._block), $.div_marker, "\n")),
    div_marker: (_) => ":::",

    // Code blocks may have a language specifier.
    code_block: ($) =>
      seq(
        $.code_block_marker,
        optional($.language),
        "\n",
        optional($.code),
        $.code_block_marker,
      ),
    code_block_marker: (_) => "```",
    code: (_) => repeat1(seq(/[^\n]*/, "\n")),
    language: (_) => /[^\s]+/,

    // A paragraph contains inline content and is terminated by a blankline
    // (two newlines in a row).
    paragraph: ($) => seq(repeat1(seq($._inline, "\n")), "\n"),

    // The markup parser could separate block and inline parsing into separate steps,
    // but we'll do everything in one parser.
    _inline: ($) => repeat1(choice($.emphasis, $._text)),
    emphasis: ($) => prec.left(seq("_", $._inline, "_")),
    _text: (_) => /[^\n]/,
  },
});

它能识别带文本和强调的段落，也能识别出 div 和代码块。

我们可以创建一个内容如下的 example-file：

:::
A paragraph _with emphasis_ inside a div

:::

然后用 tree-sitter 命令行解析它：

$ tree-sitter parse example-file
(document [0, 0] - [5, 0]
  (div [0, 0] - [4, 0]
    (div_marker [0, 0] - [0, 3])
    (paragraph [1, 0] - [3, 0]
      (emphasis [1, 12] - [1, 27]))
    (div_marker [3, 0] - [3, 3])))

搞定！

3、缺失的功能

但我之前说过，事情没那么简单，我们的解析器还缺少一些功能。最主要的是：

: 的数量可以是任意的，从而允许 div 嵌套。
关闭一个 div 时，应该同时关闭其他已打开的块（在我们的场景里就是 div 和段落）。

本质上，我们需要能够解析这样的内容：

:::
Top-level div

::::
A paragraph inside a second div,
both closed when the top-level div is closedj
:::

这……很复杂。

当然，我们可以用一些取巧的办法来绕过不同数量的 :，比如枚举冒号的数量，像这样：

div: ($) => choice($._div3, $._div4, $._div5, $._div6, $._div7, $._div8),
_div3: ($) => seq(/:{3}/, $._inside_div, /:{3}/, "\n"),
_div4: ($) => seq(/:{4}/, $._inside_div, /:{4}/, "\n"),
_div5: ($) => seq(/:{5}/, $._inside_div, /:{5}/, "\n"),
_div6: ($) => seq(/:{6}/, $._inside_div, /:{6}/, "\n"),
_div7: ($) => seq(/:{7}/, $._inside_div, /:{7}/, "\n"),
_div8: ($) => seq(/:{8}/, $._inside_div, /:{8}/, "\n"),
_inside_div: ($) => prec.left("\n", repeat($._block)),

但这并不优雅，而且自动关闭包含的块要难得多（在我脑子里这几乎不可能，不过我也不是专家）。

有了外部扫描器，我们就可以做到这一点（以及更多）。

4、外部扫描器

Tree-sitter 解析器实际上是一个 C 程序。我们看到的语法是用 JavaScript 描述的，但它只是用来生成 C 解析器的描述。如果你是个受虐狂，可以在运行 tree-sitter generate 之后看看 src/parser.c。

外部扫描器其实就是插入到解析器中的一些自定义 C 代码，它允许我们覆盖解析器的优先级、跟踪上下文状态，或者做任何其他我们需要或想做的事情。

入门的话，官方文档写得相当不错。基本上你需要：

创建 src/scanner.c，并把它在 binding.gyp 的 bindings/rust/build.rs 中包含进来。
在 grammar.js 中设置 externals 记号，并在 scanner.c 中定义匹配的 C 枚举。
定义并实现五个 C 函数。

我们来看一下。

4.1 Div 标记符会提前结束已打开的段落

我们先从遇到 ::: 时提前结束段落开始。这个更简单，因为我们不需要保存任何状态就能解决。

在解析 $.paragraph 时，我们会让解析器在"以换行结束段落"和"以我们新的 $._close_paragraph 记号结束段落"之间做选择：

paragraph: ($) =>
  seq(repeat1(seq($._inline, "\n")), choice("\n", $._close_paragraph)),

$._close_paragraph 由外部扫描器处理，通过 externals 字段指定：

externals: ($) => [$._close_paragraph],

现在我们把注意力转向 src/scanner.c。 externals 中的记号会被分配递增的编号，从 0 开始…… 就像 C 中的枚举一样！

// We only have a single element right now, but keep in mind that the order
// must match the `externals` array in `grammar.js`.
typedef enum { CLOSE_PARAGRAPH } TokenType;

我们需要实现的五个函数是：

// You should replace `sdjot` with whatever project name you chose.
bool tree_sitter_sdjot_external_scanner_scan(void *payload, TSLexer *lexer,
                                             const bool *valid_symbols) {
  // All the scanning goes here.
  return false;
}

// If we need to allocate/deallocate state, we do it in these functions.
void *tree_sitter_sdjot_external_scanner_create() { return NULL; }
void tree_sitter_sdjot_external_scanner_destroy(void *payload) {}

// If we have state, we should load and save it in these functions.
unsigned tree_sitter_sdjot_external_scanner_serialize(void *payload,
                                                      char *buffer) {
  return 0;
}
void tree_sitter_sdjot_external_scanner_deserialize(void *payload, char *buffer,
                                                    unsigned length) {}

因为我们不会使用任何状态，所以只需要更新 scan 函数。

你要做的是检查 valid_symbols，看当前时刻可以返回哪些记号，如果找到任何一个就返回 true：

bool tree_sitter_sdjot_external_scanner_scan(void *payload, TSLexer *lexer,
                                             const bool *valid_symbols) {
  if (valid_symbols[CLOSE_PARAGRAPH] && parse_close_paragraph(lexer)) {
    return true;
  }
  return false;
}

为了决定是否提前结束段落，我们会向前查看是否有 :::，如果有，就不消费任何字符直接关闭段落。这可能不是最高效的方案，因为我们必须重新解析一遍 :::，但能完成任务就行。

匹配到的记号应该存储在 lexer->result_symbol 中：

static bool parse_close_paragraph(TSLexer *lexer) {
  // Mark the end before advancing so that the CLOSE_PARAGRAPH token doesn't
  // consume any characters.
  lexer->mark_end(lexer);

  uint8_t colons = consume_chars(lexer, ':');
  if (colons >= 3) {
    lexer->result_symbol = CLOSE_PARAGRAPH;
    return true;
  } else {
    return false;
  }
}

注意，产生的记号会把我们前进过程中扫描过的任何符号都标记为归该记号所有。所以 ::: 会被标记为 _close_paragraph（由于以下划线开头，在输出中会被忽略），而不是 div_marker。为了防止这一点，我们通过在前进词法器之前标记结束位置，把 _close_paragraph 变成零宽度的记号。

我们如何让词法器前进？调用 lexer->advance：

static uint8_t consume_chars(TSLexer *lexer, char c) {
  uint8_t count = 0;
  while (lexer->lookahead == c) {
    lexer->advance(lexer, false);
    ++count;
  }
  return count;
}

这几乎就是我们对词法器能做的全部操作了。我们一次只能处理一个字符，不能向后看，而向前看的唯一工具就是在正确的位置调用 mark_end。（我们也可以查询当前的列位置。）

至此，我们就有了一个可用的外部扫描器，div 标签现在可以结束段落了：

:::
A paragraph inside a div
:::

$ tree-sitter parse example-file
(document [0, 0] - [4, 0]
  (div [0, 0] - [3, 0]
    (div_marker [0, 0] - [0, 3])
    (paragraph [1, 0] - [2, 0])
    (div_marker [2, 0] - [2, 3])))

4.2 嵌套块

要自动关闭其他已打开的块，我们需要给解析器添加一些上下文，这意味着我们需要状态管理。

我们实现的这个小子集只关心关闭 div——否则这篇文章就太长太长了——但我会尽量用一种通用的方式来实现，更贴近真实世界的解析器。

我们的策略是这样的：

div 可以有不同数量的 :，且必须匹配。因此我们会在外部扫描器中解析冒号，并把它们存到一个栈上。
当遇到 div 标记符时，我们需要判断它应该开启一个新的 div，还是关闭现有的一个。我们会查看已打开块的栈，看看能否找到匹配项。
如果我们需要关闭嵌套的 div，也就是想关闭栈中更靠下的某个 div，就得先关闭嵌套的 div。因此我们会引入一个 block_close 标记符来结束 div，并把结束 div 的标记符设为可选的。

首先，我们让语法把开始和结束记号都交给外部扫描器管理。我们用 _block_close 标记符来结束 div，并把结束标记符设为可选。（你可能也可以用两者之间的 choice()，但我在实现时觉得这样更合理。）

div: ($) =>
  prec.left(
    seq(
      // A rule starting with "_" will be hidden in the output,
      // and we can use "alias" to rename rules.
      alias($._div_marker_begin, $.div_marker),
      "\n",
      repeat($._block),
      $._block_close,
      optional(alias($._div_marker_end, $.div_marker))
    )
  ),

externals: ($) => [
  $._close_paragraph,
  $._block_close,
  $._div_marker_begin,
  $._div_marker_end,

  // This is used in the scanner internally,
  // but shouldn't be used by the grammar.
  $._ignored,
],

记得同时更新扫描器中的外部记号列表（顺序很重要）：

typedef enum {
  CLOSE_PARAGRAPH,
  BLOCK_CLOSE,
  DIV_MARKER_BEGIN,
  DIV_MARKER_END,
  IGNORED
} TokenType;

然后是我们的块栈。

我用一个 Block 类型来跟踪块的类型和冒号数量：

// In a real implementation we'll have more block types.
typedef enum { DIV } BlockType;

typedef struct {
  BlockType type;
  uint8_t level;
} Block;

我知道 level 不是最好的名字，但我没能为"冒号数量、缩进级别"之类的东西找到一个很好的通用名字。如果使用和类型（sum types），你可以用更清晰的方式建模，像这样：

enum Block {
    Div { colons: u32 },
    Footnote { indent: u32 },
    // etc
}

事实上，我要说，一个糟糕的程序员和一个优秀的程序员的区别，在于他是更看重自己的代码还是更看重自己的数据结构。糟糕的程序员担心代码。优秀的程序员担心数据结构以及它们之间的关系。 Linus Torvalds

不过扯远了，我就像个糟糕的程序员那样用 level 吧。

编写 C 程序的另一个"乐趣"在于，你得重新实现诸如可增长的栈这样的标准数据结构。它并不难，但很烦人，而且容易出错。

幸运的是，在我写这篇博客文章的时候，tree-sitter 0.22.1 发布了，它带了一个数组实现。所以现在我不必展示我那蹩脚的栈实现了，我们可以直接用他们提供的数组来做我们的栈。

我们把 Block* 的 Array 塞进一个 Scanner 结构体里，因为后面我们还需要跟踪更多数据：

#include "tree_sitter/array.h"

typedef struct {
  Array(Block *) * open_blocks;
} Scanner;

在 tree-sitter 中管理状态时，你需要在前面定义的 tree_sitter_ 函数中做一些数据管理工作。

内存分配在 _create 和 _destroy 函数中管理。 0.22.1 中新增的建议是使用 ts_ 函数进行分配，以允许使用者覆盖默认的分配器：

#include "tree_sitter/alloc.h"

void *tree_sitter_sdjot_external_scanner_create() {
  Scanner *s = (Scanner *)ts_malloc(sizeof(Scanner));

  // This is how you create an empty array
  s->open_blocks = ts_malloc(sizeof(Array(Block *)));
  array_init(s->open_blocks);

  return s;
}

void tree_sitter_sdjot_external_scanner_destroy(void *payload) {
  Scanner *s = (Scanner *)payload;

  // I haven't shown the allocation of the blocks yet,
  // but keep in mind that `array_delete` does not deallocate any memory
  // you store in the array itself.
  for (size_t i = 0; i < s->open_blocks->size; ++i) {
    // I use `array_get` even though you can index the contents directly.
    ts_free(array_get(s->open_blocks, i));
  }

  // The array is a growable one, `array_delete` ensures that the
  // memory is deleted.
  array_delete(s->open_blocks);

  ts_free(s);
}

我在一个 push_block 辅助函数中分配块：

static void push_block(Scanner *s, BlockType type, uint8_t level) {
  Block *b = ts_malloc(sizeof(Block));
  b->type = type;
  b->level = level;

  // Grows the stack automatically.
  array_push(s->open_blocks, b);
}

你还需要定义 serialize 函数。它们负责保存和恢复受管理的状态，以便 tree-sitter 能够回溯。

unsigned tree_sitter_sdjot_external_scanner_serialize(void *payload,
                                                      char *buffer) {
  Scanner *s = (Scanner *)payload;
  unsigned size = 0;
  for (size_t i = 0; i < s->open_blocks->size; ++i) {
    Block *b = *array_get(s->open_blocks, i);
    buffer[size++] = (char)b->type;
    buffer[size++] = (char)b->level;
  }
  return size;
}

void tree_sitter_sdjot_external_scanner_deserialize(void *payload, char *buffer,
                                                    unsigned length) {
  Scanner *s = (Scanner *)payload;
  array_init(s->open_blocks);
  size_t size = 0;
  while (size < length) {
    BlockType type = (BlockType)buffer[size++];
    uint8_t level = (uint8_t)buffer[size++];
    push_block(s, type, level);
  }
}

这样（初步的）状态管理就搞定了！

C 语言很吓人。试试 valgrind。

4.3 Div 标记符

当然，我们还没用到我们的状态。让我们来用用吧。

首先，在我们的 scan 函数里加上 parse_div 入口：

bool tree_sitter_sdjot_external_scanner_scan(void *payload, TSLexer *lexer,
                                             const bool *valid_symbols) {
  Scanner *s = (Scanner *)payload;

  // Paragraph needs to be closed before we try to close divs.
  if (valid_symbols[CLOSE_PARAGRAPH] && parse_close_paragraph(lexer)) {
    return true;
  }

  // Check `valid_symbols` inside `parse_div` because of multiple valid symbols.
  if (parse_div(s, lexer, valid_symbols)) {
    return true;
  }

  return false;
}

因为让词法器前进是很基础的操作，而且我们不能"回退一个字符"，所以只有在确实需要时才让它前进，这一点很重要。因此，在继续之前，我们总是需要检查 valid_symbols：

static bool parse_div(Scanner *s, TSLexer *lexer, const bool *valid_symbols) {
  if (!valid_symbols[DIV_MARKER_BEGIN] && !valid_symbols[DIV_MARKER_END]) {
    return false;
  }

  // ...
}

接下来，我们需要消费当前位置的所有冒号，并且只有在看到至少三个时才继续：

static uint8_t consume_chars(TSLexer *lexer, char c) {
  uint8_t count = 0;
  while (lexer->lookahead == c) {
    lexer->advance(lexer, false);
    ++count;
  }
  return count;
}

static bool parse_div(Scanner *s, TSLexer *lexer, const bool *valid_symbols) {
  // ...

  uint8_t colons = consume_chars(lexer, ':');
  if (colons < 3) {
    return false;
  }

  // ...
}

开启一个新的 div 很简单；我们压入块并记录冒号数量：

push_block(s, DIV, colons);
lexer->result_symbol = DIV_MARKER_BEGIN;
return true;

但要决定是开启还是关闭一个 div，我们需要一种搜索栈的方法。下面的函数做到了这一点，同时还会返回我们在栈中找到该 div 的深度（马上就会用到）：

// How many blocks from the top of the stack can we find a matching block?
// If it's directly on the top, returns 1.
// If it cannot be found, returns 0.
static size_t number_of_blocks_from_top(Scanner *s, BlockType type,
                                        uint8_t level) {
  for (int i = s->open_blocks->size - 1; i >= 0; --i) {
    Block *b = *array_get(s->open_blocks, i);
    if (b->type == type && b->level == level) {
      return s->open_blocks->size - i;
    }
  }
  return 0;
}

static bool parse_div(Scanner *s, TSLexer *lexer, const bool *valid_symbols) {
  // ...

  size_t from_top = number_of_blocks_from_top(s, DIV, colons);

  // We could check if either DIV_MARKER_BEGIN or DIV_MARKER_END are valid here,
  // but as the grammar is set up they're both always valid at the same time.
  if (from_top > 0) {
    // Close the current div, and all blocks above.
  } else {
    // No matching div to close, let's open one.
    lexer->mark_end(lexer);
    push_block(s, DIV, colons);
    lexer->result_symbol = DIV_MARKER_BEGIN;
    return true;
  }
}

但我们有一个问题：当我们想要关闭 div 时，我们需要能够输出多个记号。

例如，对于这样的输入：

:::
:::::
:::::::
text
:::

当我们看到结尾的 ::: 标记符时，栈里会有 3 个 div：

7 (top)
5
3 (the one we want to close)

在上面的代码里，from_top 会是 3，而我们需要输出 4 个记号：3 个 BLOCK_CLOSE（每个 div 一个）和 1 个 DIV_MARKER_END（对应最后的 :::）。但扫描器一次只能输出一个记号。

我解决这个问题的方法是给 Scanner 引入更多状态。具体来说，我引入了一个 blocks_to_close 变量来输出 BLOCK_CLOSE，以及一些变量来输出（并消费）DIV_MARKER_END。

typedef struct {
  Array(Block *) * open_blocks;

  // How many BLOCK_CLOSE we should output right now?
  uint8_t blocks_to_close;

  // Delayed output of a token.
  TokenType delayed_token;
  // Allows us to consume the width of a delayed token.
  uint8_t delayed_token_width;
} Scanner;

我们要记得同时更新 create 和 serialize 函数。

Serialize：

buffer[size++] = (char)s->blocks_to_close;
buffer[size++] = (char)s->delayed_token;
buffer[size++] = (char)s->delayed_token_width;

Deserialize：

s->blocks_to_close = (uint8_t)buffer[size++];
s->delayed_token = (TokenType)buffer[size++];
s->delayed_token_width = (uint8_t)buffer[size++];

我们用 IGNORED 作为"未使用"的记号，所以创建扫描器时需要把它重置：

s->blocks_to_close = 0;
s->delayed_token = IGNORED;

现在，在扫描其他东西之前，我们应该先检查 blocks_to_close，然后是 delayed_token：

bool tree_sitter_sdjot_external_scanner_scan(void *payload, TSLexer *lexer,
                                             const bool *valid_symbols) {
  Scanner *s = (Scanner *)payload;

  if (valid_symbols[BLOCK_CLOSE] && handle_blocks_to_close(s, lexer)) {
    return true;
  }

  if (output_delayed_token(s, lexer, valid_symbols)) {
    return true;
  }

  // Scan the other stuff
}

当我们看到 blocks_to_close > 0 时，应该输出一个 BLOCK_CLOSE 并移除栈顶的块（为了保险起见还做了一些健全性检查）：

static void remove_block(Scanner *s) {
  if (s->open_blocks->size > 0) {
    ts_free(array_pop(s->open_blocks));
    if (s->blocks_to_close > 0) {
      --s->blocks_to_close;
    }
  }
}

static bool handle_blocks_to_close(Scanner *s, TSLexer *lexer) {
  if (s->open_blocks->size == 0) {
    return false;
  }

  // If we reach eof with open blocks, we should close them all.
  if (lexer->eof(lexer) || s->blocks_to_close > 0) {
    lexer->result_symbol = BLOCK_CLOSE;
    remove_block(s);
    return true;
  }
  return false;
}

这样一来，我们就可以输出多个 BLOCK_CLOSE 了，接下来处理延迟记号：

static bool output_delayed_token(Scanner *s, TSLexer *lexer,
                          const bool *valid_symbols) {
  if (s->delayed_token == IGNORED || !valid_symbols[s->delayed_token]) {
    return false;
  }

  lexer->result_symbol = s->delayed_token;
  s->delayed_token = IGNORED;
  // With `delayed_token_width` we can consume the ending `:::`, for example.
  while (s->delayed_token_width--) {
    lexer->advance(lexer, false);
  }
  lexer->mark_end(lexer);
  return true;
}

另一种设计方式是维护一个延迟记号的栈，然后直接弹出。它当然更强大，只是我在尝试时碰巧选了现在这种方式，因为它更明确，也更容易看清楚发生了什么。

不管怎样，我们现在可以实现 div 的结束处理了。在 parse_div 中：

size_t from_top = number_of_blocks_from_top(s, DIV, colons);

if (from_top > 0) {
  // Found a div we should close.
  close_blocks_with_final_token(s, lexer, from_top, DIV_MARKER_END, colons);
  return true;
} else {
  lexer->mark_end(lexer);
  push_block(s, DIV, colons);
  lexer->result_symbol = DIV_MARKER_BEGIN;
  return true;
}

close_blocks_with_final_token 是一个通用的辅助函数，用来设置要关闭的块数量和最终记号：

static void close_blocks_with_final_token(Scanner *s, TSLexer *lexer,
                                          size_t count, TokenType final,
                                          uint8_t final_token_width) {
  remove_block(s);
  s->blocks_to_close = s->blocks_to_close + count - 1;
  lexer->result_symbol = BLOCK_CLOSE;
  s->delayed_token = final;
  s->delayed_token_width = final_token_width;
}

现在，我们终于可以尝试关闭 div 了：

:::::
:::
:::::::
Divception
:::

$ tree-sitter parse example-file
(document [0, 0] - [6, 0]
  (div [0, 0] - [6, 0]
    (div_marker [0, 0] - [0, 5])
    (div [1, 0] - [4, 3]
      (div_marker [1, 0] - [1, 3])
      (div [2, 0] - [4, 0]
        (div_marker [2, 0] - [2, 7])
        (paragraph [3, 0] - [4, 0]))
      (div_marker [4, 0] - [4, 3]))))

可以看到它解析时没有报错，最后一个标记符正确地关闭了第二个 div，并且最后的标记符捕获了结尾的 :::。

虽然在这篇文章里我是直接跳到可用实现的，但我当初第一次做的时候当然不是这样。我发现 -d 参数很有用，可以查看每一步消费了哪些字符、输出了哪个记号。

下面是输出的一部分（在扫描结尾 ::: 时），我加了一些注释来指出几个有意思的地方：

$ tree-sitter parse example-file -d
...
process version:0, version_count:1, state:34, row:4, col:0
lex_external state:4, row:4, column:0
  consume character:':'                         // Scan `:::`
  consume character:':'
  consume character:':'
lexed_lookahead sym:_close_paragraph, size:0    // Output _close_paragraph
reduce sym:paragraph_repeat1, child_count:2
shift state:17
process version:0, version_count:1, state:17, row:4, col:0
lex_external state:3, row:4, column:0           // Still on first `:`
  consume character:':'                         // Scan `:::` again
  consume character:':'
  consume character:':'
lexed_lookahead sym:_block_close, size:0        // Close div with _block_close
reduce sym:paragraph, child_count:2
shift state:12
process version:0, version_count:1, state:12, row:4, col:0
lex_external state:5, row:4, column:0           // Still on first `:`
lexed_lookahead sym:_block_close, size:0        // Close second div with _block_close
reduce sym:div, child_count:4
shift state:12
process version:0, version_count:1, state:12, row:4, col:0
lex_external state:5, row:4, column:0           // Still on first `:`
  consume character:':'                         // Consume `:::`
  consume character:':'
  consume character:':'
lexed_lookahead sym:div_marker, size:3          // div_marker is size 3, marks `:::`
shift state:23

虽然输出看起来让人困惑，但当你知道了该看什么之后，它非常有用。我发现，一个"逐字符查看"的审慎过程能帮我解决到目前为止遇到的各种问题。

5、处理冲突

我们的语法运行得相当不错，但还是有一些你可能想修复的问题。其中一个问题（我花了远比愿意承认的时间才弄清楚）是：当标记规则不匹配时，添加一个回退到文本的规则。

对我们的语法来说，一个简单的例子是段落中的单个下划线：

a_b

我原以为这会解析成一个带文本的段落，但结果却是一个错误：

$ tree-sitter parse example-file
(document [0, 0] - [2, 0]
  (ERROR [0, 0] - [0, 3]))

这很奇怪，因为 Tree-sitter 的主要卖点之一就是 GLR 算法，它应该会探索不同的解释，找到能成功的那一个。但出于某种原因，它没有为我们触发。

让我们来看一看。下面是语法中相关的几行：

_inline: ($) => repeat1(choice($.emphasis, $._text)),
emphasis: ($) => prec.left(seq("_", $._inline, "_")),
_text: (_) => /[^\n]/,

当我们尝试匹配一个 _ 时，语法既可以匹配 emphasis 也可以匹配 _text，因为 _ 同时匹配 "_" 和 /[^\n]/。问题似乎是 Tree-sitter 不认为这是一个冲突。

如果我们改为添加一个 _ 字符串作为回退，Tree-sitter 就会把它当作冲突来处理：

_inline: ($) => repeat1(choice($.emphasis, $._text, $._fallback)),
emphasis: ($) => prec.left(seq("_", $._inline, "_")),
// prec.dynamic() is used during conflict resolution to choose which
// branch to choose if multiple succeed.
_fallback: (_) => prec.dynamic(-100, "_"),
_text: (_) => /[^\n]/,

当我们运行 tree-sitter generate 时，就会看到这个冲突：

$ tree-sitter generate
Unresolved conflict for symbol sequence:

  '_'  •  '_'  …

Possible interpretations:

  1:  (_fallback  '_')  •  '_'  …
  2:  (emphasis  '_'  •  _inline  '_')  (precedence: 0, associativity: Left)

Possible resolutions:

  1:  Specify a higher precedence in `emphasis` than in the other rules.
  2:  Specify a higher precedence in `_fallback` than in the other rules.
  3:  Specify a left or right associativity in `_fallback`
  4:  Add a conflict for these rules: `emphasis`, `_fallback`

我们要做的是用 conflicts 字段把它们标记为语法中"预期存在"的冲突：

conflicts: ($) => [[$.emphasis, $._fallback]],

现在，我们就可以在不出错的情况下解析只包含单个 _ 的段落了。

所以，看起来 Tree-Sitter 不能识别字符串和正则之间的冲突。另一个坑是：你似乎不能用外部扫描器返回的记号来触发 GLR 算法，因为外部扫描器会覆盖 Tree-sitter 的词法分析行为。

6、一些测试

用 tree-sitter parse example-file（无论是否带 -d 或 -D 标志，没试过的话可以试试）做实验性测试没问题，但我们真的应该把各种测试用例写成正式的单元测试。 Tree-sitter 为此内置了一个测试框架。

让我们把第一个测试用例加到 test/corpus/syntax.txt：

===============================================================================
Parsing goal
===============================================================================
This is a
multiline _paragraph_

:::
This is a paragraph inside a div
:::

```gleam
let x = 2;
```

-------------------------------------------------------------------------------

(document
  (paragraph (emphasis))
  (div
    (div_marker)
    (paragraph)
    (div_marker))
  (code_block
    (code_block_marker)
    (language)
    (code)
    (code_block_marker)))

然后运行它：

$ tree-sitter test
  syntax:
    ✓ Parsing goal

耶！

我们应该在这里加（很多）更多的测试，但在这篇已经太长的博客文章里，我就不把测试全写出来了。

7、让 tree-sitter 做点有用的事

我和其他书呆子一样喜欢理论上的探讨，但我开始研究 Tree-sitter，是因为我想用语法做点什么，而不是整天摆弄它。让我们用一些实际用途来结束这篇文章吧。

7.1 语法高亮

语法高亮是通过 highlights.scm 文件中的查询来实现的。通常它被放在与语法同一个仓库的 src 目录下，但这并不是必须的。

下面是一个 src/highlights.scm 示例文件，用来高亮我们标记的不同元素：

(div_marker) @punctuation.delimiter
(code_block_marker) @punctuation.delimiter

(emphasis "_" @punctuation.delimiter) @markup.italic
(language) @tag.attribute

(code_block) @markup.raw
(paragraph) @markup

选什么颜色有点随意，我觉得这些效果还行。

关于查询和高亮如何工作的更多细节，请看文档。

7.2 语言注入

开始写语法时，我的一个大问题是：如何在同一个文档中混用多个解析器，比如用指定的语言来高亮代码块的内容：

```gleam
let x = 2;
```

事实证明，这相当简单。

使用最初的语法，代码块会被解析成：

(code_block
  (code_block_marker)
  (language)
  (code)
  (code_block_marker)))

我们将在 src/injections.scm 中使用这个结构，指定用 (language) 中指定的语法来解析 (code)：

(code_block
  (language) @injection.language
  (code) @injection.content)

当我们把语法嵌入到带高亮支持的程序中时，它会把代码块内的文本委托给注入的语言来处理。

7.3 在 Neovim 中使用我们的语法

我通常使用 nvim-treesitter 提供的 :TSInstall 在 Neovim 中安装 Tree-sitter 语法。但你也可以安装本地的 Tree-sitter 语法：

local parser_config = require("nvim-treesitter.parsers").get_parser_configs()
parser_config.sdjot = {
    install_info = {
        -- Change this url to your grammar
        url = "~/code/tree-sitter-sdjot",
        -- If you use an external scanner it needs to be included here
        files = { "src/parser.c", "src/scanner.c" },
        generate_reqires_npm = false,
        requires_generate_from_grammar = false,
    },
    -- The filetype you want it registered as
    filetype = "sdjot",
}

只需要确保语法的 package.json 中有 "tree-sitter" 部分：

"tree-sitter": [
  {
    "scope": "source.sdjot",
    "file-types": [
      "sdj"
    ],
    "injection-regex": "sdjot",
    "highlights": [
      "queries/highlights.scm"
    ]
  }
],

有了这些，改动之后你就可以执行 :TSInstall sjdot 和 :TSUpdate sdjot 了。

不过 :TSInstall 不会自动安装查询文件。我的做法是把 queries 目录符号链接到 Neovim 的配置目录：

ln -s ~/code/tree-sitter-sdjot/queries ~/.config/nvim/queries/sdjot

:TSPlaygroundToggle 对调试语法非常有用，而 :Inspect 会显示光标下的高亮组。如果你想折腾你的主题，最好看一下 :help treesitter-highlight-groups，因为要让颜色显示出来，主题需要支持我们用到的这些高亮组。

如果你想高亮代码块的内容，还需要安装注入语言的 Tree-sitter 语法。

7.4 用文本对象跳转和选择

我提到过 nvim-treesitter-textobjects 是"Tree-sitter 不只是语法高亮"的一个好例子。

要使用我们的语法，可以在 src/textobjects.scm 中添加一些捕获组。例如，我们可以把代码块注册为"函数"：

(code_block (code) @function.inner) @function.outer

这些对象是任意的，但 @function 是标准对象之一，所以我想这样设置是有道理的。

准备好符号链接之后，你只需要用 nvim-treesitter-textobjects 注册键位映射就可以使用了。我的配置是：用 [f 和 ]f 在 @function.outer 之间跳转，用 af 和 if 做选择。

这意味着，有了上面的文本对象定义，我就可以用 ]f 跳到下一个代码块，然后用 cif 删除里面的所有代码，进入插入模式，准备用新代码替换它。

虽然这个例子有点随意，但这种通用功能对编程语言来说极其有用。对于像 Djot 这样的标记语言，在标题之间跳转可能是更相关的用法。

7.5 用 Rust 嵌入语法

Tree-sitter 的卖点之一是它应该能嵌入到任何应用程序中。比如这个博客！

我一直想在博客中加入 Tree-sitter 驱动的语法高亮，现在总算有理由这么做了。

这个博客是一个用 Rust 编写的静态站点生成器，tree-sitter-highlight 看起来是个值得一试的库。让我们把它加到 Cargo.toml 中：

[dependencies]
tree-sitter-highlight = "^0.20.0"
tree-sitter-sdjot = { git = "https://codeberg.org/treeman/tree-sitter-sdjot.git" }

我用了稍微旧一点的版本，因为有些我想要的语法依赖旧版本，而且麻烦的是，它们都需要使用匹配的版本。哎。

根据文档，我们首先需要设置一个 HighlightConfiguration。我用 lazy_static! 创建了一个全局配置映射，供博客的任何并行渲染使用。这不是我写过的最漂亮的代码，但它能完成任务：

// All highlights needs to be listed explicitly.
static HIGHLIGHT_NAMES: &[&str] = &[
    // I have +100 entries here, this is for sdjot.
   "markup",
   "markup.italic",
   "markup.raw",
   "punctuation.delimiter",
   "tag.attribute",
];

lazy_static! {
    static ref CONFIGS: HashMap<String, HighlightConfiguration> = init_configurations();
}

fn init_configurations() -> HashMap<String, HighlightConfiguration> {
    [
        // I have more languages here
        (
            "sdjot",
            HighlightConfiguration::new(
                tree_sitter_sdjot::language(),
                tree_sitter_sdjot::HIGHLIGHTS_QUERY,
                tree_sitter_sdjot::INJECTIONS_QUERY,
                "",
            )
            .unwrap(),
        ),
    ]
    .into_iter()
    .map(|(name, mut config)| {
        config.configure(&HIGHLIGHT_NAMES);
        (name.to_string(), config)
    })
    .collect()
}

注意，我们感兴趣的所有高亮名称都必须显式列出。这是个很大的麻烦，特别是如果你要包含很多更大的语法的话。

这些名称可以用 ripgrep 之类的方式过滤出来：

rg "@[\w.]+" -INo --trim highlights.scm | sort | uniq

我已经通过 syntect 实现了语法高亮，所以我把各个高亮器包装成自己的类型：

enum HighlighterType<'a> {
    Syntect(SyntectHighlighter<'a>),
    Treesitter(TreesitterHighlighter<'a>),
}

pub struct TreesitterHighlighter<'a> {
    config: &'a HighlightConfiguration,
}

impl<'a> TreesitterHighlighter<'a> {
    pub fn find(lang_id: &str) -> Option<Self> {
        CONFIGS.get(lang_id).map(|config| Self { config })
    }
}

当然，有趣的部分是 highlight 方法，它接收一段代码字符串并对其应用语法高亮：

impl<'a> TreesitterHighlighter<'a> {
    pub fn highlight(&self, code: &str) -> Result<String> {
        let mut highlighter = Highlighter::new();

        let highlights = highlighter.highlight(self.config, code.as_bytes(), None, |lang| {
            // This callback handles language injection
            // and should return a `HighlightConfiguration`.
            let res = CONFIGS.get(lang);
            if !res.is_some() {
                warn!("Couldn't find treesitter grammar for `{lang}` to inject");
            }
            res
        })?;

        let mut renderer = HtmlRenderer::new();
        renderer.render(highlights, code.as_bytes(), &|attr| {
            // This should return a `&'a [u8]` with the same lifetime as `code`.
        })?;
        let res = renderer.lines().join("");
        Ok(res)
    }
}

我想指出 HtmlRenderer 中的 API，我们在这里遇到了一个非常烦人的问题：回调应该返回什么，又该怎么返回？

回调要做的是把返回值注入到 span 元素里，像这样：

<span CALLBACK_RESULT >highlight</span>

所以我们想返回类似 "class=\"markup italic\"" 这样的东西，而 attr 只是 HIGHLIGHT_NAMES 的一个 usize 索引：

renderer.render(highlights, code.as_bytes(), &|attr| {
    format!(r#"class="{}""#, HIGHLIGHT_NAMES[attr.0].replace(".", " ")).as_bytes()
})?;

因为我们要返回的字节切片指向一个在回调内部创建的字符串，所以 Rust 编译器当然会生气：

error[E0515]: cannot return value referencing temporary value
  --> src/markup/syntax_highlight/treesitter_highlighter.rs:33:13
   |
33 |             format!(r#"class="{}""#, HIGHLIGHT_NAMES[attr.0].replace(".", " ")).as_bytes()
   |             -------------------------------------------------------------------^^^^^^^^^^^
   |             |
   |             returns a value referencing data owned by the current function
   |             temporary value created here

如何在回调内部动态地创建一个字符串……并且让它比回调本身活得还久？

我告诉你，可不容易。

如果回调能返回一个 Cow 或其他什么就好了。我想知道 API 的设计者期望它怎么用？把属性包装成 class 肯定不是什么独一无二的需求吧？

算了。一种解决方法是把生成的字符串存储在一个比回调活得更久的容器里，然后引用它（是的，这是一个 Fn 回调，但总有绕过去的黑客办法）。或者，你也可以自己写一个 HtmlRenderer。

或者你可以预先生成这些类并引用它们：

lazy_static! {
    static ref CLASSES: Vec<String> = HIGHLIGHT_NAMES
        .iter()
        .map(|name| format!(r#"class="{}""#, name.replace(".", " ")))
        .collect();
}

renderer.render(highlights, code.as_bytes(), &|attr| {
    CLASSES[attr.0].as_bytes()
})?;

这应该是最快的方案，也是我目前使用的方案…… 但速度在这里并不是瓶颈，我更希望直接用 format! 返回一个 String 完事。

至此，我已经把基于 Tree-sitter 的语法高亮集成到了我的博客里！

```
With great powers comes great responsibility
```

我可以开始把各种语言从 Syntect 迁移到 Tree-sitter…… 但我不打算这么做。

有几个问题：

所有语法都需要兼容版本的 tree-sitter。语法加得越多，升级路径就越痛苦。
Syntect 对某些语言（比如 Rust 和 C）的高亮效果更好。 Neovim 有自己实现的高亮器，并且对某些语法做了调整，得到的高亮效果比我开箱即用得到的漂亮得多。把这些代码集成到我的站点生成器里大概是可以做到的，但这不是我现在想跳进去的兔子洞。
高亮器库感觉还不太成熟。一个较新的版本破坏了我从某些语法中得到的高亮组，而且我没看到任何办法可以为注入的语言给 span 添加语言特定的类。

因为这些问题，我会逐案评估使用哪个高亮器，默认选择 Syntect。

8、复杂性隐藏在边界情况之中

如果你读到了文章结尾，恭喜你。你做到了！

我不敢自称是语法或 Tree-sitter 的专家，而且我确信语法本身还有很多可以改进的地方。但我希望这篇文章能成为你开始编写自己的 Tree-sitter 语法时的一个不错的起点。

关于我如何进一步把语法开发到支持完整 Djot 规范的过程，请看 tree-sitter-djot 仓库（但请记住，我不是专家）。

在你离开之前，还有一句忠告。为简单的规则编写语法相当容易，但在现实世界中，事情很快就会变得一团糟。如果你需要在外部扫描器中同时处理多个相互冲突的规则，情况尤其如此——保持一个清晰的结构是很有挑战性的。

（即使在我们这个简单的语法里也有 bug，但我不想费心去修它们。）

原文链接: Let's create a Tree-sitter grammar

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