2026年7月28日作者：Lei阅读 --

Tree-sitter 源码深读：增量解析器是怎样从 grammar.js 变成语法树的

从 grammar DSL、parse table 生成、C runtime、GLR stack、增量重解析和 query VM 读懂 tree-sitter 的实现原理。

很多人第一次认识 Tree-sitter，是因为编辑器高亮、代码折叠、symbol outline、代码搜索或者某个 coding agent 的“代码结构索引”。官方 README 对它的定位很短：它既是 parser generator，也是 incremental parsing library。真正值得拆开的地方在于：

Tree-sitter 不是一个“运行时读 grammar.js 的解释器”。

它是两套系统拼起来的：
生成阶段：把 grammar.js/grammar.json 编译成 parser.c 和 node-types.json。
运行阶段：C runtime 载入生成出来的 TSLanguage 表，边 lex、边移进归约、边复用旧树。

本文基于 tree-sitter/tree-sitter commit 4deef2d5ef0d2dc738289f50622211a24ff7d9a0 做源码解读。它的 workspace 版本是 0.27.0，源码采用 MIT License。重点不是安装教程，而是回答几个实现问题：

grammar.js 到底怎样变成 parser.c？
parse table 是怎样处理 shift/reduce、precedence、associativity 和显式 conflicts 的？
C runtime 解析时怎样从 token 变成 concrete syntax tree？
“增量解析”具体复用了什么，什么时候会放弃复用？
query 为什么不是文本 regex，而是一台跑在语法树上的 pattern VM？
对编辑器、代码智能和 agent 来说，这种设计为什么重要？

先给一张全局图：

flowchart LR
    A[grammar.js] --> B[dsl.js 执行 grammar 函数]
    B --> C[grammar.json]
    C --> D[parse_grammar: InputGrammar]
    D --> E[prepare grammar + node types]
    E --> F[build_tables]
    F --> G[parse table + lex table]
    G --> H[render_c_code]
    H --> I[src/parser.c + node-types.json]
    I --> J[tree_sitter_language 函数]
    J --> K[TSLanguage]
    K --> L[TSParser runtime]
    L --> M[TSTree / TSNode]
    M --> N[QueryCursor]

一句话总结：

Tree-sitter 的核心思路是：
把语言规则提前编译成紧凑的 C 数据表，
运行时只保留一个很小的通用解析器，
再用可编辑旧树和多版本 parse stack，把“每次重 parse 全文件”变成“尽量复用旧结构”。

1. 仓库结构：Rust 负责生成器，C 负责运行时

从 Cargo.toml 看，Tree-sitter 是一个 Rust workspace，默认成员是 crates/cli，成员包括 crates/generate、crates/highlight、crates/loader、crates/tags、crates/language 和 lib。

按职责拆开更清楚：

模块	主要路径	职责
CLI	`crates/cli/src/main.rs`	解析 `tree-sitter generate/parse/query/test/...` 命令
生成器	`crates/generate/src`	执行 grammar DSL、构造语法、建表、渲染 C
运行时	`lib/src/parser.c`, `lexer.c`, `stack.c`, `subtree.c`, `tree.c`	通用 C parser、lexer 输入、parse stack、subtree 存储和增量编辑
Query	`lib/src/query.c`	编译 query pattern，并在语法树上匹配 capture
Bindings	`lib/binding_rust`, `lib/binding_web`	Rust/Wasm/JS API 包装
Docs	`docs/src`	grammar DSL、parser API、query API 等说明

这套分层很关键。每个语言 grammar 生成出来的 parser.c 不是完整复制一套复杂 parser 算法，而是一份 TSLanguage 数据表加若干 lex 函数。真正的解析主循环在 lib/src/parser.c 里，是所有语言共用的。

2. CLI 入口：generate 最后会走到生成器

CLI 的总入口是 crates/cli/src/main.rs 的 run。它用 clap 组装 tree-sitter 命令，然后把 Generate 子命令分派到 generate options 的 run。

真正生成 parser 的核心函数在 generate_parser_in_directory。它干了几件很具体的事：

1. 找到 grammar.js 或 grammar.json。
2. 调 load_grammar_file，把 grammar.js 执行成 JSON，或者直接读 grammar.json。
3. 写出 src/grammar.json。
4. 调 parse_grammar，把 JSON 转成 InputGrammar。
5. 如果只生成 grammar/node types，就提前返回。
6. 调 generate_parser_for_grammar_with_opts。
7. 写出 src/parser.c、src/node-types.json 和 tree_sitter 运行时头文件。

这说明 grammar.js 的生命周期只在“生成阶段”。应用调用 parser 时不会运行 JavaScript DSL；应用拿到的是已经编译好的 C 代码和 TSLanguage。

3. grammar.js：JavaScript 只是 DSL，不是运行时依赖

生成器读 grammar 文件时，先走 load_grammar_file。逻辑非常直接：

扩展名是 .js   -> load_js_grammar_file
扩展名是 .json -> fs::read_to_string
其他           -> 报错

.js 分支的 load_js_grammar_file 默认启动 node，也支持 bun、deno，在启用 native runtime 时可以走 QuickJS。它把 CLI 版本号和 dsl.js 写进 JS 进程的 stdin，然后从 stdout 取最后一行 JSON，再 pretty print 成 grammar.json。

所以 grammar DSL 的本质是：

用 JavaScript 的函数调用表达 EBNF 风格规则，
执行完以后得到一份 JSON AST，
后续建表都在 Rust 里完成。

crates/generate/src/dsl.js 里的 grammar 会校验并归一化这些字段：

grammar 字段	作用
`name`	语言名，后面会影响 `tree_sitter_<name>()` 导出函数
`rules`	语法规则，每条规则是一个返回 rule expression 的函数
`extras`	空白、注释等可出现在任意位置的 token
`externals`	外部 scanner 产生的 token
`inline`	生成时内联掉的规则
`supertypes`	node-types 中的抽象父类
`precedences`	命名 precedence 顺序
`conflicts`	允许 runtime 用 GLR 探索的有意歧义
`reserved` / `word`	reserved words 和 keyword extraction

官方 grammar DSL 文档也强调，prec、prec.left、prec.right、prec.dynamic 分别服务于生成期冲突消解、结合性和运行期动态歧义选择；token 会把复杂终结规则压成一个 token；externals 则给缩进这类正则难以表达的词法规则留出口。

4. parse_grammar：JSON 进入 Rust 内部世界

生成器把 JS DSL 的输出交给 parse_grammar。它不是简单反序列化完事，而是把不同字段转换成内部结构：

extras         -> Vec<Rule>，且禁止空字符串 extra
externals      -> Vec<Rule>
precedences    -> Vec<Vec<PrecedenceEntry>>
rules          -> Vec<Variable>
reserved       -> Vec<ReservedWordContext>
conflicts      -> expected_conflicts
inline         -> variables_to_inline
supertypes     -> supertype_symbols

最后构造 InputGrammar 并调用 .normalize(diagnostics)。这一步之后，生成器已经不再关心用户原始的 JavaScript 写法，而是面对一份结构化语法对象。

收口函数是 generate_parser_for_grammar_with_opts。它的形状很能说明生成器的分层：

InputGrammar
  -> generate_node_types_from_grammar
     得到 syntax_grammar、lexical_grammar、inlines、aliases、variable_info
  -> build_tables
     得到 parse table、lex table、关键字和外部 scanner 状态
  -> render_c_code
     渲染成 parser.c

换句话说，Tree-sitter 会把“语法规则”拆成两份互相配合的产物：

syntax grammar：非终结符、产生式、字段、alias、precedence、conflicts。
lexical grammar：终结符和 token 识别逻辑。

这种拆分也是 Tree-sitter 能把 lexer 和 parser 紧密耦合的前提。运行时不是先把整份文件 token 化完再 parse，而是在 parse state 需要某类 token 时按当前 lex mode 读取。

5. build_tables：把 grammar 编译成状态机

build_tables 是建表总控。它的主线是：

ParseItemSetBuilder::new
get_following_tokens
build_parse_table
TokenConflictMap / CoincidentTokenIndex / identify_keywords
populate_error_state
populate_used_symbols
minimize_parse_table
build_lex_table
populate_external_lex_states
mark_fragile_tokens

这里有两个值得注意的设计。

第一，Tree-sitter 的 parse table 和 lex table 不是完全独立的。identify_keywords、token_conflict_map、coincident_token_index 都说明生成器会根据 parse table 反推词法歧义和 keyword 优化。

第二，建完表还会进入 minimize_parse_table，按优化等级合并兼容状态、移除 unit reductions、移除无用状态，并按状态大小重排。这不是理论上“构造一张表”就结束，而是要让生成出来的 C 数据足够小、足够快。

6. ParseTableBuilder：冲突不是异常，而是一等公民

parse table 的核心构造器是 ParseTableBuilder.build。

它先固定两个特殊状态：

state 0: error state
state 1: starting state，包含 ParseItem::start()，lookahead 是 EOF

然后为 non-terminal extras 建特殊状态，再不断从 parse_state_queue 取出状态，对 item set 做 transitive closure，并调用 add_actions 写入 shift/reduce/goto 动作。

add_actions 是最有信息量的函数之一：

未完成 item:
  读取 next symbol
  next symbol 是 terminal -> terminal successor
  next symbol 是 non-terminal -> nonterminal successor
  后续 successor item set 变成新 parse state

已完成 item:
  augmented item -> Accept
  普通 item -> Reduce { symbol, child_count, dynamic_precedence, production_id }
  按 lookahead 插入 action list

如果同一个 lookahead 下出现多个 action，Tree-sitter 不会立刻失败。它先在 add_actions 里按 precedence 消掉明显低优先级的 reduce，再把剩下的冲突交给 handle_conflict。

handle_conflict 的策略可以概括成四层：

1. 如果是 repeat 辅助规则引入的有意歧义，保留多动作，并标记 SHIFT 为 repetition。
2. 如果 SHIFT 与 REDUCE precedence 不同，保留高 precedence 的解释。
3. 如果 precedence 相同，按 left/right associativity 决定 reduce 或 shift。
4. 如果仍有多个解释：
   - grammar 的 expected_conflicts 包含它 -> 允许 runtime 用多版本 stack 探索
   - 否则生成 ConflictError，并给出可选解决建议

这也是为什么 Tree-sitter grammar 里的 conflicts 不是“把错误压下去”的开关。它表达的是：这里确实存在局部无法靠一个 lookahead 静态决定的解释，生成器应允许运行时保留多个 parse stack version，最后再按动态 precedence 和 error cost 选择。

7. render_c_code：把状态机变成 TSLanguage

表建好后，render_c_code 创建 Generator 并调用 generate。

Generator.generate 的顺序很像一份 parser.c 文件的目录：

header / includes / pragmas
symbol enum
symbol names
symbol metadata
field names / field sequences
alias sequences
supertype map
lex functions
large character sets
lex modes
parse table
external scanner glue
parser export

parse table 渲染在 add_parse_table。它会生成两种表示：

ts_parse_table[LARGE_STATE_COUNT][SYMBOL_COUNT]：大状态用二维数组直接查。
ts_small_parse_table 和 ts_small_parse_table_map：小状态把相同 action 的 symbol 分组，减少重复。

最后 add_parser_export 生成 tree_sitter_<language>()。这个函数返回一份静态 TSLanguage，里面挂着：

parse_table
small_parse_table
parse_actions
symbol_names
symbol_metadata
field maps
alias maps
lex_modes
lex_fn
keyword_lex_fn
external_scanner
primary_state_ids
metadata

运行时 parser 的输入不是 grammar 原文，而是这份 TSLanguage。这就是 Tree-sitter 能把多语言支持做成“通用 runtime + 每种语言一份表”的原因。

8. 运行时主循环：ts_parser_parse 是所有语言共用的引擎

运行时入口是 ts_parser_parse。官方 basic parsing 文档也把它作为通用入口：调用方可以传入自定义 TSInput.read，从 rope、piece table 或其他文本结构按 byte offset 读取 chunk。

源码主线可以压成这样：

ts_parser_parse(parser, old_tree, input):
  检查 language 和 input.read
  如果是 wasm language，启动 wasm store
  设置 lexer input
  如果有 outstanding parse，恢复
  否则创建 external scanner

  如果传入 old_tree:
    retain old root
    计算 included range differences
    reusable_node_reset(old root)
  否则:
    reusable_node_clear()

  do:
    遍历每个 stack version
      while version active:
        ts_parser__advance(version, allow_node_reuse)
    ts_parser__condense_stack()
    如果 finished_tree 优于所有未完成版本，结束
    推进 included_range_difference_index
  while 还有 stack version

  balance subtree
  ts_tree_new(...)
  ts_parser_reset()

这里的关键词有三个：old_tree、stack version、finished_tree。

old_tree 用于增量复用。
stack version 用于处理冲突、恢复和多解释探索。
finished_tree 是当前最优完成结果；如果它的 error cost 已经低于所有在跑版本，就可以提前收束。

9. advance：先复用旧树，再缓存 token，最后才重新 lex

真正推动解析一步的是 ts_parser__advance。它的优先级非常能体现“增量”：

1. 如果允许 node reuse，先 ts_parser__reuse_node。
2. 如果没有可复用旧节点，再尝试 ts_parser__get_cached_token。
3. 如果还没有 lookahead，才 ts_parser__lex。
4. 根据当前 state + lookahead 查 table entry。
5. 遍历 action list：
   - Shift: push lookahead，结束这一拍
   - Reduce: pop children，建 parent，继续用同一个 lookahead 推进
   - Accept: 记录 finished tree
   - Recover: 进入错误恢复
6. 如果当前 lookahead 无效：
   - keyword 可以降级成 word token
   - reused subtree 不合法就 breakdown top of stack
   - 否则 pause 当前 stack version，等待其他版本或恢复

一个细节很重要：REDUCE 不一定消费 lookahead。它会创建新父节点，然后继续用同一个 lookahead 查新状态。这就是 LR parser 的基本节奏。SHIFT 才真正把 lookahead 推进到栈上。

ts_parser__shift 很短：必要时修改 extra 标记，把 subtree push 到 stack，并记录 external token。

ts_parser__reduce 更有意思。它会从某个 stack version pop 出 count 个 subtree，构造 parent subtree，再 push 回去。如果多个 stack path 曾经合并，pop 会产生多组 children；Tree-sitter 会选择更优 children，释放其余 subtree array。reduce 完还会尝试把新 version merge 回已有 version。

这就是 Tree-sitter runtime 的一个核心能力：

同一份输入可以暂时保留多个解释，
但每轮都会按错误代价、动态优先级和可合并状态主动压缩。

它不是无限展开的 GLR，而是带工程约束的多版本栈。

10. 增量解析：旧树先 edit，再按可复用节点前进

官方 advanced parsing 文档把编辑流程讲成两步：

1. 调 ts_tree_edit，把旧树节点范围调整到新文本坐标。
2. 再调 ts_parser_parse(parser, old_tree, input)，生成一棵和旧树共享结构的新树。

源码正好对应这两步。

ts_tree_edit 会先编辑 included ranges，再调 ts_subtree_edit 更新 root subtree。也就是说旧树不是原封不动传入 parse，而是先把 byte 和 point 坐标同步到新文本。

然后 ts_parser_parse 在看到 old_tree 时：

ts_subtree_retain(old_tree->root)
self->old_tree = old_tree->root
ts_range_array_get_changed_ranges(...)
reusable_node_reset(&self->reusable_node, old_tree->root)

reusable_node_reset 有一个很直接的注释：不要复用 root node，因为 root 在 accept 时会被加 EOF child 和 extra children，有非标准内部结构。它会先 descend 到 root 的第一个可复用子节点。

每次成功复用一个节点后，reusable_node_advance 会按字节偏移和 child index 移动到下一个候选 subtree。这个结构像一只在旧树上做 DFS 的游标：新 parser 每到一个位置，就问旧树“这里有没有一整块 subtree 可以直接搬过来”。

但复用不是盲目的。ts_parser__advance 里有一段很关键的 fallback：

如果当前 lookahead 无效，
且 stack 顶部是从旧树复用来的 subtree，
就 breakdown top of stack，把这个大 subtree 拆回 children，
然后重新 lex/parse。

这解释了增量解析的边界：Tree-sitter 不是简单相信旧树，而是先乐观复用，一旦 parse table 证明这个 subtree 在当前位置不合法，就把它打散回更小粒度。

11. changed ranges：比较的是语法结构，不只是文本 diff

解析完成后，用户常常还要知道“哪些范围的语法结构变了”。入口是 ts_tree_get_changed_ranges。它创建两只 tree cursor，计算 included range differences，然后调用 ts_subtree_get_changed_ranges。

ts_subtree_get_changed_ranges 的核心是两个 iterator 并排走：

IteratorMatches:
  两棵 subtree 明确相同，直接跳到 subtree end。

IteratorMayDiffer:
  两棵 subtree 可能内部不同，下降到 child 继续比较。

IteratorDiffers:
  记录当前 position 到 next_position 为 changed range。

它还会把 included range 变化考虑进去。也就是说 changed ranges 不是普通文本 diff，而是“旧语法树和新语法树在可见结构上哪里不一样”。这对编辑器很关键：高亮、折叠、diagnostics、符号索引可以只刷新受影响范围。

12. 错误恢复：语法树必须在坏代码上也有用

README 里提到 Tree-sitter 的目标之一是即使有语法错误也要给出有用结果。运行时里这体现在两类节点：

ERROR：无法识别或无法归约的文本。
MISSING：解析器为了恢复而插入的零宽缺失 token。

query 文档也说明，(ERROR) 和 (MISSING) 都可以被查询。这不是附加功能，而是编辑器场景的硬需求：用户敲代码时绝大多数中间状态都不是完整合法程序。如果 parser 必须等代码合法才能产出树，高亮和结构功能就会频繁闪断。

源码层面，ts_parser__advance 在当前 lookahead 无效时会先尝试 keyword 降级、breakdown reused subtree，再把当前 stack version pause。后续如果所有版本都无法前进，就进入 recover。多版本 stack 和 error cost 的存在，就是为了在坏输入上选出“最不坏”的树。

13. Query：跑在语法树上的 pattern VM

很多上层工具真正用 Tree-sitter，不是为了拿整棵树，而是为了 query：

(function_declaration
  name: (identifier) @function.name)

源码里 query 的编译入口是 ts_query__parse_pattern。这个函数很长，因为 query 语言支持很多结构：

query 语法	编译成什么
`(node child...)`	一串带 depth 的 `QueryStep`
`field: (node)`	step 上的 field id 约束
`!field`	negated field assertion
`@capture`	capture id 写入 step
`[...]`	alternative，通过 `alternative_index` 串起来
`+`, `*`, `?`	repeat/pass-through/skip alternative
`.` anchor	immediate / last-child 约束
`#predicate?`	pattern predicate
`supertype/subtype`	supertype_symbol + subtype symbol
`"anonymous"`	匿名 token symbol
`(MISSING ...)`	missing node 约束

这一步完成后，query 不再是一段字符串，而是一组可执行的 step、capture、predicate、pattern metadata。

运行时取 capture 的入口是 ts_query_cursor_next_capture。它的目标不是“找到一个就返回”，而是保证 capture 按源码顺序返回。因为不同 pattern 可以重叠，较晚发现的 match 可能包含更早的 capture。

所以它维护两类状态：

states：还在匹配中的 query state。
finished_states：已完成 match，用 min-heap 管 earliest capture。

取 capture 时，它会比较“未完成 match 中最早可能 capture”和“已完成 match 中最早 capture”。只有当某个已完成 capture 明确排在所有未完成候选之前，才安全返回。

捕获动作本身在 ts_query_cursor__capture。它先通过 ts_query_cursor__prepare_to_capture 获取 capture list；如果 capture list pool 用完，会放弃最早的 in-progress state 并复用其 list，同时标记 did_exceed_match_limit。

这里也能看出 Tree-sitter 的工程取舍：query VM 要支持复杂模式，但不能让一个恶意或过宽的 query 把内存无限撑开。

14. 为什么它适合代码智能和 Agent

对编辑器来说，Tree-sitter 的价值很直观：

每次按键后快速给出一棵尽量正确的 CST，
并且告诉上层哪些结构范围变了。

对代码智能和 agent 来说，价值稍微隐蔽一些：

稳定节点类型：function_declaration、call_expression、identifier、field name 等比纯文本 regex 更稳定。
跨语言统一 API：不同语言的 grammar 不同，但 parser runtime、query API 和 node traversal API 统一。
局部更新：索引器可以利用 changed ranges 或文件级增量策略，减少重复解析。
容忍半成品代码：agent 修改文件中途，代码经常不合法；Tree-sitter 仍能给出可用结构。
结构查询便宜：query 在 AST/CST 上匹配，比每次让 LLM 读整文件猜结构更可靠。

这也是为什么很多 code graph、code search、editor tooling、highlight engine 会把 Tree-sitter 当底座。它提供的不是完整语义理解，而是一层足够快、足够稳的语法事实。

15. 但它不是语义分析器

Tree-sitter 的边界也要说清楚。

它擅长回答：

这个范围是什么语法节点？
这个函数声明的 name field 在哪里？
这里有没有 call_expression？
两个 parse 版本哪些结构范围变了？
query pattern 命中了哪些 capture？

它不直接回答：

这个 symbol 绑定到哪个定义？
这个 import 解析到哪个包？
这个方法调用的接收者类型是什么？
这个变量在运行时可能是什么值？
跨文件 rename 会影响哪些地方？

这些需要 LSP、类型系统、构建系统、包解析、数据流分析或更上层的 code graph。Tree-sitter 给上层提供高质量语法材料，但不会替代完整编译器前端。

还有几个工程成本：

grammar 质量决定树质量。冲突、外部 scanner、keyword 提取都需要维护。
parser.c 是生成产物，调试时要回到 grammar 和生成器理解来源。
query 很强，但过宽 query 会产生大量状态，需要 match limit 保护。
多语言嵌入依赖应用层用 included ranges 组织，不是 runtime 自动理解 HTML 里所有脚本语言。

16. 把主线压成一段 mental model

最后把 Tree-sitter 的实现原理压缩成一段：

生成阶段：
grammar.js 通过 dsl.js 执行成 grammar.json。
Rust 生成器把 JSON 归一化成 InputGrammar，
拆成 syntax grammar 和 lexical grammar，
构造 parse table / lex table，
处理 precedence、associativity、conflicts、extras、keywords、external scanner，
再渲染成 parser.c 里的 TSLanguage 数据表。

运行阶段：
TSParser 接收 TSLanguage 和 TSInput。
每一拍先尝试复用 old_tree 的 subtree，
不行再用 cached token，
最后才 lex 新 token。
parser 根据当前 state 和 lookahead 查 action list，
shift 推 token，reduce 造父节点，
冲突和恢复通过多版本 stack 探索，
最后选出 error cost 最低的 finished tree。

Query 阶段：
query 字符串先编译成 QueryStep 和 predicate metadata，
QueryCursor 在语法树上维护 in-progress/finished states，
按源码顺序吐出 capture。

Tree-sitter 最厉害的地方，不是发明了某个单点算法，而是把“parser generator、增量 tree reuse、错误恢复、query VM、跨语言绑定”压进了一套工程上可嵌入的边界里：生成器可以复杂，运行时必须小而稳；grammar 可以由每种语言维护，上层工具只面对统一语法树和 query API。

这正是它能从编辑器高亮一路长到代码知识图谱和 coding agent 基础设施里的原因。