Support mutual (indirect) left-recursion that ANTLR rejects

[tinovyatkin]

Context

ANTLR 4 supports direct left-recursion: a rule that references itself as its own left corner (e : e '*' e | e '+' e | INT ;) is rewritten internally into a precedence-climbing form. This is the well-known ALL(*) precedence-rule handling.

It does not support mutual (indirect) left-recursion — a cycle through two or more rules, e.g.:

a : b '+' a | INT ;
b : a '.' b | ID ;

Here a can reach a left-recursive position through b and vice versa. ANTLR rejects this ("rule ... is left-recursive" / mutually left-recursive error) because its precedence rewrite only recognizes the direct self-reference shape. The grammar is expressible in ANTLR syntax; the tool just refuses it.

Because this is a grammar-source-shape question, it is blocked on the .g4-as-source effort (#141): the current metadata-first flow never sees the offending rules — the ANTLR tool rejects them before any .interp exists.

Research question

Once we own grammar source, can antlr-rust-runtime accept a mutually-left-recursive grammar that ANTLR rejects, and generate a correct parser for it?

Two families of approach to evaluate:

1. Transform to an equivalent accepted form. Detect the recursion cycle and apply a semantics-preserving rewrite (indirect → direct left-recursion elimination, or grammar-level substitution to collapse the cycle into a single precedence rule) so the existing precedence machinery can handle it. Lowest-risk if a general, provably-equivalent transform exists.
2. Handle the cycle directly in prediction. Extend the recognizer to climb precedence across a rule cycle rather than a single rule. Higher-risk, larger runtime surface, but avoids reshaping the user's grammar/tree.

The evaluation should establish which class of mutual recursion is tractable (there are known-hard cases) and where we must still decline.

Potential benefit vs the ANTLR limitation

• Expressiveness. Some languages are more naturally written with mutually-recursive rules (e.g. expression/type grammars where terms and types refer to each other left-recursively). Today authors must hand-refactor into a shape ANTLR accepts, which distorts the grammar and the resulting tree/labels away from how the language is actually specified.
• Fidelity to published grammars. A spec grammar written in the natural mutual form could be consumed closer to as-published, instead of forcing a target-specific rewrite.
• A concrete capability ANTLR doesn't have. "Accepts grammars the reference tool rejects" is a differentiator — if correctness is provable. It must never mean "accepts and silently miscompiles."

Required rigor

• Correctness is the whole game. For any accepted mutual-recursion grammar, define the intended associativity/precedence semantics explicitly (the user must be able to state it, as they can for direct precedence rules via alt order), and prove the generated parser matches it. Ambiguous cycles with no well-defined precedence must be rejected with a clear diagnostic, not guessed.
• Where approach (1) is used, differentially validate the transformed grammar against the intended semantics over valid and invalid inputs; parse trees must reflect the declared precedence/associativity.
• Full ANTLR runtime testsuite must still pass with zero skips (this must not perturb direct-left-recursion handling, which already works and is conformance-covered).
• If we cannot prove a general solution, ship a detector that recognizes mutual left-recursion and emits a precise, actionable error (strictly better than ANTLR's generic rejection) — that alone is a usability win and a safe first increment.

Acceptance criteria (staged)

1. Detect + diagnose: identify mutual-left-recursion cycles from grammar source and report them precisely (rules in the cycle, why rejected). Safe, ships first.
2. Accept a proven subclass: define the subclass we can transform/handle with provable precedence semantics; generate a correct parser; full parity + zero testsuite skips.
3. Document exactly which mutual-recursion shapes are supported vs declined.

Notes

Research-track — feasibility before commitment; the honest outcome may be "stage 1 only" if a general correct transform proves intractable. Related: #141 (source input, hard dependency), direct-left-recursion precedence handling (must not regress). Origin: discussion on antlr-ng#99 about what working directly from .g4 unlocks beyond a metadata file.

[tinovyatkin]

Real-world case study: Roslyn's own C# grammar is blocked only by this

While evaluating grammars for a C# analyzer, I hit a concrete instance of the "fidelity to published grammars" motivation in the issue body — and it's a strong one, because the grammar in question is the C# compiler team's own.

dotnet/roslyn's CSharp.Generated.g4 (1811 lines, ~340 rules, generated from the Roslyn syntax model, last updated 2026-06-24) is the only ANTLR grammar I could find with complete, current C# coverage:

Feature	Rule	C# version
Records	record_declaration	9
Negated patterns (is not)	unary_pattern	9
Logical patterns (and/or)	binary_pattern	9
Relational patterns	relational_pattern	9
Switch expressions	switch_expression, switch_expression_arm	8
List/slice patterns	list_pattern, slice_pattern	11
File-scoped namespaces	file_scoped_namespace_declaration	10
Collection expressions	collection_expression, spread_element	12
Raw strings	multi_line_raw_string_literal_token, …	11
with expressions	with_expression	9

For comparison, everything in grammars-v4 lags badly: csharp/v7 has zero occurrences of switch_expression, record, or any pattern rule; csharp/v8-spec stops at C# 8 (no C# 9 pattern combinators). A csharplang discussion has the Roslyn team confirming the grammars-v4 one is "roughly 8 years behind the language."

What actually blocks it — measured with ANTLR 4.13.2

I ran the real tool against it. The blockers are far narrower than the file's reputation suggests, and this issue is the last one standing:

Stage 1 — 23 × error(153) (empty-string closures). Root cause is just 6 empty rules: two /* epsilon */ rules (omitted_type_argument, omitted_array_size_expression — Roslyn's omitted syntax nodes for the blank slots in Foo<,> / new int[,]) and four /* see lexical specification */ stubs (interpolated_string_text_token, xml_text_literal_token, multi_line_raw_string_literal_token, single_line_raw_string_literal_token). Every one of the 23 errors is those propagating through closures like xml_text_literal_token*. Fixable in the grammar — the epsilon rules become optional at their use sites, and the four lexical stubs are exactly what a grafted lexer supplies.

Stage 2 — error(119), and nothing else. With stage 1 resolved, the entire remaining error output is this issue:

error(119): The following sets of rules are mutually left-recursive
  [type, array_type, nullable_type, pointer_type]
  and [name, qualified_name]
  and [member_declaration, record_declaration, base_type_declaration, type_declaration]
  and [expression, assignment_expression, binary_expression, conditional_access_expression,
       conditional_expression, element_access_expression, invocation_expression,
       is_pattern_expression, member_access_expression, postfix_unary_expression,
       range_expression, switch_expression, with_expression]
  and [pattern, binary_pattern]

Note ANTLR reports errors in stages, so error(119) is invisible until the empty-rule errors are cleared — which is presumably why this grammar is usually written off for vaguer reasons.

Why this is a good validation target for this issue

• Five cycles of genuinely different shape, not one toy case: a 13-rule expression cycle, a 4-rule type cycle, a 4-rule declaration cycle, and two 2-rule cycles (name/qualified_name, pattern/binary_pattern). That is a much better stress test of "which subclass is tractable" than a synthetic a : b '+' a.
• The intended precedence semantics are externally documented and testable. C# operator precedence/associativity is specified, and Roslyn itself is the reference implementation — so the issue's "the user must be able to state the intended semantics, and we must prove the parser matches it" bar is checkable against a real compiler, not just asserted. Differential testing against dotnet output is available.
• The payoff is concrete. Accepting it would mean consuming the C# team's own grammar essentially as-published, versus the current alternatives: a C#-7-era grammar (what I ended up vendoring), or maintaining a fork. In the analyzer I was building, the C#-7 grammar parses only 93 of 321 real files from dotnet/runtime's System.Text.Json cleanly — the dominant failure being C# 9 pattern syntax (~1123 hits), which no available ANTLR grammar covers.

Reproduction

curl -sfLo csharp.g4 https://raw.githubusercontent.com/dotnet/roslyn/main/src/Compilers/CSharp/Portable/Generated/CSharp.Generated.g4
# note: must be renamed to csharp.g4 — the grammar is `grammar csharp;`
java -jar antlr-4.13.2-complete.jar -Dlanguage=Java -o gen csharp.g4   # 23x error(153)
# then make the 6 empty rules non-empty and re-run -> error(119) only

Also relevant to the acceptance criteria: even staged outcome 1 (detect + precise diagnostic) would be an improvement here, since ANTLR's own message doesn't distinguish "this cycle is inherently ambiguous" from "this cycle has well-defined precedence that the tool merely can't rewrite" — and the Roslyn cycles are clearly the latter.

Cross-ref: #206 (stack-valued member state) is the other capability gap I hit consuming published C# grammars; the two are independent.