Crafting a parser, part 7: resilient, incremental parsing
A batch compiler parses a file once and moves on. An editor parses the same file on every keystroke, while it is syntactically broken, and expects a tree back in under a millisecond. That changes the design — this is the IDE-grade end of parsing.
Lossless syntax trees
IDE parsers keep everything: whitespace, comments, even erroneous tokens, in a tree
where every node knows its full text range. rust-analyzer's rowan and Roslyn's red/green
trees are the canonical examples.
A green tree is immutable, deduplicated, and position-free — cheap to share across edits. A red tree overlays absolute offsets and parent pointers on demand. Edits rebuild only the green nodes that changed.
Error-resilient by construction
Resilient parsers don't have an error path — error handling is the path. Every node
may contain missing or extra tokens, so a half-typed let x = still yields a Let node
with a missing value, which autocomplete can use immediately.
Incremental reparsing
When a user types inside one function, you shouldn't reparse the file. Keep the old tree, find the smallest node spanning the edit, and reparse just that subtree — reusing untouched green nodes.
You don't need this on day one. Ship the batch parser from parts 1-6 first; reach for lossless and incremental only when you are building tooling, not a compiler.
Takeaways
- Editors need lossless trees that survive broken input on every keystroke.
- Make errors the normal path: missing and extra tokens live inside nodes.
- Incremental reparse touches only the edited subtree.