How Tree-sitter Works: Parsing Code as You Type

Tree-sitter is an incremental parser. It is used for editor syntax highlighting, structural code search, and code-aware chunking in retrieval pipelines. CocoIndex uses it in its RecursiveSplitter to split source files on function and class boundaries rather than arbitrary line counts. We trace it from grammar to parser to incremental re-parse, then show how CocoIndex uses it for chunking.

What is Tree-sitter?

Tree-sitter, built by Max Brunsfeld, is the reference throughout. It is both a parser generator and a parsing library.

First, it is a parser generator. You write a grammar, the rules of a language’s syntax, in JavaScript. One rule might say “a function is the keyword def, then a name, then a parameter list, a colon, and a block.” Running tree-sitter generate turns every rule into a parser.c file: a big table of states, far too large to read by hand. You compile it once and embed it.

Second, it is a fast, dependency-free parsing library. It runs that parser to turn source code into a tree whose nodes mirror the grammar, and it updates the tree incrementally as you edit, doing work proportional to the change rather than re-reading the whole file. Feed it def greet(name): ... and you get the tree on the right of the diagram, with def, the name, the parameters, and the block each on their own node. (The Tree-sitter docs have the canonical description.)

Four design goals shaped the engineering:

Each grammar lives in its own repository and ships its generated parser as C source, so adding a language to a host application is a matter of compiling and linking that parser. CocoIndex’s text engine, for example, statically links the grammars below:

Concrete syntax tree vs. abstract syntax tree

The tree Tree-sitter produces is a concrete syntax tree (CST), also called a parse tree. The distinction from an abstract syntax tree (AST) matters for how you use the output.

• An AST (the kind a compiler builds) throws away everything that does not affect meaning: parentheses, commas, the def keyword, comments, whitespace.
• A CST (what Tree-sitter builds) keeps all of it. Every byte of the source file is covered by exactly one leaf, and every node carries its precise byte range and row/column position.

That last property is what lets a tool map back to the original text, which highlighters, formatters, and chunkers all need to do.

Here is the CST for a small Python function:

def greet(name):
    return f"hi {name}"

Notice that the keyword def, the parentheses, and the colon are all real nodes. Tree-sitter calls the meaningful, addressable nodes “named” nodes (function_definition, identifier, block) and the punctuation and keywords “anonymous” nodes. You can walk only the named nodes when you want AST-like structure, or all of them when you need to reconstruct text exactly.

How does the parser work?

A Tree-sitter grammar is a set of rules. Each rule names a syntactic construct and describes the sequences of tokens and sub-rules that form it. A trimmed fragment of the Python grammar looks like this:

function_definition: $ => seq(
  'def',
  field('name', $.identifier),
  field('parameters', $.parameters),
  ':',
  field('body', $._suite),
),

When you run tree-sitter generate, this grammar is compiled into a set of state-machine tables. At runtime the parser reads tokens left to right and, at each step, follows the classic LR parsing shift/reduce loop:

Four mechanisms do the work:

• Shift pushes the next token onto a stack.
• Reduce fires when the tokens on top of the stack complete a grammar rule: the parser pops them off and replaces them with a single node.
• Lexing runs in the same pass. Tree-sitter generates the lexer from the string and regex tokens in the grammar.
• External scanners cover what a regular lexer cannot. A grammar can supply a hand-written scanner in C for tokens like Python’s indentation or heredocs.

Plain LR parsers reject any grammar with unresolved shift/reduce conflicts, and the grammars of real languages are full of them. Tree-sitter instead uses GLR parsing (Generalized LR, from Masaru Tomita’s work on natural-language parsing). When the table says more than one action is valid, the parser forks: it pursues every interpretation in parallel on a shared stack and discards the branches that fail to reach a valid parse. That is how one engine handles the ambiguous grammars of real languages without the grammar author resolving every conflict by hand.

Why is it incremental?

An editor re-parses on every keystroke, so re-reading the whole file each time would be wasteful. Instead, you tell Tree-sitter what byte range changed, and it re-parses only the parts of the tree the edit could have affected, reusing every unchanged subtree from the previous parse. The cost of an incremental re-parse scales with the size of the edit and the affected region, not with the size of the file. Editing one line in a ten-thousand-line file touches a handful of nodes near that line and leaves the rest of the tree untouched.

Mechanically: you call tree.edit() with the byte offsets of the change, then parse again passing the old tree. Nodes whose byte ranges fall outside the edited region keep their identity and their children, so a tool watching the tree can diff old against new and update only what moved. For CocoIndex this is the same philosophy we apply at the pipeline level with incremental processing: do work proportional to what changed, not to the size of the corpus.

How does it recover from syntax errors?

While you are typing, code is usually not valid yet: a bracket is unclosed, a statement is half-finished, an identifier is a prefix of the one you mean. A parser that stopped at the first error would be useless in an editor, so Tree-sitter recovers and keeps parsing instead.

When the parser reaches a token it cannot shift or reduce, it does not abort. It inserts ERROR and MISSING nodes into the tree and resynchronizes so it can keep parsing the rest of the file. The result is a tree that stays structurally correct everywhere the source is correct. The damage is localized to the broken region. A highlighter can still color the rest of the file; a chunker can still find the function two definitions down. You can detect the broken regions by checking node.has_error or node.is_missing and decide how to handle them, rather than losing the entire parse.

What are queries?

Rather than walk the tree by hand, you can match patterns with Tree-sitter’s small declarative query language, written as S-expressions. A query describes a shape of tree you want to find and captures the nodes you care about with @-prefixed names:

(function_definition
  name: (identifier) @function.name
  parameters: (parameters) @function.params)

Run that against a file and you get back every function definition with its name and parameter list captured. This is the mechanism behind editor features built on Tree-sitter: syntax highlighting is a query that tags nodes with color classes (highlights.scm), code folding and structural selection are queries, and “go to symbol” is a query for definitions. Queries can also carry predicates (for example, match an identifier only if its text equals a constant), which keeps language-specific logic in declarative .scm files instead of host code.

How CocoIndex uses Tree-sitter to chunk code

How a file is split into chunks determines how well retrieval over it works. A fixed 1,000-character split cuts functions in half and separates a method from its class, leaving the embedding model fragments that mean little on their own. Splitting on the structure the parser already produces, the CST, avoids that.

CocoIndex’s RecursiveSplitter works this way. You give it the source text, a target chunk size, and a language; it parses with Tree-sitter and walks the resulting tree to find chunk boundaries that fall on real syntax nodes. The language can be a name or a file extension, and a helper resolves it from a filename:

from cocoindex.ops.text import RecursiveSplitter, detect_code_language

source = open("server.py").read()
language = detect_code_language(filename="server.py")  # -> "python"

splitter = RecursiveSplitter()
chunks = splitter.split(source, chunk_size=1000, chunk_overlap=300, language=language)

for c in chunks:
    print(c.start, c.end, len(c.text))

The algorithm is recursive descent over the tree, governed by size. It starts at the root and works downward:

Because every node carries its byte range, each chunk comes back with exact start and end positions, so a search result can point to the precise span in the original file. If the language is unsupported or unspecified, the splitter skips Tree-sitter entirely and treats the input as plain text. An unknown extension falls back to plain-text chunking instead of erroring, splitting on regex separators rather than syntax boundaries.

Why top-down

Top-down descent has two advantages over merging chunks up from tokens. First, it keeps each function or class whole instead of gluing fragments across boundaries. Second, its boundaries land on syntax-node boundaries, so editing one function re-chunks only that subtree and leaves its neighbors untouched.

That second property is what makes chunking ride on the same incremental machinery as the parser: stable boundaries mean a local edit causes a local re-chunk.

This pairs with incremental processing at the pipeline level: when one file in a repository changes, only that file is re-chunked and re-embedded, not the whole corpus.

Does syntax-aware chunking help retrieval?

cAST (Zhang et al., 2025), from CMU and Augment Code, measured this directly. It chunks code with the same recipe CocoIndex uses: parse with Tree-sitter, recursively split large nodes, and greedily merge small siblings up to a size budget. Against line- and character-based chunking, it improves Recall@5 on RepoEval (whether the right code lands in the top five retrieved chunks) by up to 4.3 points and Pass@1 on SWE-bench (whether a generated patch fixes the issue on the first try) by 2.67 points. The 4.3-point figure is the best case across the retrievers they tested; the others gained less.

Two findings shape how you set a splitter’s parameters:

• The merge step. Splitting without merging leaves tiny nodes (imports, single assignments) as their own thin chunks, which inflate the index and carry little context. In cAST’s ablation, removing the merge step dropped retrieval nDCG from 85.1 to 66.1. CocoIndex’s splitter runs the same merge, packing adjacent pieces back toward the target size.
• Budget by content, not lines. One line can hold a single brace or a 200-character expression, so a line budget drifts across files and languages. CocoIndex measures the budget in bytes; cAST counts non-whitespace characters. Either way, the budget should track real content. cAST found retrieval and generation peak with a budget around 2,000 to 2,500 characters.

Where this falls short

Syntax-aware parsing and chunking are not free wins everywhere:

• Tree-sitter gives you structure, not meaning. It does no name resolution, type inference, or cross-file linking, so a chunk can be syntactically whole and still miss the caller or the type definition it depends on.
• Each language is a separate grammar with its own maturity. Tokens a regular lexer cannot handle, like Python indentation or heredocs, rely on a hand-written C scanner, and a thin or lagging grammar yields a coarser tree.
• Keeping every token, with a byte range on every node, uses more memory than the pruned tree a compiler builds. That is fine for most indexing, but it adds up on very large files.
• The splitter respects boundaries only down to the smallest node that fits. A function larger than the budget, with no inner structure to descend into, falls back to regex separators inside it.
• chunk_overlap repeats text across neighboring chunks, which preserves continuity for retrieval but inflates the index.

Where to go next

If you want to see the chunker end to end, in a pipeline that indexes a codebase for retrieval and keeps the index live as files change, read Build Real-Time Codebase Indexing for AI Code Generation. For the parser internals, the Tree-sitter documentation is thorough and readable, and the per-language grammar repositories (for example tree-sitter-python) are a good way to see how a real grammar is written. For the retrieval side, cAST benchmarks AST-based chunking against line-based chunking and reports where the gains come from.

If CocoIndex’s code-aware chunking is useful to you, the project is open source at github.com/cocoindex-io/cocoindex.

CocoIndex

Fresh context for long-horizon agents.

Learn the concept → View on GitHub

About the author.

Linghua Jin Cofounder & CEO of CocoIndex · @linghuaj

CEO and cofounder of CocoIndex. Writes about incremental data infrastructure, agents, and the engineering decisions behind the engine.