Parsing
A breadth-first survey of parsing — from the classical computer-science fundamentals (formal-language theory and the LL/LR/Earley/PEG algorithm families), through the modern functional-programming designs (parser combinators), to the high-performance, low-level data-parallel and SIMD techniques used in C, C++, Rust, and Zig, and the incremental, error-resilient parsers behind today's editors. The goal is a grounded map of the state of the art across language ecosystems, to inform an allocation-conscious (@nogc/@safe) parsing direction for Sparkles — the repo already hand-parses version schemes (sparkles.versions.parsing), CLI arguments (sparkles.core_cli.args), and terminal VT sequences (sparkles:ghostty), so the design space below is directly relevant.
This survey answers seven questions:
- What are the classical results? The Chomsky hierarchy, the automata that recognize each level, and the decidability/complexity walls that decide which parsing algorithms are even possible. See formal-languages and the theory subtree.
- How do the deterministic algorithm families work? Top-down (recursive descent, LL(k), ALL(*)), bottom-up (LR/SLR/LALR/canonical-LR, GLR), and the expression-parsing engines (operator-precedence, Pratt). See top-down, bottom-up, and pratt-precedence.
- How do you parse any grammar? General context-free parsing — Earley, CYK, GLL — and the derivative-based family. See general-parsing and derivatives.
- What is the PEG/packrat model, and why did it become the default for new tooling? See peg-packrat.
- How do real ecosystems package these ideas? Generators (ANTLR, Bison, Menhir, pest), functional combinators (Parsec, nom, chumsky), data-parallel SIMD (simdjson), and incremental/IDE-grade engines (tree-sitter). See the master catalog.
- What does the field agree on, and where does it split? The deterministic-vs- general, batch-vs-incremental, and throughput-vs-recovery trade-offs, and where a Sparkles parser would sit. See the comparison.
- How do tools turn a parse into colors? The syntax-highlighting model landscape — the line-local TextMate scope machine (syntect, Shiki, consumed by bat), CST queries over a recovered tree, and the lexer-as-code family (Pygments) — plus language detection, theme formats, the window problem, and the semantic tier. See the syntax-highlighting synthesis.
NOTE
Scope: wave 1 (foundation + flagship) + three wave-2 clusters + the wave-4/5 syntax-highlighting cluster. Wave 1 established the theory subtree, the shared vocabulary, and nine flagship systems. Wave 2 added three clusters: the incremental / query-based one (incremental theory + rust-analyzer, Roslyn, Lezer, rustc queries, joining tree-sitter); the SIMD / high-performance one (simd-json, sonic-rs, yyjson (no-SIMD counterpoint), RapidJSON, Hyperscan, the Zig tokenizer, joining simdjson); and the parser-combinator one (winnow, flatparse, combine, Angstrom, FParsec, joining wave-1's Parsec/nom/chumsky). Wave 3 added the D landscape; waves 4–5 add the syntax-highlighting cluster — the engines (syntect, bat, tree-sitter-highlight, Shiki, Pygments, Chroma, highlight.js, @lezer/highlight), the detection layer (Linguist), the editor/IDE consumption patterns (Helix, IntelliJ Platform, Vim & Emacs), and the semantic tier (LSP semantic tokens), synthesized in syntax-highlighting — the evidence base for the planned sparkles:syntax library. Still deferred: generators (LALRPOP, Lark/PLY, Peggy, Ragel/re2c) and a few second-tier Scala/JVM combinators (FastParse, parsley, cats-parse). Rows a future deep-dive will add are noted, not silently omitted.
Last reviewed: July 11, 2026
Foundations (theory)
The classical results, each developed in its own deep-dive. Start with the concepts glossary for the shared vocabulary, then the theory umbrella for the algorithmic spine.
| Topic | What it pins down | Canonical results | Link |
|---|---|---|---|
| Concepts & vocabulary | The operational glossary every deep-dive links to; the parser-landscape table | — | concepts |
| Formal languages & the parse problem | The Chomsky hierarchy, grammar↔automaton pairing, decidability & the cubic complexity wall | Chomsky 1956; Valiant 1975 / Lee 2002 (BMM bound); ambiguity undecidable | formal-languages |
| Top-down parsing | Recursive descent, FIRST/FOLLOW & LL(1), LL(k)/strong-LL, LL(*)/ALL(*) | Lewis & Stearns 1968; Rosenkrantz & Stearns 1970; Parr et al. 2011/2014 | top-down |
| Bottom-up parsing | Shift-reduce, the LR(0) automaton, SLR/LALR/canonical-LR, GLR | Knuth 1965; DeRemer & Pennello 1982; Tomita 1985 (book: Kluwer, 1986) | bottom-up |
| General CF parsing | Parsing every CFG (ambiguous, left-recursive) — Earley, CYK, GLL, SPPFs | Earley 1970; CYK; Leo 1991; Scott & Johnstone (GLL); Marpa | general-parsing |
| PEG & packrat | Recognition-based grammars, ordered choice, linear-time memoization, the space cost | Ford 2002 (packrat) & 2004 (PEG); Warth 2008 (left recursion) | peg-packrat |
| Operator-precedence & Pratt | The linear-time expression engine recursive descent drops in | Floyd 1963; Pratt 1973; Crockford 2007; matklad | pratt-precedence |
| Parsing with derivatives | One self-similar operation from regex→DFA up to full CFG parsing | Brzozowski 1964; Owens et al. 2009; Might et al. 2011; Adams et al. 2016 | derivatives |
Systems master catalog
One row per surveyed system. Algorithm / grammar class is the formalism it implements (cross-linked to the theory deep-dive that develops it). Error recovery classifies the deepest tier reached: fail-fast (stop at the first error) → panic-mode (skip to a synchronizing token and resume) → diagnostic (good positioned messages, still one error) → recovering (produce a partial result + a list of errors) → incremental/IDE (recover and re-parse edited regions on every keystroke). Performance posture is the headline runtime model.
| System | Ecosystem | Category | Algorithm / grammar class | Error recovery | Performance posture | Link |
|---|---|---|---|---|---|---|
| simdjson | C++ | SIMD / data-parallel | Two-stage: vectorized structural index + pushdown state machine | Fail-fast (validate) | Branchless SIMD, ~ GB/s, zero-copy, runtime CPU dispatch | simdjson |
| simd-json | Rust | SIMD / data-parallel | Two-stage SIMD tape (simdjson port); mutable &mut [u8] in-situ | Fail-fast (validate) | Branchless SIMD, runtime CPU dispatch; no On-Demand | simd-json |
| sonic-rs | Rust | SIMD / data-parallel | On-demand SIMD (lazy get-by-pointer; not two-stage) | Fail-fast (validate) | SIMD (compile-time dispatch); lazy skip; serde-compatible | sonic-rs |
| yyjson | C (C89) | High-perf JSON (no SIMD) | Hand-tuned scalar reader → single-alloc doc/val arena | Fail-fast (error pos) | GB/s without SIMD; one .h+one .c; in-situ option | yyjson |
| RapidJSON | C++ | High-perf JSON (part SIMD) | Recursive-descent SAX + DOM; in-situ, MemoryPoolAllocator | Fail-fast (offset) | In-situ zero-copy; SIMD only for whitespace/string scan | rapidjson |
| Hyperscan | C/C++ | SIMD / data-parallel (regex) | Regex decomposition → SIMD literal (FDR/Teddy) + LimEx bit-NFA | n/a — matcher⁴ | SIMD, streaming, tens-of-thousands of patterns | hyperscan |
| Zig tokenizer | Zig | Hand-written lexer | Table-free DFA-style scanner (labeled-switch); comptime keyword map | Invalid-token (no throw) | Zero-alloc, no transition table, byte-range tokens | zig |
| tree-sitter | C | Incremental / IDE-grade | Table-driven GLR; lossless CST | Incremental/IDE | Temporal: reuse unchanged subtrees per keystroke; no SIMD | tree-sitter |
| rust-analyzer | Rust | Incremental / query-based | Hand-written RD → rowan red-green CST; salsa query graph | Incremental/IDE | Demand-driven, memoized queries; in-memory reuse per edit | rust-analyzer |
| Roslyn | C# / VB | Incremental / IDE-grade | Hand-written RD → red-green full-fidelity tree | Incremental/IDE | Subtree reuse ~99.99% per edit; lazy red nodes; DAG at green | roslyn |
| Lezer | JS / TS | Incremental / IDE-grade | Table-driven incremental GLR; compact blob tree | Incremental/IDE | TreeFragment reuse per edit; in-browser; no SIMD | lezer |
rustc queries | Rust | Query-based compiler | Demand-driven memoized queries over AST/HIR/MIR | n/a — query engine³ | On-disk red/green DepGraph reused across compiles | rustc |
| syntect | Rust | Syntax highlighting (TextMate engine) | Stateful per-line regex machine over a .sublime-syntax context stack (oniguruma / fancy-regex) | Never fails — degrades⁵ | Per-line ops; lazy contexts; bincode+flate2 grammar dumps | syntect |
| bat | Rust | Syntax highlighting (CLI pipeline) | syntect consumer — detection + pipeline; no parsing of its own | Never fails — degrades⁵ | Lazy embedded syntaxes.bin/themes.bin; full-feed stateful highlight; ANSI tiering | bat |
| tree-sitter-highlight | Rust (C core) | Syntax highlighting (CST queries) | tree-sitter GLR CST + merged highlights/injections/locals queries | Never fails — degrades⁵ | Whole-buffer parse per highlight; streaming events; host cancellation | ts-highlight |
| Shiki | TypeScript | Syntax highlighting (TextMate, web) | TextMate scope machine (vscode-textmate lineage); WASM oniguruma or JS-RegExp transpilation | Never fails — degrades⁵ | AOT/build-time HTML; packed token metadata; per-line length + time guards | shiki |
| Pygments | Python | Syntax highlighting (lexers as code) | Regex state machine per lexer (tokens dict over a state stack); whole-text scan | Never fails — degrades⁵ | Batch; hierarchical token taxonomy; 14 formatters; no pathology guards | pygments |
| Chroma | Go | Syntax highlighting (ported corpus) | Pygments' machine interpreted from machine-translated XML lexers; regexp2 backtracking | Never fails — degrades⁵ | Batch; 250 ms per-match regex timeout; integer-encoded token taxonomy | chroma |
| highlight.js | JavaScript | Syntax highlighting (web, client) | Nested-mode regex trees; relevance-scored auto-detection with illegal early rejection | Never fails — degrades⁵ | Client-side per block; SAFE_MODE; detection = highlight-with-every-grammar | hljs |
@lezer/highlight | JS / TS | Syntax highlighting (tag-based) | Tree walk over the incremental Lezer CST; closed Tag lattice + modifier algebra | Never fails — degrades⁵ | Viewport-clipped walks (from/to); stateless over the incremental tree | lezer-hl |
| Helix | Rust | Editor engine (tree-sitter consumption) | tree-sitter CSTs kept alive across edits (tree-house); merged highlight+locals queries | Degrades — per-buffer disable⁵ | Incremental reparse (500 ms budget, 512 MiB cap); viewport-bounded queries | helix |
| Linguist | Ruby | Language detection | Ordered strategy cascade (modeline→…→heuristics→classifier), monotone candidate narrowing | Never fails — worst case wrong | Cost-ordered stages; 50 KB classifier window; registry + overrides as data | linguist |
| LSP semantic tokens | Protocol | Semantic tier (wire format) | None — transports server-computed classifications (legend + 5-int delta encoding) | Invisible — base tier remains⁵ | Integer arrays, relative positions, deltas, viewport range requests | lsp-st |
| IntelliJ Platform | Java/Kotlin | Semantic tier (in-process IDE) | Restartable int-state lexer → PSI parser → incremental annotator passes (latency-layered) | Never fails — errors in-tree⁵ | Per-tier incrementality; relex-only-the-change; dumb-mode degradation | intellij |
| Vim & Emacs | C / Elisp | Editor engines (regex, windowed) | Regex items + containment / syntax-table + keyword passes; derived state, no tree | Never fails — bounded mis-scope⁵ | Backward sync (:syn sync); jit-lock render-driven laziness; explicit cost ceilings | vim-emacs |
| ANTLR | Java (10 tgts) | Generator (LL / ALL(*)) | ALL(*) adaptive LL — any non-left-recursive CFG | Recovering | O(n⁴) worst, linear in practice via warm lookahead-DFA cache | antlr |
| GNU Bison | C (multi-tgt) | Generator (LR) | LALR(1) default; IELR/canonical; opt-in GLR | Panic-mode (error) | Linear, table-driven, tiny constant; sequential | bison-yacc |
| Menhir | OCaml | Generator (LR) | Full LR(1) (Pager); opt-in canonical/LALR/GLR | Recovering API¹ | Linear; resumable API powers Merlin/ocaml-lsp | menhir |
| pest | Rust | Generator (PEG) | PEG (non-memoizing recursive descent) | Diagnostic | Scannerless, zero-copy leaves; super-linear on adversarial | pest |
| Parsec family | Haskell | Parser combinator | Predictive LL-with-try; ordered choice | Diagnostic / recov.² | Scalar; near-linear on LL(1); attoparsec streaming/zero-copy | haskell-parsec |
| nom | Rust | Parser combinator | PEG-like ordered-choice recursive descent (scannerless) | Fail-fast | Zero-copy, byte/streaming, ~ handwritten-C; no memoization | rust-nom |
| chumsky | Rust | Parser combinator | Recursive-descent PEG; opt-in left-rec + memoization | Recovering | Post-0.10 zero-copy rewrite; no SIMD/streaming/incremental | rust-chumsky |
| winnow | Rust | Parser combinator | PEG-like ordered-choice RD (nom fork); &mut Stream | Fail-fast; opt-in cut/recovery | Zero-copy; unified Stream trait; ~ nom | winnow |
| flatparse | Haskell | Parser combinator | PEG-like RD; failure/error split (nom-like) | Fail-fast + explicit errors | Zero-alloc validators (GHC primops); 2–10× attoparsec; no incremental | flatparse |
| combine | Rust | Parser combinator | Predictive LL(1) + attempt (Parsec-style) | Diagnostic (consumed/commit) | Zero-copy range; partial/streaming; any Stream | combine |
| Angstrom | OCaml | Parser combinator | PEG-like backtracking RD, unbounded lookahead | Backtracking + commit | Zero-copy bigstring; incremental (buf/unbuf); CPS | angstrom |
| FParsec | F# | Parser combinator | Predictive LL + backtracking; user-state 'u | Diagnostic (best-in-class) | Optimized (C# core); built-in OperatorPrecedenceParser (Pratt) | fparsec |
¹ Menhir's incremental/inspection API is the substrate IDE tooling uses for recovery and live parsing; unlike tree-sitter, it is not a built-in edit-local CST reuse engine. ² attoparsec drops error book-keeping for speed; Megaparsec adds typed errors, error bundles, and on-the-fly recovery. ³ rustc's query system is an incremental-computation engine, not a parser; its front-end lexer/parser is still batch. Incrementality applies to everything derived from the AST, reused across whole compiler invocations via an on-disk dependency graph. ⁴ Hyperscan is a multi-pattern regex matcher, not a parser: it reports which compiled patterns match (and where) via a callback and builds no tree — surveyed for its SIMD/data-parallel technique, shared with simdjson via co-author Geoff Langdale. ⁵ Highlighters invert the error-recovery axis: the approximate (TextMate-model) systems cannot reject input — the worst case is missing or wrong color, with guards (bat's 16 KiB line cutoff, Shiki's length/time budgets) bounding pathological cost — and the precise one inherits its parser's recovered CST (ERROR/MISSING spans emit unstyled). See the highlighting synthesis.
Wave-2 clusters landed — Incremental / query-based (rust-analyzer, Roslyn, Lezer,
rustcqueries); SIMD / high-performance (simd-json, sonic-rs, yyjson, RapidJSON, Hyperscan, Zig tokenizer); Combinators (winnow, flatparse, combine, Angstrom, FParsec). Waves 4–5 add Syntax highlighting (syntect, bat, tree-sitter-highlight, Shiki, Pygments, Chroma, highlight.js,@lezer/highlight, Helix, Linguist, LSP semantic tokens, IntelliJ, Vim & Emacs; synthesized in syntax-highlighting). Still deferred: Generators — LALRPOP (Rust), Lark & PLY (Python), Peggy (JS), Ragel/re2c (state-machine lexers) — and a few second-tier JVM combinators (FastParse/parsley/cats-parse, Scala).
Taxonomy
By parsing strategy
The single most load-bearing axis: how the parser explores the grammar. Each family is developed in the linked theory deep-dive.
| Strategy | The idea | Theory | Systems here |
|---|---|---|---|
| Top-down (LL / recursive descent) | Predict the rule from lookahead, expand from the root; leftmost derivation | top-down | ANTLR (ALL(*)), and every combinator below |
| Bottom-up (LR family) | Shift tokens, reduce handles bottom-up; rightmost derivation in reverse | bottom-up | Bison (LALR), Menhir (LR(1)) |
| Generalized (GLR / GLL / Earley) | Pursue all live parses at once (graph-structured stack / chart); all CFGs | bottom-up · general | tree-sitter (GLR); Bison/Menhir GLR mode |
| PEG (ordered-choice recognition) | First-match-wins ordered choice + syntactic predicates; unambiguous, scannerless | peg-packrat | pest, nom, chumsky, Parsec (-like); combinators winnow, flatparse, combine, Angstrom, FParsec |
| Operator-precedence / Pratt | A linear expression sub-engine driven by binding power | pratt-precedence | embedded in chumsky, pest (PrattParser) |
| Derivative-based | Differentiate the language by each input symbol; regex→DFA up to full CFG | derivatives | research-grade (derp); derivative lexers in ml-ulex |
| SIMD / data-parallel | Classify the whole input with vector instructions, then a scalar second pass | formal-languages | simdjson, simd-json, sonic-rs (JSON); Hyperscan (regex); part-SIMD RapidJSON; scalar-but-fast yyjson; hand-written Zig lexer |
| Incremental / query-based | Reuse the parse tree (node reuse) and/or the computation (memoized queries) across edits | incremental | tree-sitter · Lezer (GLR); rust-analyzer · Roslyn (red-green RD); rustc (queries) |
| Stateful line re-lexing (TextMate scopes) | Interpret a regex+scope grammar one line at a time, carrying a context/scope stack between lines — approximate, tree-free, never fails | syntax-highlighting | syntect, Shiki, consumed by bat; Vim's region stacks are the same family; the CST-query counterpart is tree-sitter-highlight |
| Whole-text regex lexing (lexers as code) | One position-anchored scan of the entire text through a host-language regex state machine — multiline-natural, batch-only | syntax-highlighting | Pygments, Chroma (ported to XML data), highlight.js (mode trees); Emacs font-lock is the editor-resident ancestor |
By interface model
How the grammar reaches the parser — the ergonomics axis.
| Interface model | What you write | Systems |
|---|---|---|
| Offline generator (external DSL) | A grammar file compiled to a parser ahead of time | ANTLR (.g4), Bison (.y), Menhir (.mly), pest (.pest), tree-sitter (grammar.js) |
| Embedded combinators (internal DSL) | Ordinary host-language values composed with combinator functions | Parsec, nom, chumsky, winnow, flatparse, combine, Angstrom, FParsec |
| Hand-written recursive descent | A procedure per rule, often + a Pratt expression loop | the production norm (GCC/Clang/rustc/Go); rust-analyzer + Roslyn (→ a red-green CST); the Zig lexer; the substrate the above reify |
| Library state machine (no grammar) | Direct hand-tuned pipeline (SIMD or careful scalar) | simdjson, simd-json, sonic-rs, yyjson, RapidJSON, Hyperscan |
| Query graph (no phases) | Define the compiler as memoized K → V queries; results reused on demand | rust-analyzer (salsa), rustc |
| Runtime-interpreted grammar data | Declarative pattern/query files loaded and interpreted at run time — no codegen: .sublime-syntax, .tmLanguage.json, .scm queries | syntect, Shiki, tree-sitter-highlight (queries over a generated grammar); bat ships them pre-serialized; Chroma (XML lexers); Helix (languages.toml + .scm + TOML themes) |
By error-recovery posture
The modern differentiator (see the comparison). Recovery is what separates a batch compiler back-end from an IDE-grade front-end.
| Posture | Behaviour on a syntax error | Systems |
|---|---|---|
| Fail-fast / validate | Stop at the first error; report position | simdjson, simd-json, sonic-rs, yyjson, RapidJSON, nom, winnow, flatparse, Bison (without error rules) |
| Panic-mode | Skip to a synchronizing token and resume without a full tree | Bison (error rules), classic LL/LR parsers |
| Diagnostic | Precise positioned message (expected-sets), still one error | pest, Parsec/Megaparsec (base), combine, FParsec (best-in-class) |
| Recovering | Produce a partial AST and a list of errors | chumsky, ANTLR, Megaparsec, Menhir clients |
| Incremental / IDE | Recover and re-parse only the edited region on each keystroke | tree-sitter, rust-analyzer, Roslyn, Lezer |
| Degrade-gracefully (highlighting) | Never reject input; worst case is unstyled or mis-scoped text, with guards bounding pathological cost | syntect, bat (16 KiB line cutoff), Shiki (length/time budgets), tree-sitter-highlight (ERROR spans + cancellation); wave 5: Chroma (250 ms match timeout), Helix (parse budget → per-buffer disable), Vim & Emacs (synmaxcol/redrawtime, jit-lock), Pygments (unguarded — the counterexample), LSP/IntelliJ (higher tiers fail invisibly) |
Milestones
A high-confidence timeline interleaving theory/algorithm milestones with tool/system milestones. Per-result provenance lives in each deep-dive's Sources.
| Year | Theory / algorithm milestone | Tool / system milestone |
|---|---|---|
| 1956 | Chomsky — Three Models for the Description of Language (the hierarchy) | — |
| 1959–1963 | Chomsky formal properties; Floyd 1963 — operator-precedence parsing | — |
| 1964 | Brzozowski — derivatives of regular expressions | — |
| 1965 | Knuth — On the Translation of Languages from Left to Right (LR parsing) | CYK recognition (Cocke/Kasami/Younger, 1965–67) |
| 1968–1970 | Lewis & Stearns LL(k); Earley 1970 — general CF parsing | — |
| 1973 | Pratt — Top Down Operator Precedence (TDOP) | — |
| 1975 | Valiant — sub-cubic CF recognition via Boolean matrix mult. | yacc (Johnson, Bell Labs) — LALR(1) generator ships on Unix |
| 1977–1982 | Pager 1977 minimal-state LR; DeRemer & Pennello 1982 efficient LALR(1) | lex/flex lexer generators |
| 1985 | Tomita — GLR (graph-structured stack) for natural language (Efficient Parsing for Natural Language, Kluwer, 1986) | GNU Bison released |
| 1986 | The "Dragon Book" (Aho, Sethi & Ullman) codifies the field | PCCTS, Terence Parr's ANTLR predecessor (1989) |
| 1991 | Leo — linear Earley on every LR(k) grammar | — |
| 1997–2001 | Wagner & Graham 1997/98 — optimal incremental parsing (O(t+s·lg N)); Hutton & Meijer 1998 Monadic Parsing | Parsec (Leijen & Meijer, 2001) — Haskell combinators; Vim 5.0 ships syntax highlighting (Feb 1998); IntelliJ IDEA 1.0 (Jan 2001) — the layered IDE model; jit-lock becomes Emacs' default lazy fontification engine (21.1, Oct 2001; font-lock itself dates to 1992, Lucid Emacs) |
| 2002 | Ford — packrat parsing (linear-time PEG); Lee — BMM lower bound | Aycock & Horspool practical Earley |
| 2004 | Ford — Parsing Expression Grammars (POPL) | TextMate 1.0 (Odgaard, Oct 2004) — the editor whose scope-named grammars + .tmTheme themes (a 1.x-era feature) became the highlighting lingua franca |
| 2006–2009 | Warth 2008 PEG + left recursion; Owens et al. 2009 derivatives reexamined | Menhir (Pottier & Régis-Gianas, 2006); attoparsec; FParsec (Tolksdorf, F#); Pygments 0.5 (Brandl, Oct 2006); highlight.js (Sagalaev, 2006) |
| 2011 | Might, Darais & Spiewak — Parsing with Derivatives; LL(*) (PLDI) | Marpa (Kegler) — engineered Earley; Roslyn CTP — red-green trees / compiler-as-a-service; Linguist open-sourced (GitHub, May 2011) |
| 2012–2014 | CompCert verified parser (ESOP 2012); ALL(*) (Parr, Harwell & Fisher, OOPSLA 2014) | ANTLR 4 (2013, ALL(*)); Roslyn open-sourced (2014); nom 1.0 (2015) |
| 2015–2016 | Megaparsec; Adams et al. 2016 — PWD is cubic, ~951× faster | Bison counterexamples (Isradisaikul & Myers, PLDI 2015); rustc query system; RapidJSON 1.1; Hyperscan open-sourced (Intel); Angstrom (OCaml); .sublime-syntax YAML grammar format (Sublime Text 3 build 3084, Apr 2015); syntect (Hume, Jun 2016) |
| 2017–2018 | Jourdan & Pottier 2017 — verified C11 LR parser (TOPLAS); Build Systems à la Carte (Mokhov et al., ICFP 2018) | tree-sitter (Brunsfeld/GitHub, 2018) — incremental GLR; rust-analyzer + salsa (2018); bat v0.1.0 (sharkdp, Apr 2018); Shiki (Pine Wu, Oct 2018); Chroma (alecthomas, 2017) — Pygments' corpus ported to Go |
| 2019 | Wang et al. — Hyperscan (NSDI '19) | simdjson (Langdale & Lemire, VLDB J.) — SIMD JSON; simd-json (Rust port); tree-sitter-highlight crate (Feb 2019) — used for GitHub.com highlighting by early 2020 (per the tree-sitter docs; no GitHub-authored announcement exists) |
| 2020–2021 | CPython adopts a PEG parser (PEP 617) | chumsky (recovering combinators); Lezer / CodeMirror 6; yyjson (no-SIMD C); Bison 3.8; LSP 3.16 semantic tokens (Dec 2020); VS Code turns on semantic highlighting for TS/JS (v1.43, 2020) |
| 2023–2026* | — | winnow forks nom; sonic-rs (ByteDance SIMD JSON); flatparse matures; chumsky zero-copy 0.10+; Shiki v1.0 rewrite (Fu, Feb 2024) + pure-JS RegExp engine (v1.15.0, Aug 2024; oniguruma-to-es from v1.23.0); Menhir GLR back-end* |
* The Menhir GLR back-end is dated to the 20260112 release as observed in this review; treat 2023–2026 tool entries as current-as-of-review.
Quick navigation
Suggested reading paths
- "I want the classical theory first." concepts → formal-languages → top-down → bottom-up → general-parsing.
- "I want the PEG/combinator lineage." peg-packrat → haskell-parsec → rust-nom → rust-chumsky → pest.
- "I want the high-performance story." formal-languages (the complexity wall) → simdjson → tree-sitter (incrementality as the other way to be fast).
- "I want production generators." bottom-up → bison-yacc → menhir → top-down → antlr.
- "I want expression parsing." pratt-precedence → the
PrattParsernotes in pest / chumsky. - "I want the syntax-highlighting story." syntax-highlighting (the model landscape + vocabulary) → syntect (the TextMate engine) → bat (the CLI pipeline around it) → tree-sitter-highlight (the precise counterpart, read against tree-sitter) → shiki (the web/HTML side) → then widen: Pygments/Chroma (lexers as code + porting), Linguist + highlight.js (detection), Helix + Vim & Emacs (windowed consumption), LSP + IntelliJ (the semantic tier) → the "Where
sparkles:syntaxfits" close (+ the D landscape). - "I'm designing the Sparkles parser." comparison → rust-nom (zero-copy,
@nogc-shaped) + rust-chumsky (recovery) → peg-packrat (the space cost) → pratt-precedence (the expression engine) → the D landscape (what D offers + the gap) → thesparkles:parsingproposal (the design).
Synthesis
- Concepts & vocabulary — the shared glossary + the parser-landscape table.
- Theory umbrella — the classical algorithm spine, end to end.
- Comparison — the head-to-head matrix, the consensus, the trade-offs, and where a Sparkles parser fits.
- Syntax highlighting — the wave-4 cluster synthesis: the TextMate vs CST-query models, the theme-format landscape, and where
sparkles:syntaxfits. - D landscape — the inward turn: what the D ecosystem offers for parsing, and the
@nogc-combinator gap thesparkles:parsingproposal fills.
Sources
Each deep-dive carries its own primary-source citations (papers, source trees, and official docs); the authoritative artifacts behind this index's classifications are:
- Foundational theory — Chomsky 1956; Knuth 1965; Earley 1970; Ford 2002/2004; Valiant 1975 / Lee 2002; as cited in the theory subtree and concepts.
- Per-system sources — the project source trees, official docs, and papers cited in each linked deep-dive (simdjson, tree-sitter, ANTLR, Bison, Menhir, pest, Parsec, nom, chumsky).