tree-sitter

tree-sitter 是一个 parser generator 和增量解析工具。其使用 LR(1) 算法对源码进行解析，因此保证了性能。

语法结构

grammar.js 中可以使用以下语法结构：

符号解释

符号	解释
字符串和 regex	每个字符串和 regex 都被视为一个完整的 token。其中 regex 符合 ECMA 标准，但是无法使用 lookargound 和 assert。
sequence: `seq(rule1, rule2, …)`	按顺序匹配一系列规则。
choice: `choice(rule1, rule2, …)`	匹配规则中的一个。规则的顺序并不重要
repeat: `repeat(rule)`	重复一个规则零次或多次
repeat1: `repeat1(rule)`	rule 至少出现一次。
优先级: `prec(number, rule)`	用于在生成解析器时解决 LR(1) 冲突。
左结合： `prec.left(rule)`	发生 LR(1) 冲突时选择更短的序列。
右结合： `prec.right(rule)`	发生 LR(1) 冲突时选择更长的序列。
立即 token： `token.immediate(rule)`	rule 必须紧跟在上一个 token 后面。中间不能掺杂空格或 `extras` 中的内容。
别名： `alias(rule, name)`	为 rule 创建一个别名。如果 name 是一个符号，则 rule 会成为 Named Node。
FieldName: `field(name, rule)`	为 rule 创建一个 field name，不影响 rule 的可见性。

字符串和 regex

每个字符串和 regex 都被视为一个完整的 token。其中 regex 符合 ECMA 标准，但是无法使用 lookargound 和 assert。

sequence: seq(rule1, rule2, …)

按顺序匹配一系列规则。

choice: choice(rule1, rule2, …)

匹配规则中的一个。规则的顺序并不重要

repeat: repeat(rule)

重复一个规则零次或多次

repeat1: repeat1(rule)

rule 至少出现一次。

优先级: prec(number, rule)

用于在生成解析器时解决 LR(1) 冲突。

左结合： prec.left(rule)

发生 LR(1) 冲突时选择更短的序列。

右结合： prec.right(rule)

发生 LR(1) 冲突时选择更长的序列。

立即 token： token.immediate(rule)

rule 必须紧跟在上一个 token 后面。中间不能掺杂空格或 extras 中的内容。

别名： alias(rule, name)

为 rule 创建一个别名。如果 name 是一个符号，则 rule 会成为 Named Node。

FieldName: field(name, rule)

为 rule 创建一个 field name，不影响 rule 的可见性。

词法优先级和解析优先级。LR(1) 用来代之解析优先级，prec 决定了在形成语法过程中出现冲突如何处理。但是除此之外还有另一种情况：

词法优先级代表了在形成 token 的过程中更倾向于形成哪个 token。例如有下面一种情况：

// this is a comment (1)
//@key (2)

解析两种 symbol 的方式如下：

comment: $ => seq('//', /[^\r\n]*/, /\r?\n/),
annotation: $ => seq('//', repeat($.anno)),
anno: $ => seq('@', /\w+/)

在实际解析的过程中会发现 comment 总是会覆盖掉 annotation 的匹配。这时就需要提升 annotation 的词法优先级：

anno: $ => seq(token(prec('@')), /\w+/)

在 LR 语法中，reduce 操作是指将一系列已扫描的、较低级别的语法符号组合成一个较高级别的语法符号的过程。

当分析栈的顶端产生足够多的符号后、且这些符号匹配某个产生式时，分析器就会执行 reduce 操作，弹出栈顶的符号，然后将产生式的左侧非终结符推入栈中，并且根据当前状态和新推入的非终结符跳转到一个新的状态。

执行 reduce 操作会利用 lookahead 符号。这个符号用来帮助分析器在产生式之间进行 reduce 操作。从而避免 shift-reduce 和 reduce-reduce 冲突。

在 reduce 过程中，出错的原因可能有以下集中：

语法错误。比如 seq 操作被错误的写为 choice 操作。从而导致分析器在 reduce 过程中失败。
语法导致的 reduce 失败代表性形式如下：

符号正常识别且 reduce。
符号在成功 reduce 一个符号后突然抛出错误。
reduce-reduce 冲突。在某些文法中，可能存在多个产生式，它们的右侧部分前缀相同。在这样的情况下，分析器可能不确定使用哪一个产生式进行 reduce 操作，从而引发冲突。例如，在左递归文法中，可能有多个产生式都可以匹配相同的输入序列。
shift-reduce 冲突发生在分析器不确定是应该继续读取下一个输入符号（shift 操作），还是应该使用已经读取的符号进行 reduce 的时候。这种冲突通常发生在文法不明确的情况下，尤其是在处理运算符优先级和结合性时。

在 tree-sitter 中，由于存在 prec 操作，因此经常出现的是第一种错误。