Let's Build Tree-sitter: How Your Editor Parses Code On Every Keystroke

For about thirty years, syntax highlighting worked like this: a pile of regular expressions, applied line by line, guessing. It is why a string containing a brace used to break the colours for the rest of the file, why a comment could swallow your function, and why “highlight the variable under the cursor” highlighted the same word inside an unrelated string three lines down.

The obvious fix is to actually parse the code. The reason nobody did it for so long is that real parsers have two properties that make them useless in an editor: they re-read the entire file for every change, and they give up on the first syntax error — which describes your file for most of the time you are typing in it.

Tree-sitter is the parser that fixed both. Let us build it.

What are we building, exactly?

Not a compiler front end. The output is different, and the difference matters.

A compiler builds an abstract syntax tree: punctuation is discarded, structure is kept, whitespace never existed. That is right for generating code and wrong for an editor, which needs to answer “what is at byte 4,102” and “which range should I highlight”.

Tree-sitter builds a concrete syntax tree instead. Every token is present, every node carries a byte range, and the whole file can be reconstructed from the tree.

function add(a, b) {
  return a + b;
}

Click through the nodes. Two features do most of the work.

Byte ranges on everything. Cursor position to node, and node back to a range to highlight, fold or select. This is the entire basis of “expand selection”, “go to enclosing block” and every structural editing command.

Field names. The identifier in name: and the one in parameters: are both identifier nodes; the field is what lets you ask for the function’s name without matching its arguments. Grammars declare these, and queries depend on them.

Requirement one: parse in the time between keystrokes

A person typing fast produces a keystroke every 80 milliseconds or so. Anything the editor does per keystroke has to finish well inside that, on a file that might be tens of thousands of lines, while the editor is also doing everything else.

Re-parsing from scratch will not do it. So do not.

The idea is straightforward once stated. When an edit arrives, you know its byte range. Nodes entirely before it are unaffected. Nodes entirely after it are unaffected except that their positions shift — and a tree that stores relative offsets does not even need to be told. Only nodes overlapping the edit are damaged.

So the parser walks the old tree, reuses every subtree it can as a pointer rather than a copy, and runs the real parsing work only over the damaged region. In practice an edit inside one function re-parses that function and nothing else, and the cost is a function of the size of the change rather than the size of the file.

That is the whole trick, and it is why it works on a hundred-thousand-line file.

Requirement two: never give up

Code in an editor is broken almost continuously. You have typed if (x and not yet the ). You are halfway through a function name. A parser that returns “syntax error” and nothing else means the highlighting flickers off on every second keystroke, which is exactly the behaviour the whole exercise was meant to remove.

Tree-sitter recovers. When it cannot match the grammar it inserts an ERROR node covering the region it could not understand, and carries on parsing after it. The result is a tree that is wrong in one place and correct everywhere else — try the third scenario in the figure above. The function keeps its name, the parameters keep being parameters, and the editor keeps working while you finish the thought.

It also inserts MISSING nodes: when the grammar requires a token that is not there, it pretends it is, records that it did, and continues. The tree then tells you precisely what you forgot, which is a much better error message than “unexpected end of input”.

How does the parsing actually work?

Tree-sitter uses GLR — generalised LR parsing.

A plain LR parser is a state machine with a stack, built from the grammar ahead of time. It is fast and it is deterministic, and it fails on grammars where the next token is not enough to decide what to do. Real programming languages are full of these. In JavaScript, a leading { might open a block or an object literal, and you cannot tell without reading on.

GLR handles the ambiguity by refusing to choose: at a conflict it forks the stack and pursues both interpretations in parallel. Whichever fork keeps matching survives; the other dies as soon as it hits a token it cannot accept. Because conflicts are rare and the forks die quickly, the common case runs at ordinary LR speed and only the genuinely ambiguous corners pay extra.

Two further details make it practical:

The lexer is external and context-aware. Some tokens cannot be recognised without knowing where you are — a regular expression versus a division sign in JavaScript, significant indentation in Python, a here-document in shell. Grammars can declare an external scanner in C for exactly these cases, which is the escape hatch that lets the generated parser stay simple.

Grammar conflicts are resolved by rule. Where two interpretations both survive to the end, tree-sitter picks by declared precedence and associativity, and by preferring the parse with fewer error nodes.

Requirement three: let other people build on it

A tree nobody can inspect is a tree nobody uses. Tree-sitter ships a query language: S- expressions matched against the tree, with named captures.

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

function add(a, b) {
  return a + b;
}

This is the part that changed editors, rather than just improving them. Syntax highlighting becomes a file of queries. So do code folding, indentation rules, the symbol outline, and structural search-and-replace. Adding a language to an editor means writing a grammar and a queries file, not patching the editor — which is why tree-sitter grammars exist for languages no editor vendor would ever have prioritised.

It is also why structural search works properly. (binary_expression left: (identifier) right: (identifier)) finds additions of two variables and cannot be fooled by the same characters inside a string, a comment, or a variable name that happens to contain them. Grep never had a chance at that.

What would we build, in order?

If you set out to write one of these — and the reason to do it is to understand it — this is the order that keeps you honest:

1. A grammar format and a parser generator. Rules in, LR tables out. Start with arithmetic expressions and stop when you have a conflict you have to think about.
2. The concrete tree. Every token, byte ranges, parent and sibling links. Get a cursor API right early — everything downstream is built on walking the tree.
3. GLR forking. Handle the first genuine ambiguity by splitting the stack instead of guessing. This is where the exercise stops being a toy.
4. Error recovery. ERROR and MISSING nodes, and a recovery strategy that resynchronises at a plausible boundary rather than at the end of the file.
5. Incremental re-parse. Take an edit range, mark the damaged nodes, reuse the rest by pointer. Measure it against full re-parse on a large file — this is the number that justifies the whole project.
6. Queries. Pattern matching over the tree with captures. Then write a highlighter with it and watch the previous five steps pay off at once.

Where it is used

Almost certainly in something you already run. Neovim’s built-in highlighting and structural text objects, Zed’s whole editing model, Helix, Emacs 29 and later, Atom originally — and outside editors, GitHub’s code navigation and symbol search, and a growing number of static analysis and codemod tools that would otherwise have needed a full compiler front end per language.

The bindings are C with a WebAssembly build, which is why it turns up in browser-based editors as readily as in native ones.

The short version

Tree-sitter is a parser built for a hostile environment: the file is broken, the edits never stop, and the answer is needed in the time between keystrokes. It gets there with three ideas — a concrete tree where every byte is addressable, GLR parsing that forks rather than guesses, and incremental re-parsing that makes the cost proportional to the edit rather than the file.

The lesson generalises past parsers. The reason the old approach was bad was not that regular expressions are bad; it is that they were the wrong data structure for the question being asked. Once the answer is a tree with byte ranges, highlighting, folding, navigation and search all stop being separate features and become queries.