How to not write parsers

Posted on August 5, 2026
Writing parsers is tricky and cumbersome, and that's even with provided grammars. This post is about approaching parsing from a different angle.

This blogpost is written based on a presentation I gave, of which the slides can be found here.

I use helix as my editor of choice. It uses tree-sitter as the mechanism for highlighting text. I really like Haskell. Unfortunately, the tree-sitter grammar for .cabal files, got reverted from the Helix repository as it was still quite a bit WIP
There was a pre-existing grammar by Magnus Therning, and a PR by Ananda Umamil fixing the segfaults, this is what I used for quite some time. Then I wanted cabal.project too, which was enough motivation to do a revamp.
.

How to sit in trees

Tree-sitter is a parser-generator DSL. You write a grammar in JavaScript, it generates an incremental parser in C, and out comes a concrete syntax tree.
readFields :: ByteString -> Either ParseError [Field] -- Cabal
parse      :: Text       -> Tree                      -- tree-sitter

The first nice thing about tree-sitter parsers is that they’re total. They don’t fail if there were parsing errors. Instead it decorates the parse tree with ERROR or MISSING nodes.
library                        (library
  build-depends base >= 4.9 ~>   type: (section_type))
               ^ no colon      (ERROR (field_name) (identifier) ...)

The second thing that’s quite nice is how easy it is to attach semantics onto these parse trees. This is done through tree-sitter queries that pattern match against the parse tree to annotate and capture specific nodes. These captures can then be used by downstream consumers to fuel some feature, like isolating all symbols in a file for go-to-symbol-like functionality.
match :: Query -> Tree -> [Match]

This matching of queries and trees form a relation. One pattern can capture in many places, and one node can be involved in different query captures. The . in hs-source-dirs: ., for example, can match both a path capture and a plain string capture in a single token.

So the whole tree-sitter pipeline decomposes into a total parse, a relational match, and a fold that turns captures into arbitrary behavior, encompassing what users do.
Text to Tree to list of Match, then foldMap id to a lossless record and foldMap last to one capture per token
The pipeline.

Grammar and query, sitting in a tree

A grammar and its corresponding queries, is a point in a solution space of possible useful parsers. On one side we have a parser that parses the empty language, and on the other, all possible strings. The cabal parser we want is somewhere in between those two ends.
three boxes, an over-fit grammar on the left, the grammar I want in the middle, a permissive grammar on the right
The solution space.

I can phrase this as a search. Given constraints C1,…,CnC_1, \ldots, C_n, each a fold from Tree into some monoid MiM_i, and expected values eie_i over a fixture set XX, find gg such that

Ci(parseg  x)=ei(x)∀i,  ∀x∈X.C_i(\mathrm{parse}_g\; x) = e_i(x) \qquad \forall i,\; \forall x \in X.

The free variable gg is the pair (grammar, queries), since their definitions are tied
The expected values ei are technically also shifting with changing constraints. I can manually keep that in check though via diffs.
. Every time one of the grammar, or query, changes and all constraints are satisfied, we have a valid parser in our hands from the solution space. The next step is choosing the constraints carefully so they precisely correspond to what features we want the parser to have.

Picking my tree

check-queries. The first constraint (constraint and tests are interchangeable from here on) checks whether the patterns in every query are compatible with the generated parser. So something like (librari ...) is an invalid node type, as it should be library.

parse-corpus. While tree-sitter doesn’t fail on invalid parses, we do know for sure that the parse trees from our tests should contain no error nodes. This forms the second constraint, asserting that no tree has these ERROR or MISSING nodes, across a large corpus.

The corpus, I harvested from the cabal and haskell-language-server repositories, which between them carry a rich regression suite of tests including files that should parse successfully. This yielded 968 files, with a median length of 14 lines.

extract-golden. What exactly gets captured is quite blackboxey. A golden testsuite pins it down, enforcing the presence of certain captures along with their location and contents, given a small testset. The size here is deliberately small to ensure this is easy to review.

highlight-golden. Highlighting was my original use-case, so it’s only appropriate to also capture it as a test. We can enforce that symbols we expect to be highlighted, indeed are. Only one capture wins per token, as ultimately only a single color can be shown. As the query file here is the one that’ll do the actual highlighting job, it’s a better representation than the one used in extract-golden.

Searching through the forest

The above constraints make it so any changes to the grammar or queries, can be rendered and diffed. This makes it easy to build into a feedback loop usable by a coding agent
Coding agent output is bound to be wrong, some of it is useful though.
. The agent proposes a grammar or query edit, checks all four constraints. Green means done. Red forks and hints at the agent where a regression occurred.
a cycle from agent proposes to run all four tests, branching to read the diff when all pass, or to which side of grammars or queries to change, and loops back to do a next change.
The feedback loop.

This still requires intervention. There are an infinite number of valid parsers that pass all of the tests, yet isn’t the parser or query setup I’m looking for. The ideal setup is subjective
Though it is possible to imagine phrasing this as a metric, so it can be made objective. But then again, the choice of metric is probably still going to be subjective.
. That human step, reading the diff and testing out the grammar on a real file, is still necessary. Luckily, diffs are a bit better to review than complex regexes.

The result of this experiment is tree-sitter-haskell-contrib, which contains grammars for .cabal, cabal.project, and GHC’s Core, STG, and Cmm dumps.

Discussion links: Reddit, Lobste.rs