emacs 的 treesit — 用 tree-sitter 写 parser

当前（2024-02-03），tree-sitter 在 github 上已有 14.9k 个 star，1.2k 个 fork，4661 个 commit 和接近 1k 的 pr。目前 tree-sitter 的最新版本是 0.20.9，似乎离 1.0 还有些距离。

我并没有深入参与到 tree-sitter 开发的经历，这里只能通过观察 issue 简单了解一下它的发展状态。当前被置顶的两个 issue 分别是 Tree-sitter 1.0 Checklist 和 Tree-Sitter Roadmap，前者于 2021 年的 2 月 21 日 Open，后者就在昨天（2024-02-02）。在 1.0 Checklist 中，没有被打勾的目标似乎不是那么紧要的任务，比如支持 ES modules、从仓库中分离源代码与生成产物、改进文档等等；在 Tree-Sitter Roadmap 这个 issue 中，发起者 amaanq 给出了一些要在 0.20.10 和 0.21.0 达到的目标。也许我们已经可以认为 tree-sitter 在核心功能上已经成熟了，但谁知道呢。

（[2024-02-14]，现在 Tree-Sitter Roadmap 这个 issue 已被关闭，可以参考 milestones 了解 tree-sitter 进展）

至于 tree-sitter 的应用，根据文档的说法，tree-sitter-highlight 被 github 用于一些语言的高亮。在 neovim 中直接集成了对 tree-sitter 的支持，你可以在 nvim 源代码中找到 tree-sitter 的 binding。nvim 默认支持 bash, c, lua 等语言，用户可以使用 nvim-treesitter 插件方便地引入其他语言的 tree-sitter 支持，读者可以在该 repo 的 README 页面或 queries 目录中找到它当前支持的 parser 列表。我没有使用过 nvim 及其 tree-sitter 支持，这里有篇不错的文章可以看看。

就像本文开头提到的那样，emacs 于 29.1 引入了 tree-sitter 支持，当前 emacs 中已经有了一些支持 tree-sitter 的 major-mode。从我对 nvim 的粗浅了解来看它直接利用了 highlights.scm 来进行高亮，而 emacs 的 treesit 并未提供这样的支持（当然有其他的包，比如 treesit-langs。tree-sitter 也有 Discussions 在讨论相关的问题）。读者可以通过阅读 elisp manual 的 Parsing Program Source 一章了解如何在 emacs 中使用 tree-sitter，我会在之后的文章中进行介绍。在是否使用 hightlights.scm 作为各编辑器的公用标准这一讨论中，我比较认同下面的观点：

Highlighting query files are not a very large amount of work to make and might take a day or two at most for a very complicated grammar. If new clients want to reuse existing work they can choose to support the same capture names and predicates as for example neovim.

ahelwer on Jul 13, 2023

既然 vim（neovim）和 emacs 都提到了，那就顺带提一提 vscode 吧。通过搜索 vscode + tree-sitter ，你能找到一个叫做 vscode-tree-sitter 的插件，只不过在 README 的第一行就有这样的陈述： With the improving support for custom syntax coloring through language server, this extension is no longer needed ，参考这个讨论，类似的插件还有 syntax-highlighter 和 vscode-parse-tree。在 vscode 的 repo 中也有 issue 讨论了 tree-sitter 集成的问题，但到了今天也没有什么进展。vscode 本身提供了很多机制实现高亮等功能，读者可以阅读「你不知道的 VSCode 代码高亮原理」来简单了解。

为什么我们会突然想写个 tree-sitter parser？可能是突然想练练手学习一下编译原理，可能是闲得无聊打法一下时间，或者是为编辑器添加更准确的语法高亮和缩进。我不太可能知道读者们的动机和想法，只能提供一种编写 parser 的流程，希望能够有所帮助。

要编写一门语言的 parser，首先需要知道的是语言的书面语法，或者说语言标准。毕竟我们不是语言的设计者，仅凭编程经验来手搓容易漏掉一些犄角旮旯的细节，更何况编写的可能是从来没用过语言的 parser。举例来说的话，JavaScript（或者说 ECMAScript）的语言标准可以在 ECMA-262 标准中找到，C++ 则可以参考 EBNF Syntax: C++，Rust 可以参考 wg-grammar，zig 可以参考 zig-spec，等等。多数的语言标准应该会提供类似 BNF 形状的语言标准，读者可以简单了解一下什么是 BNF：Backus-Naur form。

在熟悉语言标准后，读者就可以开始 parser 的编写过程了。tree-sitter 将 creating parser 这一过程描述为 Developing Tree-sitter grammars can have a difficult learning curve, but once you get the hang of it, it can be fun and even zen-like. 是不是禅意的我不好说，只能说是唯手熟尔，多写一点就有经验了。一般编译型语言的编程流程是编写 -> 编译 -> 测试 -> 崩溃 -> 编写的一个循环，tree-sitter 也差不多是编写 -> 生成 -> 测试 -> 报错 -> 编写的过程。

tree-sitter 为我们提供了专门的测试子命令，我们可以在编写新规则时编写它的测试样例，然后在生成后直接测试，这也是文档推荐的做法： For each rule that you add to the grammar, you should first create a test that describes how the syntax trees should look when parsing that rule.

当编写的 parser 完全覆盖了目标语言的语法，且编写的测试全部通过时，我们可以认为我们完成了 parser 的开发工作。接下来我们可以将生成的 C 代码编译得到可用的动态库，然后通过 libtree-sitter 在自己的程序中加载并使用这个 parser。在使用过程中我们可能会碰到 parser 的 bug，从而导致不得不修改 parser 源代码来修复错误，我就碰到过 parser 瞬间吃满内存的 bug，但到现在我也不知道具体是什么原因（笑）。

需要说明的是，当前网上关于 tree-sitter 的资料少的可怜，如果读者在编写 parser 过程中遇到了问题且无法通过搜索引擎解决，那最好的方法可能是寻找其他语言中的类似结构，并参考其现成 tree-sitter parser 的实现。tree-sitter 官网列出了一堆已有的 parser 实现，其中的官方实现很有参考价值。

在 tree-sitter 文档的 Creating Parsers 一章中提到的依赖项是 node.js 和 C/C++ 编译器。在 Windows 上我们可以前往 node 官网下载 node.js，并通过安装 Visual Studio 顺带安装 MSVC 编译器（当然也可以仅安装生成工具）。随后，我们可以通过 npm 或 cargo 安装 tree-sitter-cli，这个工具的主要功能是根据 grammar.js 生成可被编译为动态链接库的 C 代码：

# rust cargo
cargo install tree-sitter-cli
# node npm
npm install tree-sitter-cli
# or get from prebuild binary
https://github.com/tree-sitter/tree-sitter/releases/tag/v0.20.9

以上安装方法来自 tree-sitter-cli 的 README 页面，如果我们想要在 node 中使用 parser 的话最好参考官网中文档的做法（当然本文不会涉及到 parser 的使用）：

# This will prompt you for input
npm init
# This installs a small module that lets your parser be used from Node
npm install --save nan
# This installs the Tree-sitter CLI itself
npm install --save-dev tree-sitter-cli
# 为啥使用 --save-dev 可参考
# https://stackoverflow.com/questions/22891211/what-is-the-difference-between-save-and-save-dev

在完成以上步骤后，我们就完成了 tree-sitter 开发环境的配置。官方文档推荐我们将项目的 node_modules/.bin 目录添加到当前环境变量 PATH 中来使用 tree-sitter-cli，不过我建议直接使用 npx 命令激活环境。接着我们在项目根目录添加一个 grammar.js 文件即可进行编译了：

module.exports = grammar({
  name: 'yy',
  rules: {
      source_file: $ => 'include-yy',
  },
});

当你添加以上文件到项目根目录后，调用 tree-sitter generate 会在 src 目录下生成可编译的 C 文件，其中的 tree_sitter 目录包含源代码所需的头文件：

接着，我们可以使用 tree-sitter parse 命令测试某个文件是否满足 parser 规则。举例来说，如果 1.txt 中只包含 include-yy ，那么 tree-sitter parse 1.txt 会得到以下结果：

根据文档的说法，执行 tree-sitter parse 和 tree-sitter test 都需要 C/C++ 编译器的支持，因为需要编译 parser 得到可用的动态库。我倒是有些好奇如果没有安装编译器这些命令会有什么结果。

You might notice that the first time you run tree-sitter test after regenerating your parser, it takes some extra time. This is because Tree-sitter automatically compiles your C code into a dynamically-loadable library. It recompiles your parser as-needed whenever you update it by re-running tree-sitter generate.

Automatic Compilation | Creating-parsers

generate, test 和 parse 是 tree-sitter 最核心的三个子命令，除此之外还有 query, tags, highlight, build-wasm, playground 和 dump-languages ，不过似乎和 parser 的编写过程关系不大，读者可以阅读 Syntax Highlighting 和 Code Navigation Systems 等章节来深入了解，这里我就不介绍了。

在我们执行 tree-sitter generate 时，除了会在 src 目录下生成 parser.c 外，还有 tree_sitter/parser.h ，这个头文件会提供一些在 parser.c 中使用的基础定义。除了这些可被编译的产物外， generate 指令还会在 bindings 目录下生成 node 和 Rust 的 binding（当然还有项目根目录下的 binding.gyp），它们具体包括这些内容：

通过使用 tree-sitter test 命令，我们可以使用位于 test/corpus 或 corpus 目录下的文件进行测试。根据文档的说法，每一条语法规则对应于一个测试文件，每个测试文件中可以有多个测试用例。在测试文件中，测试用例名使用 == 分隔，输入的源代码位于名字的后面，随后将源代码与预期语法树输出使用 --- 分隔，其中语法树输出使用 S 表达式的格式，且只应包含有名字的节点。对于上一节的示例 parser 我们可以写出这样的测试文件：

===========================
Me
===========================

include-yy

---

(source_file)

接着使用 tree-sitter test 命令会看到如下结果（第二次调用时我将输入代码改为了 include-yyy ，从而导致测试错误）：

如果语言中的语法与测试文件冲突了，我们可以在 == 和 --- 的后面加上任意的由相同字符组成的后缀（文档中使用的是 | ），就像这样：

===========================||||
Me
===========================||||

include-yy

---||||

(source_file)

如果我们想要指定某个测试而不是一下子执行所有测试，可以使用 -f 参数： tree-sitter test -f "Me" 。如果我们想要在单个文件中创建多个测试用例，只需重复上面测试单元的结构即可，这个可以参考 tree-sitter-c 的一些测试文件。

除了使用 test 命令对位于特定位置的文件进行测试外，我们也可以使用 parse 命令来解析任意的指定文件。在上一节中我们指定单个文件 1.txt 进行解析，实际上 tree-sitter parse 命令支持任意数量的输入文件，它会对所有给定的文件进行解析，并输出解析结果。如果解析过程出现错误 tree-sitter 会返回一个非零状态码。我们可以指定 --quiet 标志让 tree-sitter 不输出解析结果，指定 --stat 让它输出解析成功和失败信息。文档将 parse 命令称为第二种测试手段：我们可以通过以下命令检测大量的文件：

tree-sitter parse 'examples/**/*.go' --quiet --stat

在这一小节中我对 using-parsers 给出的部分 C API 做了个总结，原先在写这篇文章时我打算将 tree-sitter parser 的编写和使用放在一篇文章中，现在看来内容有些过多了，这也就导致这一节和本文关系不是很大，读者可以选择跳过。当然提前了解一下 libtree-sitter 的用法也不是什么坏事就是了。

根据文档的说法，tree-sitter 提供了四种对象，分别是 TSLanguage, TSParser, TSTree 和 TSNode ：

• TSLanguage 是一个不透明的对象，定义了如何解析特定的编程语言，它的代码来自使用 tree-sitter-cli 编写并生成的 parser
• TSParser 是一个有状态的对象，可以通过 TSLanguage 指定要解析的语言，可由它根据源代码生成 TSTree 对象
• TSTree 表示由源文档得到的整个语法树，它包含表示源代码结构的 TSNode 对象，当源代码发生变化时它也可以被用来生成新的 TSTree 对象
• TSNode 表示语法树中的单个节点。它追踪源代码中它所在的起始和结束位置，以及它与其他节点（父兄子）的关系

根据文档中给出的 JSON 解析程序来看，首先我们需要创建 TSParser 指针类型的变量，随后将特定语言的 TSLanguage 对象绑定到 parser 上才能开始解析源代码：

// Declare the `tree_sitter_json` function, which is
// implemented by the `tree-sitter-json` library.
TSLanguage *tree_sitter_json();

int main() {
	// Create a parser.
	TSParser *parser = ts_parser_new();

	// Set the parser's language (JSON in this case).
	ts_parser_set_language(parser, tree_sitter_json());

	// Build a syntax tree based on source code stored in a string.
	const char *source_code = "[1, null]";
	TSTree *tree = ts_parser_parse_string(
		parser,
		NULL,
		source_code,
		strlen(source_code)
		);

	// Get the root node of the syntax tree.
	TSNode root_node = ts_tree_root_node(tree);
}

下面是一些 API 的介绍：

• ts_parser_parse_string ，使用 parser 解析 buffer 中的源代码

  TSTree *ts_parser_parse_string(
    TSParser *self,
    const TSTree *old_tree,
    const char *string,
    uint32_t length
  );

• ts_parser_parse ，使用 TSInput 结构而不是字符串 buffer 作为输入，它是更加灵活的 parse 函数

  TSTree *ts_parser_parse(
  	TSParser *self,
  	const TSTree *old_tree,
  	TSInput input
  	);
  
  typedef struct {
  	void *payload;
  	const char *(*read)(
  		void *payload,
  		uint32_t byte_offset,
  		TSPoint position,
  		uint32_t *bytes_read
  		);
  	TSInputEncoding encoding;
  } TSInput;

  可见 TSInput 结构中要有存放文本的 payload，读取文本的 raed 函数和文本的编码。

• ts_node_type ，获取节点的类型

  const char *ts_node_type(TSNode);

• ts_node_start_* 和 ts_node_end_* ，获取节点在源代码中的位置范围

  tree sitter 分别提供了返回行列坐标和 byte offset 的函数，Emacs 的 treesit 应该使用的是 offset：

  uint32_t ts_node_start_byte(TSNode);
  uint32_t ts_node_end_byte(TSNode);
  
  typedef struct {
  	uint32_t row;
  	uint32_t column;
  } TSPoint;
  
  TSPoint ts_node_start_point(TSNode);
  TSPoint ts_node_end_point(TSNode);

• 节点获取与访问

  我们可以使用 ts_tree_root_node 从 TSTree 获取 root 节点

  TSNode ts_tree_root_node(const TSTree *);

  tree sitter 还提供了许多节点访问函数，可以获取当前节点的兄弟节点，父节点和子节点：

  // Get the node's number of children.
  uint32_t ts_node_child_count(TSNode);
  // Get the node's child at the given index, where zero represents the first child.
  TSNode ts_node_child(TSNode, uint32_t);
  // Get the node's next / previous sibling.
  TSNode ts_node_next_sibling(TSNode);
  TSNode ts_node_prev_sibling(TSNode);
  // Get the node's immediate parent.
  TSNode ts_node_parent(TSNode);

  通过 ts_node_is_null 我们可以判断某个节点是否是空节点，也即判断它是否存在：

  // Check if the node is null. Functions like [`ts_node_child`] and
  // [`ts_node_next_sibling`] will return a null node to indicate that no such node
  // was found.
  bool ts_node_is_null(TSNode);

• 匿名节点与有名节点

  在以下语法规则中， if, ( 和 ) 是匿名节点，而 $._expression 和 $._statement 是有名节点：

  if_statement: ($) => seq("if", "(", $._expression, ")", $._statement);

  通过使用匿名节点相关的 api 我们可以避免处理匿名节点。

  /**
   * Check if the node is *named*. Named nodes correspond to named rules in the
   * grammar, whereas *anonymous* nodes correspond to string literals in the
   * grammar.
   */
  bool ts_node_is_named(TSNode);
  // Get the node's *named* child at the given index.
  TSNode ts_node_named_child(TSNode, uint32_t);
  // Get the node's number of *named* children.
  uint32_t ts_node_named_child_count(TSNode);
  // Get the node's next / previous *named* sibling.
  TSNode ts_node_next_named_sibling(TSNode);
  TSNode ts_node_prev_named_sibling(TSNode);

• 节点字段名

  在编写 tree sitter parser 时，我们可以给节点赋予字段名字，并通过以下函数进行访问：

  TSNode ts_node_child_by_field_name(
  	TSNode self,
  	const char *field_name,
  	uint32_t field_name_length
  	);

  有字段的节点拥有自己的 id，我们也可以通过名字获取 id 或通过 id 获取名字，并通过 id 访问节点的子节点：

  // Get the number of distinct field names in the language.
  uint32_t ts_language_field_count(const TSLanguage *);
  // Get the field name string for the given numerical id.
  const char *ts_language_field_name_for_id(const TSLanguage *, TSFieldId);
  // Get the numerical id for the given field name string.
  TSFieldId ts_language_field_id_for_name(const TSLanguage *, const char *, uint32_t);
  // Get the node's child with the given field name.
  TSNode ts_node_child_by_field_id(TSNode, TSFieldId);

以上就是 tree sitter 的基本 api，如果之后的文章有用到 tree sitter 的高级特性我也会介绍的。

在文档的 The Grammar DSL 一节给出了所有可用的内置函数，这里我直接给出函数与 EBNF 规则的对照表，就不使用过多文字解释了：

除了上面这些能够对应于 BNF 或 EBNF 的函数，tree-sitter 也提供了以下这些：

• token(rule) ，将给定的规则标记为单个 token
• token.immediate(rule) ，与 token 类似，但是仅在 token 前面没有空白字符时匹配
• alias(rule, name) ，让规则 rule 以名字 name 出现在语法树中，如果 name 是字符串字面量那么规则将会以匿名节点出现
• field(name, rule) ，为规则中匹配的子节点提供一个名字，方便访问

在表格中的函数很容易弄懂，但是列表中的那四个可就不是了。老实说，不管你是去看文档还是看我这里的解释你都可能不太懂它们到底是干什么的，仅仅是 grammar.js 中的代码可能并不能很好地体现出它们的具体作用，所以这里需要补充一些例子及其 C 语言对应产物。

module.exports = grammar({
    name: 'yy',
    rules: {
	source_file: $ => token($.abc),
	abc: $ => 'abc',
    },
});

//Error processing rule source_file_token1
//Caused by:
//    Grammar error: Unexpected rule Symbol(Symbol { kind: NonTerminal, index: 1 })

module.exports = grammar({
    name: 'yy',
    rules: {
	// try to delete token and see what happened in parser.c after generating
	source_file: $ => token(choice('ab', 'cd')),
    },
});

// use token
static const char * const ts_symbol_names[] = {
  [ts_builtin_sym_end] = "end",
  [aux_sym_source_file_token1] = "source_file_token1",
  [sym_source_file] = "source_file",
};
// not use token
static const char * const ts_symbol_names[] = {
  [ts_builtin_sym_end] = "end",
  [anon_sym_ab] = "ab",
  [anon_sym_cd] = "cd",
  [sym_source_file] = "source_file",
};

static bool ts_lex(TSLexer *lexer, TSStateId state) {
	START_LEXER();
	eof = lexer->eof(lexer);
	switch (state) {
	case 0:
		if (eof) ADVANCE(3);
		if (lookahead == 'a') ADVANCE(1);
		if (lookahead == 'c') ADVANCE(2);
		if (lookahead == '\t' ||
		    lookahead == '\n' ||
		    lookahead == '\r' ||
		    lookahead == ' ') SKIP(0)
		END_STATE();
	case 1:
		if (lookahead == 'b') ADVANCE(4);
		END_STATE();
	case 2:
		if (lookahead == 'd') ADVANCE(4);
		END_STATE();
	case 3:
		ACCEPT_TOKEN(ts_builtin_sym_end);
		END_STATE();
	case 4:
		ACCEPT_TOKEN(aux_sym_source_file_token1);
		END_STATE();
	default:
		return false;
	}
}

static bool ts_lex(TSLexer *lexer, TSStateId state) {
	START_LEXER();
	eof = lexer->eof(lexer);
	switch (state) {
	case 0:
		if (eof) ADVANCE(3);
		if (lookahead == 'a') ADVANCE(1);
		if (lookahead == 'c') ADVANCE(2);
		if (lookahead == '\t' ||
		    lookahead == '\n' ||
		    lookahead == '\r' ||
		    lookahead == ' ') SKIP(0)
		END_STATE();
	case 1:
		if (lookahead == 'b') ADVANCE(4);
		END_STATE();
	case 2:
		if (lookahead == 'd') ADVANCE(5);
		END_STATE();
	case 3:
		ACCEPT_TOKEN(ts_builtin_sym_end);
		END_STATE();
	case 4:
		ACCEPT_TOKEN(anon_sym_ab);
		END_STATE();
	case 5:
		ACCEPT_TOKEN(anon_sym_cd);
		END_STATE();
	default:
		return false;
	}
}

4.1.2. token.immediate

从功能上来说它 token.immediate 基本与 token 一致，但是它会保证它与前一 token 之间无空白字符时才会匹配。读者可以比较一下以下代码生成的 ts_lex 函数的不同之处：

module.exports = grammar({
    name: 'yy',
    rules: {
	// try generate with token instead of token.immediate
	source_file: $ => seq('1', token.immediate(choice('u', 'i'))),
    },
});

有 token.immediate ：

static bool ts_lex(TSLexer *lexer, TSStateId state) {
	START_LEXER();
	eof = lexer->eof(lexer);
	switch (state) {
	case 0:
		if (eof) ADVANCE(2);
		if (lookahead == '1') ADVANCE(3);
		if (lookahead == 'i' ||
		    lookahead == 'u') ADVANCE(4);
		if (lookahead == '\t' ||
		    lookahead == '\n' ||
		    lookahead == '\r' ||
		    lookahead == ' ') SKIP(1)
		END_STATE();
	case 1:
		if (eof) ADVANCE(2);
		if (lookahead == '1') ADVANCE(3);
		if (lookahead == '\t' ||
		    lookahead == '\n' ||
		    lookahead == '\r' ||
		    lookahead == ' ') SKIP(1)
		END_STATE();
	case 2:
		ACCEPT_TOKEN(ts_builtin_sym_end);
		END_STATE();
	case 3:
		ACCEPT_TOKEN(anon_sym_1);
		END_STATE();
	case 4:
		ACCEPT_TOKEN(aux_sym_source_file_token1);
		END_STATE();
	default:
		return false;
	}
}

仅有 token ：

static bool ts_lex(TSLexer *lexer, TSStateId state) {
	START_LEXER();
	eof = lexer->eof(lexer);
	switch (state) {
	case 0:
		if (eof) ADVANCE(1);
		if (lookahead == '1') ADVANCE(2);
		if (lookahead == 'i' ||
		    lookahead == 'u') ADVANCE(3);
		if (lookahead == '\t' ||
		    lookahead == '\n' ||
		    lookahead == '\r' ||
		    lookahead == ' ') SKIP(0)
		END_STATE();
	case 1:
		ACCEPT_TOKEN(ts_builtin_sym_end);
		END_STATE();
	case 2:
		ACCEPT_TOKEN(anon_sym_1);
		END_STATE();
	case 3:
		ACCEPT_TOKEN(aux_sym_source_file_token1);
		END_STATE();
	default:
		return false;
	}
}

此时仅从代码不太容易看出 token 与 token.immediate 的区别来，不过明显可以看出后者的 lex 函数比前者多出一个状态。而且为 token.immediate 时，以下测试会在 tree-sitter parse 中报错，但为 token 时能正常解析：

1 u

tree-sitter-c 中的宏定义可能能比较好地说明 token.immediate 的用法：

preproc_def: $ => seq(
    preprocessor('define'),
    field('name', $.identifier),
    field('value', optional($.preproc_arg)),
    token.immediate(/\r?\n/),
)

module.exports = grammar({
    name: 'yy',
    rules: {
	source_file: $ => $._exp,
	_exp: $ => choice(
	    $.number,
	    seq($._exp, $.op, $.number),
	),
	// try remove `alias` and generate
	op: $ => choice(
	    alias('+', $.add),
	    alias('*', $.mul),
	),
	number: $ => /[0-9]+/,
    },
});

tree-sitter parse 1.txt
(source_file [0, 0] - [1, 0]
  (number [0, 0] - [0, 1])
  (op [0, 2] - [0, 3]
    (add [0, 2] - [0, 3]))
  (number [0, 4] - [0, 5])
  (op [0, 6] - [0, 7]
    (mul [0, 6] - [0, 7]))
  (number [0, 8] - [0, 9]))

tree-sitter parse 1.txt
(source_file [0, 0] - [1, 0]
  (number [0, 0] - [0, 1])
  (op [0, 2] - [0, 3])
  (number [0, 4] - [0, 5])
  (op [0, 6] - [0, 7])
  (number [0, 8] - [0, 9]))

module.exports = grammar({
  name: 'yy',
  rules: {
      source_file: $ => $._exp,
      _exp: $ => choice(
	  $.number,
	  seq($._exp, $.op, $.number),
      ),
      op: $ => choice(
	  $.add,
	  $.mul,
      ),
      add: $ => '+',
      mul: $ => '*',
      number: $ => /[0-9]+/,
  },
});

module.exports = grammar({
  name: 'yy',
  rules: {
      source_file: $ => $._exp,
      _exp: $ => choice(
	  $.number,
	  seq($._exp, alias($.op, $.po), $.number),
      ),
      op: $ => choice(
	  alias($.add, $.sub),
	  alias($.mul, $.div),
      ),
      add: $ => '+',
      mul: $ => '*',
      number: $ => /[0-9]+/,
  },
});

tree-sitter parse 1.txt
(source_file [0, 0] - [1, 0]
  (number [0, 0] - [0, 1])
  (po [0, 2] - [0, 3]
    (sub [0, 2] - [0, 3]))
  (number [0, 4] - [0, 5])
  (po [0, 6] - [0, 7]
    (div [0, 6] - [0, 7]))
  (number [0, 8] - [0, 9]))

module.exports = grammar({
  name: 'yy',
  rules: {
      source_file: $ => $._exp,
      _exp: $ => choice(
	  $.number,
	  seq($._exp, alias($.op, 'op'), $.number),
      ),
      op: $ => choice(
	  alias($.add, $.sub),
	  alias($.mul, $.div),
      ),
      add: $ => '+',
      mul: $ => '*',
      number: $ => /[0-9]+/,
  },
});

tree-sitter parse 1.txt
(source_file [0, 0] - [1, 0]
  (number [0, 0] - [0, 1])
    (sub [0, 2] - [0, 3])
  (number [0, 4] - [0, 5])
    (div [0, 6] - [0, 7])
  (number [0, 8] - [0, 9]))

module.exports = grammar({
    name: 'yy',
    rules: {
	source_file: $ => seq('(',
	    field('one', $.number), ',',
	    field('two', $.number), ',',
	    field('three', $.number), optional(','),
	    ')',
	),
	number: $ => /[0-9]+/,
    },
});

tree-sitter parse 1.txt
(source_file [0, 0] - [1, 0]
  one: (number [0, 1] - [0, 2])
  two: (number [0, 4] - [0, 5])
  three: (number [0, 7] - [0, 8]))

不管你学的是什么编程语言，一般入门教程的前几章都会提到并介绍表达式运算符的优先级和结合性这个知识点。C 语言中各算符的优先级可以参考 cppreference.com，JavaScript 可以参考 MDN。

通俗地说，优先级就是算符与算子的结合紧密程度，结合性描述了表达式中连续出现多个相同优先级操作符时的操作执行顺序。在一个包含多个操作符和操作数的表达式中，优先级高的操作符会更先与相邻的操作数结合，左结合操作符会将左边的操作数当作一个整体，右结合则将右侧操作数当作整体。但是更严谨地说，优先级和结合性的概念作用于产生式规则而不是操作符，优先级和结合性通过产生式的规则来体现，下面的代码及其解析结果可以说明这一点：

module.exports = grammar({
    name: 'yy',
    rules: {
	src: $ => $.add_exp,
	add_exp: $ => choice(
	    $.mul_exp,
	    seq($.add_exp, token(choice('+', '-')), $.mul_exp),
	),
	mul_exp: $ => choice(
	    $.number,
	    seq($.mul_exp, token(choice('*', '/')), $.number),
	),
	number: $ => /[0-9]+/,
    },
})

还是解析 1 + 2 * 3 ，我们可以得到以下结果：

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (add_exp [0, 0] - [0, 9]
    (add_exp [0, 0] - [0, 1]
      (mul_exp [0, 0] - [0, 1]
	(number [0, 0] - [0, 1])))
    (mul_exp [0, 4] - [0, 9]
      (mul_exp [0, 4] - [0, 5]
	(number [0, 4] - [0, 5]))
      (number [0, 8] - [0, 9]))))

上面的规则表示 mul_exp 具有比 add_exp 更高的优先级，这是因为它的嵌套“更深”，需要首先被解析。上面的规则也表示了结合性：不管是加减法还是乘除法都具有左结合性，这可以通过解析 1 + 2 + 3 + 4 的结果来体现（注意树的生长方式）：

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (add_exp [0, 0] - [0, 13]
    (add_exp [0, 0] - [0, 9]
      (add_exp [0, 0] - [0, 5]
        (add_exp [0, 0] - [0, 1]
          (mul_exp [0, 0] - [0, 1]
            (number [0, 0] - [0, 1])))
        (mul_exp [0, 4] - [0, 5]
          (number [0, 4] - [0, 5])))
      (mul_exp [0, 8] - [0, 9]
        (number [0, 8] - [0, 9])))
    (mul_exp [0, 12] - [0, 13]
      (number [0, 12] - [0, 13]))))

如果加减乘除具有右结合性，那么同样是 1 + 2 + 3 + 4 我们会得到以下结果：

module.exports = grammar({
    name: 'yy',
    rules: {
	src: $ => $.add_exp,
	add_exp: $ => choice(
	    $.mul_exp,
	    seq($.mul_exp, token(choice('+', '-')), $.add_exp),
	),
	mul_exp: $ => choice(
	    $.number,
	    seq($.number, token(choice('*', '/')), $.mul_exp),
	),
	number: $ => /[0-9]+/,
    },
})

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (add_exp [0, 0] - [0, 13]
    (mul_exp [0, 0] - [0, 1]
      (number [0, 0] - [0, 1]))
    (add_exp [0, 4] - [0, 13]
      (mul_exp [0, 4] - [0, 5]
	(number [0, 4] - [0, 5]))
      (add_exp [0, 8] - [0, 13]
	(mul_exp [0, 8] - [0, 9]
	  (number [0, 8] - [0, 9]))
	(add_exp [0, 12] - [0, 13]
	  (mul_exp [0, 12] - [0, 13]
	    (number [0, 12] - [0, 13])))))))

语言标准中为了表示优先级和结合性会广泛使用上面这种结构，tree-sitter 文档中给出了根据 ES 标准解析 return x + y; 所带来的产生式嵌套：

ReturnStatement          ->  'return' Expression
Expression               ->  AssignmentExpression
AssignmentExpression     ->  ConditionalExpression
ConditionalExpression    ->  LogicalORExpression
LogicalORExpression      ->  LogicalANDExpression
LogicalANDExpression     ->  BitwiseORExpression
BitwiseORExpression      ->  BitwiseXORExpression
BitwiseXORExpression     ->  BitwiseANDExpression
BitwiseANDExpression     ->  EqualityExpression
EqualityExpression       ->  RelationalExpression
RelationalExpression     ->  ShiftExpression
ShiftExpression          ->  AdditiveExpression
AdditiveExpression       ->  MultiplicativeExpression
MultiplicativeExpression ->  ExponentiationExpression
ExponentiationExpression ->  UnaryExpression
UnaryExpression          ->  UpdateExpression
UpdateExpression         ->  LeftHandSideExpression
LeftHandSideExpression   ->  NewExpression
NewExpression            ->  MemberExpression
MemberExpression         ->  PrimaryExpression
PrimaryExpression        ->  IdentifierReference

现在我们可以回收一下文章开头提到的 tree-sitter-wgsl 官方实现了，我之所以说它基本上是没用的实现，就是因为它并没有使用 tree-sitter 提供的优先级和结合性内置函数来消除这些繁琐的嵌套，举例来说，表达式 1 + 2 + 3 + 4 在 tree-sitter-wgsl 中的解析结果是这样的：

var bar = 1 + 2 + 3 + 4;
------------------------
tree-sitter parse 1.txt
(translation_unit [0, 0] - [1, 0]
  (global_variable_decl [0, 0] - [0, 23]
    (variable_decl [0, 0] - [0, 7]
      (var [0, 0] - [0, 3])
      (ident [0, 4] - [0, 7]))
    (equal [0, 8] - [0, 9])
    (expression [0, 10] - [0, 23]
      (relational_expression [0, 10] - [0, 23]
        (shift_expression [0, 10] - [0, 23]
          (additive_expression [0, 10] - [0, 23]
            (additive_expression [0, 10] - [0, 19]
              (additive_expression [0, 10] - [0, 15]
                (additive_expression [0, 10] - [0, 11]
                  (multiplicative_expression [0, 10] - [0, 11]
                    (unary_expression [0, 10] - [0, 11]
                      (singular_expression [0, 10] - [0, 11]
                        (primary_expression [0, 10] - [0, 11]
                          (const_literal [0, 10] - [0, 11]
                            (int_literal [0, 10] - [0, 11])))))))
                (plus [0, 12] - [0, 13])
                (multiplicative_expression [0, 14] - [0, 15]
                  (unary_expression [0, 14] - [0, 15]
                    (singular_expression [0, 14] - [0, 15]
                      (primary_expression [0, 14] - [0, 15]
                        (const_literal [0, 14] - [0, 15]
                          (int_literal [0, 14] - [0, 15])))))))
              (plus [0, 16] - [0, 17])
              (multiplicative_expression [0, 18] - [0, 19]
                (unary_expression [0, 18] - [0, 19]
                  (singular_expression [0, 18] - [0, 19]
                    (primary_expression [0, 18] - [0, 19]
                      (const_literal [0, 18] - [0, 19]
                        (int_literal [0, 18] - [0, 19])))))))
            (plus [0, 20] - [0, 21])
            (multiplicative_expression [0, 22] - [0, 23]
              (unary_expression [0, 22] - [0, 23]
                (singular_expression [0, 22] - [0, 23]
                  (primary_expression [0, 22] - [0, 23]
                    (const_literal [0, 22] - [0, 23]
                      (int_literal [0, 22] - [0, 23])))))))))))
  (semicolon [0, 23] - [0, 24]))

什么狗屎😅。

tree-sitter 为我们提供了这些内置函数来 显式 指定产生式规则的优先级和结合性：

• prec(number, rule) ，它为规则提供一个数字指定的优先级来解决 parser 生成时的 LR(1) 冲突。当两条规则可能产生歧义时 tree-sitter 会选择优先级更高的那个。默认情况下所有规则的优先级都是 0
• prec.left([number], rule) ，它将规则标记为 左结合 （可选提供一个优先级数字），当在所有规则都具有相同优先级数值的情况下出现 LR(1) 冲突时，tree-sitter 会根据优先级规则消除冲突
• prec.right([number], rule) ，它将规则标记为 右结合 （同样可选提供优先级）

还是上面的加减乘除表达式解析，现在让我们加上指数运算来展示右结合。根据 Python 的操作符优先级，指数 ** 高于乘法高于加法，我们可以如此实现：

module.exports = grammar({
    name: 'yy',
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.number,
	    $.paren_exp,
	    $.binary_exp,
	),
	paren_exp: $ => seq('(', $._exp, ')'),
	binary_exp: $ => choice(
	    prec.right(3, seq(
		field('l', $._exp),
		field('op', '**'),
		field('r', $._exp))),
	    prec.left(2, seq(
		field('l', $._exp),
		field('op', token(choice('*', '/'))),
		field('r', $._exp))),
	    prec.left(1, seq(
		field('l', $._exp),
		field('op', token(choice('+', '-'))),
		field('r', $._exp))),
	),
	number: $ => /[0-9]+/,
    },
})

以下是解析 1 + 2 * 3 ** (1 + 2) 的结果：

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (binary_exp [0, 0] - [0, 20]
    l: (number [0, 0] - [0, 1])
    r: (binary_exp [0, 4] - [0, 20]
      l: (number [0, 4] - [0, 5])
      r: (binary_exp [0, 8] - [0, 20]
	l: (number [0, 8] - [0, 9])
	r: (paren_exp [0, 13] - [0, 20]
	  (binary_exp [0, 14] - [0, 19]
	    l: (number [0, 14] - [0, 15])
	    r: (number [0, 18] - [0, 19])))))))

在指定优先级这件事上，除了全序（total order）外，我们还可以使用偏序（partial order），不过这在文档中并没有得到说明。简单来理解就是偏序允许我们定义不同组别的优先级关系，组别内能够进行比较，但是组别间不能进行比较。通过使用与 rules 同级的 precedences 我们可以定义偏序优先级，它是一个包含字符串数组的数组，字符串数组的优先级单调递减。我们可以这样实现上面的优先级：

module.exports = grammar({
    name: 'yy',
    precedences: $ => [
	['expt', 'mul', 'add'],
    ],
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.number,
	    $.paren_exp,
	    $.binary_exp,
	),
	paren_exp: $ => seq('(', $._exp, ')'),
	binary_exp: $ => choice(
	    prec.right('expt', seq(
		field('l', $._exp),
		field('op', '**'),
		field('r', $._exp))),
	    prec.left('mul', seq(
		field('l', $._exp),
		field('op', token(choice('*', '/'))),
		field('r', $._exp))),
	    prec.left('add', seq(
		field('l', $._exp),
		field('op', token(choice('+', '-'))),
		field('r', $._exp))),
	),
	number: $ => /[0-9]+/,
    },
})

precedences 的使用方式可以参考 tree-sitter-javascript，里面还有一些更加神奇的用法。

在上一节中我展示了如何通过 prec 解决优先级的问题，但并未展示使用 tree-sitter generate 试图生成带有冲突的 grammar.js 的结果，对于以下语法我们会得到如下输出：

module.exports = grammar({
    name: 'yy',
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.number,
	    $.binary_exp,
	),
	binary_exp: $ => seq($._exp, choice('*', '/'), $._exp),
	number: $ => /[0-9]+/,
    },
})

可见 tree-sitter 能够识别出语法中的冲突，并给出合适的建议，这些建议对于编写一个可用的 parser 非常有用。如果我们按照上面的第一条方法进行修复，那就是通过 prec 等函数指定结合性的方法。当然它也指出了另一种方法：通过 conflicts 指定现有的冲突：

module.exports = grammar({
    name: 'yy',
    conflicts: $ => [
	[$.binary_exp],
    ],
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.number,
	    $.binary_exp,
	),
	binary_exp: $ => seq($._exp, choice('*', '/'), $._exp),
	number: $ => /[0-9]+/,
    },
})


// parse 1 * 2 * 3
// tree-sitter parse 1.txt
// (src [0, 0] - [1, 0]
//   (binary_exp [0, 0] - [0, 9]
//     (binary_exp [0, 0] - [0, 5]
//       (number [0, 0] - [0, 1])
//       (number [0, 4] - [0, 5]))
//     (number [0, 8] - [0, 9])))

可见在加上 conflicts 后结合性冲突被消除了，而且还是我们所期望的 左结合 。如果你有意注意上面截图中的 Possible interpretations 中规则的顺序，你会发现左结合在右结合之前。如果我们想要让右结合的的优先级高于左结合，我们可以使用 pred.dynamic ： binary_exp: $ => pred.dynamic(1, pred.right(...)) 。但是这个用法并不能显著体现出动态优先级的作用，毕竟我完全可以直接使用 pred.right 。文档是这样描述 pred.dynamic 和 conflicts 的：

• prec.dynamic(number, rule) ，该函数与 prec 类似，但优先级应用于 运行时 而不是 parser 生成时。这只在使用 conflicts 处理冲突以及存在真正歧义（genuine ambiguity）时才需要： 多个规则 正确匹配给定的代码片段。在这种情况下，tree-sitter 比较与每个规则关联的总动态优先级，并选择具有最高优先级的那个
• conflicts 一个由规则名称数组组成的数组。每个内部数组代表一组在语法中存在的 LR(1) 冲突的规则。当这些冲突在运行时发生时，tree-sitter 将使用 GLR 算法来探索所有可能的解释。如果多个解析最终成功，tree-sitter 将选择对应规则具有最高动态优先级的子树

我没有认真学过 parser 知识，这里只能给出我对这类所谓运行时冲突的粗浅认识：即在 tree-sitter 中无法使用 prec 和 prec.left 或 prec.right 消除的冲突，换言之就是语言中固有的 LR(1) 冲突。要解决这类冲突，tree-sitter 给出的方法是 GLR，但我也没有从理论上尝试理解过它，这里就打住了。下面我会给出一些使用 conflicts 解决冲突的例子，方便读者理解和使用。

在 C++ 中一个显而易见的例子就是嵌套的模板和比较操作符以及位移操作符之间的冲突。（更加详细的描述可以参考 C++ Template Ambiguity 和 Right angle bracket），在 C++ Primer 5th 中是这样描述的：

在 C++ 语法的 EBNF 描述中，你可以发现（善用 Ctrl+F） template_argument_list （模板列表）中的 template_argument 可为 assignment_expression 表达式。而如果你顺着 assignment_expression 往上找的话，你能够找到以下链条：

template_argument_list = template_argument | template_argument_list ',' template_argument
template_argument = assignment_expression | type_id | id_expression

assignment_expression -> conditional_expression -> logical_or_expression ->
logical_and_expression -> inclusive_or_expression -> exclusive_or_expression ->
and_expression -> equality_expression -> rational_expression(<, >, <=, >=) ->
shift_expression(<<, >>) -> additive_expression(+, -) ->
multiplicative_expression(*, /, %) -> pm_expression -> cast_expression ->
unary_expression -> postfix_expression -> primary_expression -> id_expression ->
unqualified_id -> template_id

template_id = template_name '<' [template_argument_list] '>'

哈哈，绕了一圈又绕回来了，而且实际还不止这一条路径。那么这样的圈圈有什么问题呢，我们现在写个简化的 tree-sitter 语法看看：

module.exports = grammar({
    name: 'yy',
    conflicts: $ => [
	//[$._exp, $.template_id],
	//[$._exp, $.template_argument_list],
    ],
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.binary_exp,
	    $.id,
	    $.number,
	    $.template_id,
	),
	id: $ => token(/([_\p{XID_Start}][\p{XID_Continue}]+)|([\p{XID_Start}])/uy),
	number: $ => /[0-9]+/,
	template_id: $ => seq($.id, $.template_argument_list),
	template_argument_list: $ => seq(
	    '<',
	    commaSep(choice(
		$._exp,
		$.template_id,
	    )),
	    '>'),
	binary_exp: $ => choice(
	    prec.right(1, seq($._exp, alias('<', $.lt), $._exp)),
	    prec.right(1, seq($._exp, alias('>', $.gt), $._exp)),
	    prec.right(2, seq($._exp, alias('<<', $.shl), $._exp)),
	    prec.right(2, seq($._exp, alias('>>', $.shr), $._exp)),
	    prec.right(3, seq($._exp, alias('+', $.add), $._exp)),
	    prec.right(3, seq($._exp, alias('-', $.sub), $._exp)),
	    prec.right(4, seq($._exp, alias('*', $.mul), $._exp)),
	    prec.right(4, seq($._exp, alias('/', $.div), $._exp)),
	),
    },
})

function commaSep(rule) {
  return optional(commaSep1(rule));
}
function commaSep1(rule) {
  return seq(rule, repeat(seq(',', rule)));
}

对以上语法使用 tree-sitter generate 命令，我们可以得到如下结果：

在上面的输出中，只有最后一条是靠谱的（我实在想不到如何给 _exp 添加结合性或者是优先级）。现在让我们加上 conflicts:$ => [[$._exp, $.template_id],], 试试：

现在 tree-sitter 提示我们仍然存在冲突，我们继续加上 [$._exp, $.template_argument_list] ，然后就可以正常生成了，但是在解析类似 vec<vec<2>> 的字符串时会得到错误的结果：

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (binary_exp [0, 0] - [0, 11]
    (id [0, 0] - [0, 3])
    (lt [0, 3] - [0, 4])
    (binary_exp [0, 4] - [0, 11]
      (id [0, 4] - [0, 7])
      (lt [0, 7] - [0, 8])
      (binary_exp [0, 8] - [0, 11]
	(number [0, 8] - [0, 9])
	(shr [0, 9] - [0, 11])
	(id [0, 11] - [0, 11])))))
1.txt	0 ms	(MISSING id [0, 11] - [0, 11])

可见此时我们的 parser 还是不能正常处理模板与 > 和 >> 的区别。我们需要赋予位于 template_argument_list 中的元素以不同的优先级：

template_argument_list: $ => seq(
    '<',
    commaSep(choice(
	prec.dynamic(1, $._exp),
	prec.dynamic(2, $.template_id),
    )),
    '>')

但是光是这样做似乎还是不够，我参考了 tree-sitter-cpp 的相同部分实现，发现它对模板的结尾符号赋予了一个非常奇怪的优先级：

template_argument_list: $ => seq(
    '<',
    commaSep(choice(
	prec.dynamic(3, $.type_descriptor),
	prec.dynamic(2, alias($.type_parameter_pack_expansion, $.parameter_pack_expansion)),
	prec.dynamic(1, $._expression),
    )),
    alias(token(prec(1, '>')), '>'),
)

直到现在我也不太理解这个 token(prec(1, '>')) 到底有什么用… 不过这样做之后代码确实能够工作了（注意下面对 binary_expression 内各规则的优先级的修改）：

module.exports = grammar({
    name: 'yy',
    conflicts: $ => [
	[$._exp, $.template_id],
	[$._exp, $.template_argument_list],
    ],
    rules: {
	src: $ => $._exp,
	_exp: $ => choice(
	    $.binary_exp,
	    $.id,
	    $.number,
	    $.template_id,
	),
	id: $ => token(/([_\p{XID_Start}][\p{XID_Continue}]+)|([\p{XID_Start}])/uy),
	number: $ => /[0-9]+/,
	template_id: $ => seq($.id, $.template_argument_list),
	template_argument_list: $ => seq(
	    '<',
	    commaSep(choice(
		prec.dynamic(1, $._exp),
		prec.dynamic(2, $.template_id),
	    )),
	    alias(token(prec(1, '>')), '>')),
	binary_exp: $ => choice(
	    prec.right(2, seq($._exp, alias('<', $.lt), $._exp)),
	    prec.right(2, seq($._exp, alias('>', $.gt), $._exp)),
	    prec.right(3, seq($._exp, alias('<<', $.shl), $._exp)),
	    prec.right(3, seq($._exp, alias('>>', $.shr), $._exp)),
	    prec.right(4, seq($._exp, alias('+', $.add), $._exp)),
	    prec.right(4, seq($._exp, alias('-', $.sub), $._exp)),
	    prec.right(5, seq($._exp, alias('*', $.mul), $._exp)),
	    prec.right(5, seq($._exp, alias('/', $.div), $._exp)),
	),
    },
})

function commaSep(rule) {
  return optional(commaSep1(rule));
}
function commaSep1(rule) {
  return seq(rule, repeat(seq(',', rule)));
}

还是对于 vec<vec<1>> ，现在我们能得到如下正确结果：

tree-sitter parse 1.txt
(src [0, 0] - [1, 0]
  (template_id [0, 0] - [0, 11]
    (id [0, 0] - [0, 3])
    (template_argument_list [0, 3] - [0, 11]
      (template_id [0, 4] - [0, 10]
	(id [0, 4] - [0, 7])
	(template_argument_list [0, 7] - [0, 10]
	  (number [0, 8] - [0, 9]))))))

目前我对 conflicts 和 prec.dynamic 的理解是非常粗浅的，我也不知道 cpp parser 到底玩了些什么魔法。读者若遇到语言中固有 LR(1) 冲突，建议去具有相似冲突的已有 tree-sitter 实现中找找灵感。

另外需要注意的是，你可以看到我在 grammar.js 中使用了自定义的 JS 函数，目前我不知道 tree-sitter 对 JS 的支持究竟到了怎样的地步，也许只要是返回 DSL 函数表达式都行？读者可以参考各 parser 实现中出现的 JS 语言用法，尤其是 C/C++ 这对父子（从 tree-sitter parser 依赖关系的意义上来看）。

如果你看过了《编译原理》，你就会知道词法分析和语法分析是两个分开的过程。虽然我们通过 tree-sitter-cli 并不会得到单独的 lexer 或者 scanner，但正如你在上面的 C 代码中看到的，tree-sitter parser 并不是没有词法分析过程，而是我们无需自己调用 lexer 来做词法分析。在这一节中我会介绍文档中 Lexical Analysis 一节中的内容，同时尝试解答上面关于 token(prec(1, '>')) 的一些疑惑。

文档列出了 lexer 的行为规则，这里简单翻译一下：

• Context-aware Lexing tree-sitter 在解析过程中按需执行词法分析。在源文档的任何给定位置，lexer 只尝试识别在该位置有效的 token
• Lexical Precedence 当优先级函数（指 prec 系列函数）在 token 函数内使用时，给定的显式优先级值作为指令传递给 lexer。如果在文档的给定位置有两个有效的 token 与字符匹配，tree-sitter 将选择具有更高优先级的那一个
• Match Length 如果在源文档给定位置有多个具有相同优先级的有效 token 与字符匹配，tree-sitter 将选择匹配字符序列最长的 token
• Match Specificity 如果有两个有效的 token 具有相同的优先级并且都匹配相同数量的字符，tree-sitter 将倾向于选择在语法中作为 String 指定的 token，而不是作为 Regexp 指定的 token
• Rule Order 如果上述任何标准都无法用来选择一个 token 而不选择另一个，tree-sitter 将倾向于选择在语法中更早出现的 token

（这篇文章的时间跨度实在是有点大了，我大概在一周前写完了上一小节，如果能把对在 token 内的解释放到上面 C++ 的部分应该更好一点）

如你所见，上面规则的第二条说明了在 token 函数内使用优先级函数时的行为，它修改的是 lexer 中的优先级，而不是解析过程的优先级。文档是这样描述的：

One common mistake involves not distinguishing lexical precedence from parse precedence. Parse precedence determines which rule is chosen to interpret a given sequence of tokens. Lexical precedence determines which token is chosen to interpret at a given position of text and it is a lower-level operation that is done first.

虽然我认识到了 token(prec()) 与一般 prec 的不同之处，但上一节 template_id 部分的代码还是有些难以理解，目前只能搁置在这里了。和 lexer 有关的字段有 word ， extras 和 externals ，其中 externals 文档已经介绍的比较详细了（至少能知道怎么写）， word 起的作用也足够明显，此处就不介绍了。

我们可以使用 extras 指定可出现在源文档任意位置的 token，默认情况下它就是空格，通过添加注释规则我们可以忽略掉文档注释，比如以下是 tree-sitter-c 的 extras 字段：

extras: $ => [
    /\s|\\\r?\n/,
    $.comment,
  ],

所谓 public field，在 tree-sitter DSL 中指的是 grammar 接受的结构中的字段，在上面我们已经见识过了 name, rules, precedences 和 extras 等字段，现在提一下剩下的两个： inline 和 supertypes 。

文档关于 inline 的描述是这样的，由于不长我就懒得翻译了：

inline - an array of rule names that should be automatically removed from the grammar by replacing all of their usages with a copy of their definition. This is useful for rules that are used in multiple places but for which you don’t want to create syntax tree nodes at runtime.

从描述上来看， inline 和内联函数很像，生成的语法树中不会存在被内联的节点。看过本文前面的读者应该还记得前面提到过匿名节点（简单字符串或正则）和隐藏节点（名字前面带 _ 的规则），这两者在语法树中是实际存在的，即使 tree-sitter 的某些 API 会忽略掉它们。位于 inline 数组中的规则会被完全展开而在解析得到的语法数中完全不存在。这里的讨论应该能够说明这一点，我就不举例说明了（本文不涉及 API 使用，举也举不出）。

最后的 supertypes 只有轻飘飘的一句话：

supertypes an array of hidden rule names which should be considered to be ‘supertypes’ in the generated node types file.

请参考引文中的链接来了解它的用法，目前我也不知道有什么用。