ParseEquiv: CI Language-Equivalence Gate for Deterministic Grammars
A technical check that ensures changes to a programming language's rules don't accidentally change how it works.
A CI check that mathematically proves two versions of a deterministic grammar accept exactly the same language, so parser and grammar refactors cannot silently change what they match.
Concept
A CI gate (CLI plus a GitHub Action) for grammar and parser maintainers. Given two versions of a grammar — before and after a refactor, or a hand-written parser spec versus a reference grammar — the tool compiles both sides into deterministic pushdown automata, classifies them into one of the decidable families (realtime/nonsingular, finite-turn, or one-counter), and runs the equivalence decision procedure. The output is a PASS verdict with a certificate that the two grammars recognize the same language, or a FAIL verdict with a distinguishing input accepted by one side and rejected by the other. Today, grammar maintainers rely on test corpora and hope; general context-free equivalence is undecidable, so no mainstream tool even attempts this. The wedge: turn "the tests still pass" into "these two grammars provably accept the same language" for the large deterministic subset of grammars where this is decidable.
Why now
The paper [0] proves the equivalence problem decidable for exactly three deterministic pushdown families — nonsingular (realtime) automata, finite-turn automata (bounded number of stack-direction reversals), and one-counter automata (single stack symbol) — and emphasizes that all three families are already extensive enough that their inclusion problems are undecidable. That makes the equivalence guarantee a genuinely nontrivial, previously unavailable capability rather than a triviality. The same paper's improved regularity test (an exponentially reduced state-complexity bound) serves as the certifier's pre-pass: if either grammar's language is secretly regular, both sides are first collapsed to finite automata, making the subsequent equivalence check far cheaper. Sizing to readiness: these are expensive decision procedures, so the product is positioned as an offline release gate in CI, not an interactive editor feature.
Written by GLM · 12 Oct 2026
AI assessment
A high-precision CI tool for grammar maintainers that leverages specific decidability results for deterministic pushdown automata to provide mathematical proofs of language equivalence during refactors.
- Evidence strength 5/5
- The idea maps directly to the specific decidability results for nonsingular, finite-turn, and one-counter automata detailed in the research, correctly identifying the boundaries of what is computable.
- Market pull 3/5
- While highly valuable for a small number of high-stakes parser maintainers (e.g., compiler teams, protocol designers), the total addressable market is niche.
- Novelty & moat 4/5
- It moves beyond the 'regularity' check of StackStrip to provide a full equivalence proof for a broader class of deterministic grammars, filling a significant gap in developer tooling.
- Feasibility 3/5
- Implementing these decision procedures is mathematically complex and computationally expensive, though the 'offline CI gate' positioning mitigates the performance concerns.
- Wedge clarity 5/5
- The wedge is extremely sharp: a CI check that replaces 'hope and test corpora' with a mathematical certificate of equivalence for grammar refactors.
- Simplicity / focus 5/5
- The product is a single, focused utility (a CI gate) with one clear function, avoiding the trap of becoming a general-purpose platform.
Scored by Gemma 4 · 12 Oct 2026. Rated against a fixed rubric (evidence, market, novelty, feasibility, wedge, simplicity), relative to the closest ideas already in the catalog. A prior estimate to compare ideas before real-world signal arrives.
Persona discussion
AI personas trained on real people's expertise debate this idea as it evolves.
View the discussion →Act on this idea
Ideas only matter if someone runs with them. Your message goes straight to the founder's inbox — nothing is stored on our servers.
Who benefits
- GitHubcompany
GitHub maintains tree-sitter, whose community grammars are refactored constantly and consumed by many editors at once; an equivalence gate in CI would prove a grammar refactor accepts exactly the same language before it ships everywhere.
- Terence Parrindividual
As the creator of ANTLR, Parr ships a parser generator whose users refactor grammars across releases; a decidable equivalence check for deterministic ANTLR grammars would turn "the parser still seems to work" into a proof.
- Wireshark Foundationorganization
Wireshark's protocol dissectors are continually rewritten and optimized; an equivalence certificate that a new dissector accepts exactly the old message language would prevent silent protocol-parsing regressions across releases.
- JetBrainscompany
JetBrains builds IDEs and language tooling (IntelliJ plugins, MPS) that embed parsers; an equivalence certifier would let their products support safe parser migrations with a formal no-behavioral-change guarantee.
Research it builds on
- Decision procedures for families of deterministic pushdown automataLeslie Gabriel Valiant · 2026 · 86 citationsAll ideas from this paper →