---
title: "How Tree-sitter Works: Parsing Code as You Type"
description: "Grammars, concrete syntax trees, GLR parsing, error recovery and queries, then how CocoIndex splits code into chunks on function and class boundaries."
published: 2026-11-05
last_updated: 2026-11-05
doc_version: "2026-11-05"
canonical: https://cocoindex.io/blogs/how-tree-sitter-works/
---
# How Tree-sitter Works: Parsing Code as You Type

> Grammars, concrete syntax trees, GLR parsing, error recovery and queries, then how CocoIndex splits code into chunks on function and class boundaries.

Published: 2026-11-05 · Canonical: https://cocoindex.io/blogs/how-tree-sitter-works/

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`](https://cocoindex.io/docs/ops/text/#recursivesplitter) to
split source files on function and class boundaries rather than arbitrary line
counts.

Here is the result first. Move `chunk_size` to see which classes and functions
stay in one chunk, then add two lines to a function to see which chunks need a
new embedding.

The rest of this post explains how that works: the grammar, the parser and the
syntax tree, then how CocoIndex turns the tree into chunks.

## What is Tree-sitter?

[Tree-sitter](https://tree-sitter.github.io/tree-sitter/), created by Max
Brunsfeld, is both a parser generator and a parsing library.

First, it is a parser generator. A grammar author writes 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 the rules into a `parser.c` file: a large generated table of
parse states. The host application compiles it once and links it in. This is why
installing a parser in an editor often needs a C compiler: the editor builds
`parser.c`, and `scanner.c` when the grammar has one, into a shared library.

Second, it is a parsing library with no runtime dependencies. It runs that parser to
turn source code into a tree whose nodes mirror the grammar, and after an edit it
updates the tree incrementally, reusing the structure the edit did not touch.
Given `def greet(name): ...`, it returns the tree in the last panel of the
diagram: a `function_definition` node whose children hold the name, the
parameters and the block.

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](https://cocoindex.io/docs/examples/index-codebase),
for example, statically links the grammars below:

## Concrete syntax tree vs. abstract syntax tree

The tree Tree-sitter produces is a [concrete syntax tree](https://en.wikipedia.org/wiki/Parse_tree)
(CST), also called a parse tree. The distinction from an abstract syntax tree
(AST) decides what tools can do with the output.

- **An AST** omits concrete syntax details that an analysis does not need, such as punctuation or comments.
- **A CST** (what Tree-sitter builds) retains grammar tokens such as parentheses, commas, and the `def` keyword. Nodes carry byte ranges and row/column positions. Ordinary whitespace is usually skipped rather than represented by a leaf.

Highlighters, formatters and chunkers use the byte ranges to map each node back
to the exact text in the original source.

Here is the CST for a small Python function:

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

The keyword `def`, the colon, and the parentheses (inside `parameters`) are all
real nodes. Tree-sitter calls the meaningful, addressable nodes "named" nodes
(`function_definition`, `identifier`, `block`) and the punctuation and keywords
"anonymous" nodes. A tool that needs AST-like structure walks only the named
nodes. A formatter, which needs punctuation and keywords, includes the anonymous
ones too.

## 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:

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

`tree-sitter generate` compiles this grammar into a set of state-machine
tables. At runtime the parser reads tokens left to right and, at
each step, follows the [LR parsing](https://en.wikipedia.org/wiki/LR_parser)
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.

A plain LR parser needs exactly one action for every state and next token, and
the grammars of real languages have places where one token of lookahead is not
enough to choose. Tree-sitter uses
[GLR parsing](https://en.wikipedia.org/wiki/GLR_parser) (Generalized LR, from
Masaru Tomita's work on natural-language parsing) for those places. When the
table says more than one action is valid, the parser forks: it pursues each
interpretation in parallel on a shared stack and discards the branches that fail
to reach a valid parse.

The grammar author still decides where that is allowed. `tree-sitter generate`
stops with an "Unresolved conflict" error unless each conflict is settled with
precedence (`prec`, `prec.left`, `prec.right`) or listed in the grammar's
[`conflicts`](https://tree-sitter.github.io/tree-sitter/creating-parsers/2-the-grammar-dsl.html)
field. Only the listed conflicts become GLR forks at runtime.

## How does it recover from syntax errors?

Code in an editor is often invalid while someone types: a bracket is unclosed, a
statement is half-finished, or an identifier is a prefix of the intended one. 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 encounters unrecognized text, it can represent that text with
`ERROR` nodes. It may also insert zero-width tokens marked `MISSING` to recover
and continue parsing. This often preserves useful structure around the broken
region, though recovery cannot guarantee the intended interpretation of the rest
of the file. In the example below (the real output of `tree-sitter-python`), a
missing colon breaks the middle function, and the functions on either side still
parse cleanly. A highlighter can still color them, and a chunker can still find
them. `node.has_error` and `node.is_missing` mark the broken regions, so a tool
can skip or flag them and keep the rest of the parse.

## What are queries?

Tree-sitter also has a small declarative query language for matching patterns
in a tree, written as
[S-expressions](https://tree-sitter.github.io/tree-sitter/using-parsers/queries/index.html).
A query describes a tree shape and captures the nodes of interest with
`@`-prefixed names:

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

Run against a file, this query returns 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 affects retrieval quality. 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. It takes the source text, a
target chunk size and a language, parses the text with Tree-sitter, and places
chunk boundaries on syntax nodes. The
language can be a name or a file extension, and a helper resolves it from a
filename:

```python
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.line, c.end.line, len(c.text))
```

`c.start` and `c.end` are `TextPosition` objects. Each holds a `byte_offset`, a
`char_offset`, and a 1-based `line` and `column`, so a search result can point
to the exact span in the original file.

The splitter works in two passes. The first walks the syntax tree from the root
and breaks the file into small pieces along node boundaries. Nodes with no
children, such as long strings, fall back to text separators.

The second pass treats chunking as an optimization over the whole file. Instead
of merging pieces greedily from left to right, it scores candidate sets of cuts
on syntax depth, line structure and chunk size, and it finds the lowest-cost set
with dynamic programming, in time linear in the file size for a fixed
`chunk_size`. Overlap is part of the same search. The cuts tend to fall between
functions and classes and at blank lines. The splitter would rather leave a
chunk a little under the minimum size than cut through a function; a chunk far
under the minimum still costs too much to choose.

The same search runs for all 39 bundled grammars, and `RecursiveSplitter`
exposes it as one `split()` call.

The demo at the top of this post runs these two passes on a small Python file
with a nested class.

If the language is unsupported or unspecified, or the parse fails, the splitter
skips Tree-sitter and treats the input as plain text: an unknown extension falls
back to regex separators instead of raising an error.

### What happens when you edit a function

Splitting from the top keeps a function whole when it fits, and it puts
every cut on a syntax-node boundary. The second property matters when a file
changes. CocoIndex does not re-chunk a subtree for this. The splitter parses the
whole file again (it does not pass an old tree to Tree-sitter) and splits the
new tree from the root. The incremental work happens one level up. In the
[codebase indexing example](https://cocoindex.io/blogs/index-codebase-v1), the
per-file function is memoized, so files that did not change are skipped and
only the edited file is parsed, split and embedded again. Inside that file, cuts
that sit on syntax nodes tend to stay where they were, so chunks away from the
edit often come out with the same text. The embedder's `embed` call is memoized
on its input text, so those chunks reuse their stored vectors, and only chunks
with new text go to the model. A fixed-size split does not have this property:
inserting two lines moves every cut after the edit, and every later chunk has
new text.

The boundaries can still move. The second pass chooses its cuts
for the file as a whole, so an edit that changes a function's size can move a
neighbor's boundary. In the demo at `chunk_size` 200, the edit grows
`remove_item` to 254 bytes, past the budget, so it is split, and the chunk that
holds `add_item` takes its first line: three of eight chunks get new text. At
`chunk_size` 300 and 400, the same edit changes one chunk, the one that holds
`remove_item`.

### Does syntax-aware chunking help retrieval?

[cAST (Zhang et al., 2025)](https://arxiv.org/abs/2506.15655), from Carnegie
Mellon University and Augment Code, evaluates a related approach: parse with
Tree-sitter, recursively split large nodes, and merge small siblings up to a
size budget. Against fixed-size chunks, the paper reports two headline gains:

- Recall@5 on RepoEval (whether the right code lands in the top five retrieved
  chunks) rises from 70.7 to 75.0 with the GIST-base retriever, a 4.3-point gain.
- Pass@1 on SWE-bench Lite (whether a generated patch fixes the issue on the
  first try) rises from 14.0 to 16.7 with Claude 3.7 Sonnet as the generator and
  CodeSage-small-v2 as the retriever, a 2.7-point gain (the abstract gives
  2.67).

These results come from cAST's pipelines. The paper does not benchmark
CocoIndex, and the gain depends on the retriever: with CodeSage-small-v2, RepoEval Recall@5 rises
only from 82.1 to 83.9.

Two findings apply to 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 with the CodeSage-small-v2
  retriever, removing the merge step dropped retrieval nDCG from 85.1 to 66.1.
  CocoIndex's second pass also groups adjacent pieces into chunks of up to
  `chunk_size`.
- **The budget unit.** 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.
  cAST reports that retrieval
  and generation peak with a maximum chunk size between 2,000 and 2,500
  characters in its setup.

## How Tree-sitter helps coding agents

A coding agent works inside a fixed context window, so most of its effort goes
into finding the right code before it reads or edits anything. Tree-sitter gives
the agent's tools a structural view of a repository:

- **Whole-unit retrieval.** Search returns a function or class with its
  signature, not a window that starts in the middle of a body.
- **File outlines.** A query for definitions lists every class and function in
  a file with its line range, so the agent opens only the part it needs instead
  of the whole file.
- **Structural search.** Queries match code by shape, such as every call to a
  function, which plain text search cannot express.
- **Exact locations.** Every node carries byte and line ranges, so a result
  points at the lines to edit, and `has_error` tells the agent whether its edit
  still parses.
- **Half-written code.** Error recovery keeps the tree usable while the agent or
  a person is in the middle of a change.

Tree-sitter parses one file at a time and keeps no index across the repository.
A repository changes on every save and every agent edit, and an index that lags
behind sends the agent to code that no longer exists. CocoIndex keeps that index
current: the pipeline parses and chunks with Tree-sitter, processes only the
files that changed, and reuses the embedding of every chunk whose text did not
change, as [the edit example above](#what-happens-when-you-edit-a-function)
shows.

[cocoindex-code](https://github.com/cocoindex-io/cocoindex-code) packages this
for coding agents. It is a local CLI (`ccc`) and MCP server for Claude Code,
Codex and Cursor that keeps an AST-chunked, incrementally updated semantic index
of a codebase. For many repositories on GitHub or GitLab,
[CocoIndex Code Plus](/cocoindex-code) also stores the definitions and
references of every symbol and a text index for grep, in your Postgres.

## Where this falls short

Syntax-aware parsing and chunking have limits:

- Tree-sitter returns syntax only. It does no name resolution, type
  inference, or cross-file linking. Editors such as Neovim and Helix get those
  from a language server (LSP) and run both side by side. 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. The cost grows with file size.
- A function larger than `chunk_size` has to be cut inside. A function that
  fits is kept whole in nearly every case, but the splitter does not guarantee
  it, and a class that fits can still be split across chunks.
- A node with no children that is still too large, such as a long string, is cut
  at regex separators inside it.
- `chunk_overlap` repeats text across neighboring chunks, which preserves
  continuity for retrieval but inflates the index.

## Where to go next

For the parser internals, read the [Tree-sitter documentation](https://tree-sitter.github.io/tree-sitter/)
and a grammar repository such as
[tree-sitter-python](https://github.com/tree-sitter/tree-sitter-python). For the
retrieval side, [cAST](https://arxiv.org/abs/2506.15655) benchmarks AST-based
chunking against fixed-size chunking. CocoIndex is open source at
[github.com/cocoindex-io/cocoindex](https://github.com/cocoindex-io/cocoindex).

To run this chunker on a real codebase, in a pipeline that embeds the chunks and
keeps the index current as files change, start with the tutorial:

## Sitemap

- [Blog index](https://cocoindex.io/blogs/)
- [Site index (llms.txt)](https://cocoindex.io/llms.txt)
- [Full blog corpus](https://cocoindex.io/llms-full.txt)
- [Markdown sitemap](https://cocoindex.io/sitemap.md)
- [XML sitemap](https://cocoindex.io/sitemap.xml)
- [RSS feed](https://cocoindex.io/blogs/rss.xml)