Tree-sitter

1. Parser
2. Query
3. Build
4. References

1. Parser

1.1. CLI

tree-sitter
- init
- generate
- parse OPTION FILE
  - -d TYPE, --debug TYPE type can be quiet, normal, and pretty (color coded)

1.2. Grammar

Grammer is defined in grammar.js file in the project root. It is used to generate parser.c in the src directory.

The file exports a dictionary that contains the grammar rules as anonymous functions.

{
    extras: [
        /\s/,
        $.comment,
    ],
    conflicts: [
        [$.A, $.B],
    ],
    rules: {
        source_file: $ => seq($.header, $.body),
    }
}

1.2.1. Token

token(LITERAL) is used to lex the next token for the lookahead. When there are multiple candidate lexems,

the longest token is matched first,
and then the first token is matched first.

Possible next tokens are restricted by the previous stack. So better separate each token by its function in the syntax.

1.2.2. Reduction Rule

The tokens are reduced according to the rules specified by anonymous function

Tree-sitter perform reduction only with the knowledge of the next token. It generate tree bottom up.

If you want to define something multiline without any delimiter, you probably want to reduce lines after they are reduced line by line.

Once tree sitter finds the first token in a sequence, it wants to continue it possibly ignoring tokens along the way.

seq
choice
repeat
repeat1
prec, prec.left, prec.right

Precedence is important when reduction generate a token. So use not within the choice but as a wrapper of rule.

1.2.3. Extra

If there exists character or token, including newline and space, that does not satisfy any rule, and it is in extra, it is free to attach to any parent node.

1.3. Algorithm

LR(1) parser

It stores the stack of subtrees along with the past states.

The current state determine which possiblities are considered next. Reduce, Shift, (Skip, Condense) are performed after the parser sees the next token generated in place by the lexer.

2. Query

3. Build

Tree-sitter has ABI versions with the most recent version being 15 (as of tree-sitter 0.26.5).

Emacs uses ABI 14 or 13, so it is required to build the parser with appropriate ABI version:

tree-sitter generate --abi 14
tree-sitter build

Tree-sitter uses cl.exe to build the parser.dll.