TECH Signal 395
How to not write parsers
↗
Illustration only Photo by Declan Sun on Unsplash
A developer demonstrates an alternative approach to writing parsers using tree-sitter, focusing on incremental parsing and relational queries for syntax-aware tooling.
Engineers building language tooling or editors can replace brittle, failure-prone parsers with total parsers that annotate errors in the syntax tree. The method shifts validation from runtime failures to compile-time constraints, reducing debugging overhead. Adopting this requires rethinking parser design as a search problem with testable invariants.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
Tree-sitter generates total parsers that annotate errors in the syntax tree instead of failing outright.
Queries pattern-match against the parse tree to capture nodes, enabling features like symbol isolation or syntax highlighting.
Parser correctness is framed as a search problem with constraints, validated via corpus tests and golden test suites.
THE READ
What elseif makes of it.
The event describes a shift from traditional parser design to an incremental, constraint-driven approach using tree-sitter. Traditional parsers often fail on invalid input, requiring extensive error handling. Tree-sitter parsers, by contrast, are total, they always produce a syntax tree, decorating invalid or missing nodes with `ERROR` or `MISSING` annotations. This changes how engineers handle parsing errors: instead of catching exceptions, they traverse a tree with explicit error markers. The cost is rewriting grammars in tree-sitter’s JavaScript DSL and adopting a new mental model for error recovery.
The core innovation is treating parser development as a search problem. The grammar and queries form a point in a solution space, bounded by constraints like 'no error nodes in valid files' or 'specific captures must match golden test cases.' These constraints are testable properties, not runtime behaviors. For example, a corpus of 968 files ensures the parser never emits `ERROR` nodes for valid input, while golden tests enforce that queries capture the right nodes. This turns parser development into an iterative feedback loop, where changes to grammar or queries are validated against constraints before integration.
The approach is particularly useful for tooling like editors or linters, where incremental parsing and syntax-aware features are critical. Tree-sitter’s relational queries allow pattern-matching against the syntax tree, enabling features like go-to-symbol or syntax highlighting. However, the method has limits: it assumes the grammar and queries can be expressed in tree-sitter’s DSL, and it requires a curated corpus and golden test suite to define correctness. The trade-off is between upfront effort in defining constraints and long-term maintainability of the parser.
The framing of parser development as a search problem with constraints is a departure from traditional parser generators. It prioritizes testability and incremental improvement over one-shot correctness. For engineers, this means parser development becomes more like writing property-based tests: defining invariants and refining the grammar until all constraints are satisfied. The cost is the overhead of maintaining a corpus and golden tests, but the benefit is a parser that evolves with the language it supports, rather than breaking on edge cases.
Written by elseif from the cluster below · checked for specifics the sources never containedTHE CLUSTER