使用 tree-sitter 生成语法树（未完成）

介绍

Tree-sitter 是一个解析器生成工具和增量解析库。它可以为源文件构建具体的语法树，并在编辑源文件时有效地更新语法树。有以下特点：

  • 通用 足以解析任何编程语言的通用性
  • 快速 能够在每次编辑源码时及时解析
  • 强大 即使存在语法错误，也足够强大以提供有用的结果
  • 无依赖 所以那些用纯 C 编写的运行时库（runtime lib），可以嵌入到任何应用程序中

通过tree-sitter可以将目标语言实时解析为语法树。

你可以在以下语言中使用tree-sitter:

  • Haskell
  • JavaScript (Node.js)
  • JavaScript (Wasm)
  • Lua
  • OCaml
  • Python
  • Ruby
  • Rust
  • Swift
  • Kotlin
  • Java

你可以使用tree-sitter解析以下语言：

  • Bash
  • C
  • C#
  • C++
  • Common Lisp
  • CSS
  • CUDA
  • DOT
  • Elm
  • Emacs Lisp
  • Eno
  • ERB / EJS
  • Fennel
  • GLSL (OpenGL Shading Language)
  • Go
  • HCL
  • HTML
  • Java
  • JavaScript
  • JSON
  • Lua
  • Make
  • Markdown
  • OCaml
  • PHP
  • Python
  • Ruby
  • Rust
  • R
  • S-expressions
  • SPARQL
  • SystemRDL
  • Svelte
  • TOML
  • Turtle
  • TypeScript
  • Verilog
  • VHDL
  • Vue
  • YAML
  • WASM
  • WGSL WebGPU Shading Language

以下语言的解析器还在开发：

  • Agda
  • Elixir
  • Erlang
  • Dockerfile
  • Go mod
  • Hack
  • Haskell
  • Julia
  • Kotlin
  • Nix
  • Objective-C
  • Org
  • Perl
  • Protocol Buffers
  • Scala
  • Sourcepawn
  • Swift
  • SQL

安装

为了创建tree-sitter解析器，需要先安装tree-sitter。
有以下三种方式可以安装：
(记得放入环境变量，以方便使用)

npm

npm install tree-sitter-cli

二进制

去GitHub的release界面下载你的平台的二进制文件

cargo

cargo install tree-sitter-cli

创建

文件夹

之后的操作都在创建的文件夹进行

1
2
mkdir tree-sitter-${YOUR_LANGUAGE_NAME}
cd tree-sitter-${YOUR_LANGUAGE_NAME}

规则文件

创建规则

创建grammar.js文件（这个文件是告诉tree-sitter解析规则的），并在文件内输入以下代码

1
2
3
4
5
6
7
8
module.exports = grammar({
  name: 'YOUR_LANGUAGE_NAME',

  rules: {
    // TODO: add the actual grammar rules
    source_file: $ => 'hello'
  }
});

例如以上的示例，规定了一个规则，hello匹配一个名为source_file的规则，tree-sitter在解析语言文件时，会把文件内的hello字符解释为规则source_file。

具体如何编写规则将在后面叙述。

测试规则

生成测试文件，example.your-lang是要解析的目标文件（你要解析的语言的文件）

1
echo 'hello' > example.your-lang

使用tree-sitter进行解析

1
tree-sitter parse example.your-lang

会得到以下结果

1
(source_file [0, 0] - [1, 0])

表明在第0行的第0个字符到第1行的第0个字符匹配到了规则source_file

编写规则

具体文档

CLI

tree-sitter {CMD}

generate

tree-sitter generate 这条命令是最重要的。该命令读取当前工作目录中的 Grammar.js 文件并创建一个名为 src/parser.c 的文件，该文件实现了解析器。更改语法后，只需再次运行 tree-sitter generate 即可。

第一次运行 tree-sitter generate 时，它​​还会生成一些其他文件：

文件名 描述
binding.gyp 这个文件告诉 Node.js 如何编译你的语言。
bindings/node/index.js 这是 Node.js 在使用您的语言时最初加载的文件。
bindings/node/binding.cc 当在 Node.js 中使用时，此文件将您的语言包装在 JavaScript 对象中。
bindings/rust/lib.rs 当在 Rust 中使用时，此文件将您的语言包装在 Rust crate 中。
bindings/rust/build.rs 这个文件包含了 Rust crate 的构建过程。
src/tree_sitter/parser.h 这个文件提供了一些在你生成的 parser.c 文件中使用的基本 C 定义。
如果语法中存在歧义或局部歧义，Tree-sitter 将在解析器生成期间检测到它，并将退出并显示未解决的冲突错误消息。有关这些错误的更多信息，请参见下文。

test

对于添加到语法中的每条规则，您应该首先创建一个测试来描述语法树在解析该规则时的外观。 这些测试是使用解析器根文件夹中的 corpus/ 或 test/corpus/ 目录中特殊格式的文本文件编写的。

例如，您可能有一个名为 test/corpus/statements.txt 的文件，其中包含一系列如下条目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
==================
Return statements
==================

func x() int {
  return 1;
}

---

(source_file
  (function_definition
    (identifier)
    (parameter_list)
    (primitive_type)
    (block
      (return_statement (number)))))
  • 每个测试的名称写在仅包含=字符的两行之间。
    1
    2
    3
    ==================
    Return statements
    ==================
  • 然后编写输入源代码，后跟一行包含三个或更多-字符。
    1
    2
    3
    4
    5
    func x() int {
      return 1;
    }

    ---
  • 然后，预期的输出语法树被写成一个 S 表达式。 S 表达式中空格的确切位置无关紧要，但理想情况下，语法树应该是清晰的。请注意，S 表达式不显示 func、( 和 ; 等语法节点，它们在语法中表示为字符串和正则表达式。它只显示命名节点，如解析器使用页面所述。

预期的输出部分还可以选择显示与每个子节点关联的字段名称。要在测试中包含字段名称，请在 S 表达式中的节点本身之前写入节点的字段名称，后跟冒号：

1
2
3
4
5
6
7
(source_file
  (function_definition
    name: (identifier)
    parameters: (parameter_list)
    result: (primitive_type)
    body: (block
      (return_statement (number)))))

这些测试很重要。它们充当解析器的 API 文档，每次更改语法时都可以运行它们以验证所有内容是否仍然正确解析。

默认情况下，tree-sitter test 命令运行您的语料库或 test/corpus/ 文件夹中的所有测试。 要运行特定测试，您可以使用 -f 标志：
tree-sitter test -f 'Return statements'

建议在添加测试时要全面，尽量测试每种语言结构的所有排列。

parse

您可以使用 tree-sitter 解析在任意文件上运行解析器。这将打印生成的语法树，包括节点的范围和字段名称，如下所示：

1
2
3
4
5
6
7
8
9
(source_file [0, 0] - [3, 0]
  (function_declaration [0, 0] - [2, 1]
    name: (identifier [0, 5] - [0, 9])
    parameters: (parameter_list [0, 9] - [0, 11])
    result: (type_identifier [0, 12] - [0, 15])
    body: (block [0, 16] - [2, 1]
      (return_statement [1, 2] - [1, 10]
        (expression_list [1, 9] - [1, 10]
          (int_literal [1, 9] - [1, 10]))))))

您可以将任意数量的文件路径和 glob 模式传递给 tree-sitter 解析，它将解析所有给定的文件。如果发生任何解析错误，将以非零状态码退出。还可以使用 --quiet 标志阻止打印语法树。此外，--stat 标志打印出所有已处理文件的聚合解析成功/失败信息。这使得 tree-sitter parse 可检查大量文件是否正确解析：

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

highlight 高亮

您可以使用 tree-sitter highlight 在任意文件上运行语法突出显示。 这可以使用 ansi 转义码将颜色直接输出到您的终端，或者生成 HTML（使用了 --html 标志）。 有关详细信息，请参阅语法高亮。
You can run syntax highlighting on an arbitrary file using tree-sitter highlight. This can either output colors directly to your terminal using ansi escape codes, or produce HTML (if the –html flag is passed). For more information, see the syntax highlighting page.

The Grammar DSL

以下是一些内建方法 (built-in functions)，可以在grammar.js内定义规则。详细规则会在后面讲述。

The following is a complete list of built-in functions you can use in your grammar.js to define rules. Use-cases for some of these functions will be explained in more detail in later sections.

符号

$

每个语法规则，都被写作一个接收参数$的js函数。你可以通过$.identifier引用另一个规则。

Every grammar rule is written as a JavaScript function that takes a parameter conventionally called $. The syntax $.identifier is how you refer to another grammar symbol within a rule.

字符串和正则表达式

"" 或者 /REGEXP/

语法中的字符使用 JavaScript 字符串和正则表达式来描述。当然，Tree-sitter 在解析过程中并没有使用 JavaScript 的正则表达式引擎来解析这些正则表达式；它生成自己的正则表达式匹配逻辑作为每个解析器的一部分。正则表达式文字只是用作在语法中编写正则表达式的便捷方式。

The terminal symbols in a grammar are described using JavaScript strings and regular expressions. Of course during parsing, Tree-sitter does not actually use JavaScript’s regex engine to evaluate these regexes; it generates its own regex-matching logic as part of each parser. Regex literals are just used as a convenient way of writing regular expressions in your grammar.

按顺序排列

seq(rule1, rule2, ...)

此函数创建一个匹配任意数量的其他规则的规则，一个接一个。这类似于简单地以 EBNF 表示法将多个符号彼此相邻地书写。

This function creates a rule that matches any number of other rules, one after another. It is analogous to simply writing multiple symbols next to each other in EBNF notation.

多选一

choice(rule1, rule2, ...)

这会在rule1, rule2...里匹配一个，这和EBNF语法中的管道符(|)相同。

This function creates a rule that matches one of a set of possible rules. The order of the arguments does not matter. This is analogous to the | (pipe) operator in EBNF notation.

重复0次及以上

repeat(rule)

会匹配规则0次或以上，作用与EBNF语法中的{x}相同。

This function creates a rule that matches zero-or-more occurrences of a given rule. It is analogous to the {x} (curly brace) syntax in EBNF notation.

重复一次或多次

repeat1(rule)

匹配一次或更多。

This function creates a rule that matches one-or-more occurrences of a given rule. The previous repeat rule is implemented in terms of repeat1 but is included because it is very commonly used.

可选的（0次或1次）

optional(rule)

匹配0或1次，与[x]同。

This function creates a rule that matches zero or one occurrence of a given rule. It is analogous to the [x] (square bracket) syntax in EBNF notation.

优先级

prec(number, rule)

为规则rule设定优先级number。优先级将用于在解析器生成时解决 LR(1) 冲突。当两个规则重复匹配时，Tree-sitter将尝试通过匹配具有更高优先级的规则来解决冲突。所有规则的默认优先级为零。与Yacc语法中的优先级指令类似。

This function marks the given rule with a numerical precedence which will be used to resolve LR(1) Conflicts at parser-generation time. When two rules overlap in a way that represents either a true ambiguity or a local ambiguity given one token of lookahead, Tree-sitter will try to resolve the conflict by matching the rule with the higher precedence. The default precedence of all rules is zero. This works similarly to the precedence directives in Yacc grammars.

左优先级（优先从左匹配）

prec.left([number], rule)

将规则标记为左关联（并可选择应用number优先级）。当出现所有规则具有相同数值优先级的 LR(1) 冲突时，Tree-sitter将验证规则的关联性。如果存在左关联规则，则 Tree-sitter 将优先匹配较早结束（左边）的规则。与Yacc语法中的关联性指令类似。

This function marks the given rule as left-associative (and optionally applies a numerical precedence). When an LR(1) conflict arises in which all of the rules have the same numerical precedence, Tree-sitter will consult the rules’ associativity. If there is a left-associative rule, Tree-sitter will prefer matching a rule that ends earlier. This works similarly to associativity directives in Yacc grammars.

右优先级（从右匹配）

prec.right([number], rule)

这和prec.left类似，但是将优先匹配晚结束（右边）的规则。

This function is like prec.left, but it instructs Tree-sitter to prefer matching a rule that ends later.

动态优先级

prec.dynamic(number, rule)

类似于prec，但给定的数值优先级在运行时(runtime)应用，而不是在解析器生成(tree-sitter generate)时应用。这个方法，仅在使用语法中的冲突conflict属性，或者当存在真正的歧义时（多个规则正确匹配给定的代码片段），动态处理冲突时才有必要。在这种情况下，Tree-sitter会比较与每个规则关联的总动态优先级，并选择总和最高的一个。与Bison语法中的动态优先级指令类似。

This function is similar to prec, but the given numerical precedence is applied at runtime instead of at parser generation time. This is only necessary when handling a conflict dynamically using the conflicts field in the grammar, and when there is a genuine ambiguity: multiple rules correctly match a given piece of code. In that event, Tree-sitter compares the total dynamic precedence associated with each rule, and selects the one with the highest total. This is similar to dynamic precedence directives in Bison grammars.

标记

token(rule)

将给定规则标记为仅生成单个标记（token）。Tree-sitter的默认设置是将语法中的每个String或RegExp文字视为单独的标记。每个标记都由词法分析器单独匹配，并作为树中的叶节点返回。token函数允许您使用上述函数，让Tree-sitter将其视为单个标记(token)，（而不是作为单个正则表达式）来表达复杂的规则。

This function marks the given rule as producing only a single token. Tree-sitter’s default is to treat each String or RegExp literal in the grammar as a separate token. Each token is matched separately by the lexer and returned as its own leaf node in the tree. The token function allows you to express a complex rule using the functions described above (rather than as a single regular expression) but still have Tree-sitter treat it as a single token.

忽略空格

token.immediate(rule)

通常，每个标记之前的空格（以及任何其他额外内容，例如注释）是可选的。这个函数意味着只有在没有空格的情况下令牌才会匹配。
Usually, whitespace (and any other extras, such as comments) is optional before each token. This function means that the token will only match if there is no whitespace.

别名

alias(rule, name)

这个函数导致给定的规则在语法树中出现一个替代名称。如果 name 是一个符号，如在 alias($.foo, $.bar) 中，则别名规则将显示为名为 bar 的命名节点。 如果 name 是字符串文字，如 alias($.foo, ‘bar’)，则别名规则将显示为匿名节点，就好像该规则已被编写为简单字符串一样。

This function causes the given rule to appear with an alternative name in the syntax tree. If name is a symbol, as in alias($.foo, $.bar), then the aliased rule will appear as a named node called bar. And if name is a string literal, as in alias($.foo, ‘bar’), then the aliased rule will appear as an anonymous node, as if the rule had been written as the simple string.

字段

field(name, rule)

此函数将字段名称分配给与给定规则匹配的子节点。在生成的语法树中，您可以使用该字段名称来访问特定的子项。除了名称和规则字段之外，语法还有一些其他可选的公共字段会影响解析器的行为。

This function assigns a field name to the child node(s) matched by the given rule. In the resulting syntax tree, you can then use that field name to access specific children.
In addition to the name and rules fields, grammars have a few other optional public fields that influence the behavior of the parser.

其他可选配置

grammar.js内除了name（解析的语言的名称）和rules（规则表）属性，还有其他公开属性影响解析器行为。

In addition to the name and rules fields, grammars have a few other optional public fields that influence the behavior of the parser

extras

此属性包含一组可能出现在语言中任何地方的标记（token）。通常用于空格和注释。extras的默认值包含空格。如果要手动处理空格，请将extras: $ => []加入你的配置。

an array of tokens that may appear anywhere in the language. This is often used for whitespace and comments. The default value of extras is to accept whitespace. To control whitespace explicitly, specify extras: $ => [] in your grammar.

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.

conflicts

包含多组规则名称。conflicts内每个数组表示一组规则，这些规则涉及旨在存在于语法中的 LR(1) 冲突。当这些冲突在运行时发生时，Tree-sitter将使用GLR算法来探索所有可能的解释。如果多个解析最终成功，则Tree-sitter将选择其相应规则具有最高总动态优先级的子树。

an array of arrays of rule names. Each inner array represents a set of rules that’s involved in an LR(1) conflict that is intended to exist in the grammar. When these conflicts occur at runtime, Tree-sitter will use the GLR algorithm to explore all of the possible interpretations. If multiple parses end up succeeding, Tree-sitter will pick the subtree whose corresponding rule has the highest total dynamic precedence.

externals

可以由外部扫描器返回的令牌（token）名称数组。外部扫描器允许您编写在词法分析过程中运行的自定义 C 代码，以处理正则表达式无法描述的词法规则（例如 Python 的缩进标记）。

an array of token names which can be returned by an external scanner. External scanners allow you to write custom C code which runs during the lexing process in order to handle lexical rules (e.g. Python’s indentation tokens) that cannot be described by regular expressions.

word

为了关键字提取优化的目的，将匹配关键字的标记的名称。

the name of a token that will match keywords for the purpose of the keyword extraction optimization.

supertypes

隐藏规则名称的数组，在生成的节点类型文件中应被视为“超类型”。

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

举例

这里使用的Lua的规则来举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
module.exports = grammar({
    // 要解析的语言的名称
    name: 'lua',

    // 常用于空格和注释（此属性内的规则将被忽略）
    extras: $ => [
      $.comment,
      /[\s\n]/
    ],

    // 
    inline: $ => [
      $._statement
    ],

    conflicts: $ => [
      [$._prefix],
      [$._expression, $._variable_declarator],
      [$._expression, $.function_call_statement],
      [$.function_name, $.function_name_field]
    ],

    externals: $ => [
      $.comment,
      $.string
    ],

    rules: {
        nil: $ => 'nil',
        true: $ => 'true',
        false: $ => 'false',
    }
})

内置方法

例如以下规则会匹配Lua当中的table表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// `seq`代表按顺序匹配
table: $ => seq(
  // `{`和`}`是必须的
  '{',
  // `optional`代表规则`$._field_sequence`是可选的
  optional($._field_sequence),
  '}'
),
// `choice`从以下三个规则中选择一个
field: $ => choice(
  seq('[', $._expression, ']', '=', $._expression),
  seq($.identifier, '=', $._expression),
  $._expression
),
// `prec`会给规则设定优先级（这里是1，默认优先级为0）
_field_sequence: $ => prec(1, seq(
  $.field,
  repeat(seq($._field_sep, $.field)),
  optional($._field_sep)
)),
_field_sep: $ => choice(',', ';'),

规则table可以匹配以下源码（等）：

1
2
3
4
{}
{a}
{1,2,3}
{"1",a,2}

以下的例子会匹配for循环：

1
2
3
4
5
6
7
8
9
10
for_statement: $ => seq(
  'for',
  // 可以通过alias(r1, r2)，将for_loop_expression或while_loop_expression
  // 规则重命名为loop_expression
  alias($._loop_expression, $.loop_expression),
  'do',
  repeat($._statement),
  optional($.return_statement),
  'end'
),
1
2
3
4
5
6
-- for $.loop_expression do
for i=1,10 do
  -- 重复0次或以上$._statement
  print(i)\
-- end
end

绑定

以py-tree-sitter举例。

安装

pip3 install tree_sitter

初始化

选择你要解析的语言的解析器，你可以clone已经实现了的解析器或者使用上一节自己创建的解析器。

1
2
3
git clone https://github.com/tree-sitter/tree-sitter-go
git clone https://github.com/tree-sitter/tree-sitter-javascript
git clone https://github.com/tree-sitter/tree-sitter-python

使用 Language.build_library 方法将它们编译成可从 Python 使用的库。 如果自上次修改源代码后库已经编译，则此函数将立即返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
from tree_sitter import Language, Parser

Language.build_library(
  # Store the library in the `build` directory
  'build/my-languages.so',

  # Include one or more languages
  [
    'vendor/tree-sitter-go',
    'vendor/tree-sitter-javascript',
    'vendor/tree-sitter-python'
  ]
)

解析

创建一个解析器，并设定语言

1
2
parser = Parser()
parser.set_language(PY_LANGUAGE)

进行解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tree = parser.parse(bytes("""
def foo():
    if bar:
        baz()
""", "utf8"))
# 或者
src = bytes("""
def foo():
    if bar:
        baz()
""", "utf8")

def read_callable(byte_offset, point):
    return src[byte_offset:byte_offset+1]

tree = parser.parse(read_callable)

检查语法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
root_node = tree.root_node
assert root_node.type == 'module'
assert root_node.start_point == (1, 0)
assert root_node.end_point == (3, 13)

function_node = root_node.children[0]
assert function_node.type == 'function_definition'
assert function_node.child_by_field_name('name').type == 'identifier'

function_name_node = function_node.children[1]
assert function_name_node.type == 'identifier'
assert function_name_node.start_point == (1, 4)
assert function_name_node.end_point == (1, 7)

assert root_node.sexp() == "(module "
    "(function_definition "
        "name: (identifier) "
        "parameters: (parameters) "
        "body: (block "
            "(if_statement "
                "condition: (identifier) "
                "consequence: (block "
                    "(expression_statement (call "
                        "function: (identifier) "
                        "arguments: (argument_list))))))))"

使用遍历（walk）方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cursor = tree.walk()

assert cursor.node.type == 'module'

assert cursor.goto_first_child()
assert cursor.node.type == 'function_definition'

assert cursor.goto_first_child()
assert cursor.node.type == 'def'

# Returns `False` because the `def` node has no children
assert not cursor.goto_first_child()

assert cursor.goto_next_sibling()
assert cursor.node.type == 'identifier'

assert cursor.goto_next_sibling()
assert cursor.node.type == 'parameters'

assert cursor.goto_parent()
assert cursor.node.type == 'function_definition'