Heuristic grammar pre-optimizations #125

Activity

1. tinovyatkin

   added sub-issues on Jul 19, 2026

   • codegen: complete the opt-in grammar optimization pipeline #128
   • perf(codegen): left-factor pure parser alternatives and optional tails #129
   • perf(codegen): inline eligible pure parser rules before ATN construction #130
   • perf(codegen): eliminate provably duplicate or subsumed pure parser alternatives #131
2. tinovyatkin commented on Jul 19, 2026

   

   tinovyatkin

   on Jul 19, 2026

   ContributorAuthor

   More actions

   I read the full article and mapped all of its proposals against the current Rust generation/runtime path.

   Main conclusion

   There are three reusable source-rewrite families worth pursuing, but they need a new pre-ANTLR stage first. antlr4-rust-gen currently receives .interp after ANTLR has already constructed the ATN; --grammar is used for semantic metadata/actions and cannot change prediction structure.

   I created these ordered sub-issues:

   1. codegen: complete the opt-in grammar optimization pipeline #128 — opt-in pre-ANTLR grammar optimization pipeline, structured grammar model, source maps/manifests, safety classes, differential testing, and Rust-side measurement
   2. perf(codegen): left-factor pure parser alternatives and optional tails #129 — pure common-prefix/optional-tail factoring (P X | P, shared call prefixes/suffixes, etc.)
   3. perf(codegen): inline eligible pure parser rules before ATN construction #130 — bounded inlining of eligible pure parser rules
   4. perf(codegen): eliminate provably duplicate or subsumed pure parser alternatives #131 — removal of exact/provably subsumed pure parser alternatives in a finite conservative fragment

   The distinction between tree/API preserving and recognition preserving is essential. This target exposes one public method per parser rule plus typed contexts/listener events. A rewrite can preserve the accepted token language while still breaking generated APIs, tree shape, labels, action timing, alternative numbers, diagnostics, or recovery.

   How the article maps

   Applicable under conservative eligibility:

   • Inlining built-in/helper productions (reported 50%) and rule resolution (2.7%) reduce to grammar-agnostic pure-rule inlining: perf(codegen): inline eligible pure parser rules before ATN construction #130. The pass must not know what a built-in function is.
   • Declaration left-factorization (2.2%), optional .key() merge (1.4%), call factorization (>1%), and the non-left-recursive parts of the variable-access rewrites reduce to common structural factoring: perf(codegen): left-factor pure parser alternatives and optional tails #129.
   • Removing the bracket-expression alternative (2%) motivates perf(codegen): eliminate provably duplicate or subsumed pure parser alternatives #131, but only where duplication/subsumption is actually proven. Arbitrary CFG language inclusion is not a safe heuristic.
   • Merging call categories is only automatable where the result is algebraically language-equivalent. The article's generalized examples can widen accepted argument forms; that semantic generalization is not included.

   Not filed as new optimization issues:

   • Two-stage SLL then LL (15.2%) is runtime policy, not .g4 preprocessing. This runtime already exposes PredictionMode::Sll and BailErrorStrategy, and generated adaptive decisions perform SLL prediction before full-context escalation. Any whole-parse retry convenience should be justified separately, not mixed into the grammar pass.
   • Parser reuse is already supported by generated recognizer reset/re-feed APIs (the article also measured no meaningful gain).
   • Semantic-predicate merging regressed the article workload by 6%; adding runtime predicates is particularly harmful to prediction and is excluded.
   • Operator merging/grouping and left-recursive variable-access factoring require knowledge of intended precedence and associativity. ANTLR encodes precedence through left-recursive alternative order; a heuristic cannot assume separately ordered operators were intended to share a level.
   • Outsourcing built-in validation to visitors changes the grammar's accepted language and moves cost/behavior into application code. It is not a semantics-preserving codegen optimization.
   • Generalizing method calls can similarly admit name/argument combinations rejected by the original grammar unless exact equivalence is proven; the exact safe subset is covered by perf(codegen): left-factor pure parser alternatives and optional tails #129/perf(codegen): inline eligible pure parser rules before ATN construction #130.
   • Removing a parenthesized form because another rule appears to cover it is grammar-specific unless perf(codegen): eliminate provably duplicate or subsumed pure parser alternatives #131's bounded proof succeeds.
   • Comment character-class correction ([\n|\r] to [\r\n]) is a correctness change that removes literal |; intent cannot be inferred safely and it was not a parse-time win.
   • Heap sizing, explicit lexer rules, whitespace/newline consolidation, subrule reordering, another declaration factorization, concrete EBNF substitutions, expression reordering, and manual left-recursion elimination were reported as neutral or ineffective. Several can also change token channels, ambiguity ordering, or precedence.
   • Speedy ANTLR is an alternative native backend strategy, not grammar preprocessing.
   • Visitor/listener caching is application-specific and the article provides no generic runtime transformation to implement.

   Evidence standard

   The article's 85.6% headline is the combined result for one Rula grammar using a generated Python parser, with some visitor changes. It is not an expected result for this Rust target, whose generated parser already performs LL(1)/SLL/adaptive specialization. Each pass therefore needs same-machine generated-Rust A/B evidence and before/after ATN/adaptive-decision metrics; shorter source or generated line count alone is insufficient.
3. tinovyatkin

   added a sub-issue on Jul 26, 2026

   • perf(codegen): collapse linear precedence ladders into a single left-recursive rule #225