WEP: Gale — Grammar Adaptive LL Engine

Context

Wado-based projects need a parser generator for processing structured text (config formats, DSLs, the Wado grammar itself). The problem with existing tools:

Bison/yacc .y: Grammar and semantics are coupled — action code ({ $$ = $1 + $3; }) is embedded in the grammar file. The grammar becomes host-language-specific and hard to read.

ANTLR4: Solves the coupling problem with Visitor/Listener pattern. But the generator and runtime must be the same version. Every consumer project carries a antlr4-runtime dependency pinned to the generator version. Runtime version drift is a persistent maintenance burden in practice.

PEG/packrat (pest, etc.): No lexer/parser separation; whitespace handling is awkward; no grammar label system.

Wado's answer is Gale (Grammar Adaptive LL Engine): a parser generator written in Wado, targeting Wado output, that eliminates version drift by inlining the runtime into every generated file.

Decision

Name

Gale — Grammar Adaptive LL Engine.

• Respects ANTLR4's Adaptive LL algorithm as direct inspiration
• Independent identity; not a fork or port
• Short, evocative of speed and power
• 4 letters, consistent with Wado ecosystem tool naming

Grammar Format: ANTLR4 .g4 Subset

ANTLR4's .g4 format is adopted as Gale's primary input. Key reasons:

• Already host-language-free — action code (@header, @members, {...}) exists in ANTLR4 but is never required for pure structure description
• Lexer rule / parser rule separation (uppercase = lexer, lowercase = parser) is clean and practical
• Rule labels (# LabelName) map naturally to Wado variant cases
• Widely used; existing grammars (SQL, JSON, etc.) can be adapted with minimal changes

Phase 1 parses target-language-dependent elements — action blocks ({...}), semantic predicates ({...}?), options { superClass = ... }, @header/@members — and skips them with a warning, so real-world .g4 grammars are consumable while the output stays purely structural. Later phases translate them instead; package-gale/antlr4-compatibility.md holds the current contract.

Phase 1 Scope

Supported:

Parsed but ignored (warned and skipped):

• Embedded action blocks ({ code }) — skipped with warning
• Semantic predicates ({condition}?) — skipped with warning
• options { superClass = ...; } — parsed, superClass ignored with warning; tokenVocab recognized for future lexer/parser split support
• @header, @members, and other named actions — skipped with warning

Not in Phase 1:

• Lexer modes (mode INSIDE;)
• Grammar imports (import BaseGrammar;)
• tokens {} blocks
• Syntactic predicates
• Error recovery customization

Code Generation: Recursive Descent

The generator emits an error-resilient, untyped flat CST (CstStore), not a typed node per rule and a visitor over it. That typed shape was the original plan and was not shipped. For everything a generated parser exports, see package-gale/README.md.

Generated output is a single .wado file containing:

1. Inlined runtime — Span, TokenStream, Diagnostic, the CST store, etc.
2. Token kinds — one TK_<name> constant per lexer rule plus the synthetic TK_EOF and TK_ERROR
3. Node kinds — one RK_<RULE> constant per parser rule, and a <Rule>Alt enum for a rule with labeled alternatives
4. Lexer function — tokenize(input) -> TokenStream
5. Parser functions — parse and one parse_<rule> per parser rule, each returning a ParseResult

Recursive descent is chosen over table-driven because:

• The generated Wado code is human-readable and debuggable
• No separate table interpreter is needed in the runtime
• LL grammars (the target of .g4) map 1:1 to recursive descent functions
• Reduces the runtime surface to pure data structures

Runtime Inlining: No Version Drift

Gale reads its own src/runtime/*.wado at generation time and emits it verbatim into the generated file, gated so each parser carries only the fragments it needs. This requires #include_str (see WEP: Compile-Time File Inclusion).

Each generated file therefore carries the exact runtime its generator used. There is no external runtime package to keep in sync: upgrading Gale and regenerating upgrades the runtime everywhere. This is the decision that distinguishes Gale from ANTLR4, whose generator and runtime must be version-matched by every consumer.

The fragments are plain Wado modules, unit-testable on their own.

Consequences

Positive

• No runtime version drift: each generated file is self-contained
• Grammar files are pure structure — no host code ever
• Generated Wado code is human-readable and debuggable
• Runtime is independently testable as plain Wado source
• package-gale/ is a concrete pilot for wado.toml
• ANTLR4 .g4 grammars are directly usable — action blocks and semantic predicates are warned and skipped, so real-world grammars work without manual cleanup

Negative

• Generated files are larger: runtime code is repeated across all generated parsers
• Runtime bug fixes require regenerating parsers (acceptable trade-off for eliminating version drift)
• Only direct left recursion is rewritten (matching ANTLR4); indirect/mutual left recursion is unsupported

Trade-offs

Inlining vs separate runtime package: A separate runtime package would be smaller generated files but reintroduces the version drift problem. Inlining is the principled choice for a tool that prioritizes zero-maintenance consumption.

Recursive descent vs table-driven: Recursive descent generates readable code and needs minimal runtime. Table-driven parsing (LL table, Earley chart) would support a wider class of grammars but the generated code would be opaque arrays — harder to debug and requiring a larger runtime. For the target use case (well-structured DSLs and config formats in .g4 form), recursive descent is sufficient.

Left-recursion: LL parsers cannot handle left recursion directly. Gale rewrites direct left recursion into a precedence-climbing parser automatically (as ANTLR4 does), so grammars like expr : expr '+' term | INT work as written. Indirect (mutual) left recursion remains unsupported.

Progress

Status: Done. The shipped design diverged from the typed-CST + Visitor sketch in the Decision section. Generated parsers expose an error-resilient, untyped flat CST (CstStore; ParseResult { cst, tokens, diagnostics }), left recursion is handled by precedence climbing, and prediction is adaptive LL with a runtime ATN simulator for ALL(*) decisions. See package-gale/README.md for the current consumer-facing API and package-gale/antlr4-compatibility.md for the compatibility contract.

Phase 0: Project scaffold — Done

• package-gale/ directory with wado.toml
• Runtime types with tests

Phase 1: G4 lexer and parser — Done

• G4 lexer (g4/token.wado, g4/lexer.wado): tokenizes .g4 source text.
• G4 parser (g4/parser.wado): recursive descent producing Grammar IR.
• Grammar IR (ir.wado): typed representation of grammar structure.

Phase 2: Code generation — Done

• [x] Generate .wado source from Grammar IR
• [x] Inline runtime via #include_str, gated per fragment
• [x] Lexer generation (fn tokenize)
• [x] Recursive descent parser-function generation

Phase 3: Adaptive LL and resilient parsing — Done

• [x] Error-resilient parse tree: untyped flat CstStore + ParseResult { cst, tokens, diagnostics }, with local recovery (Missing / Skipped / <error>) instead of a hard parse failure
• [x] Direct left recursion via precedence climbing (lifts the Phase 1 LL-only limit)
• [x] Adaptive LL prediction with a runtime ATN simulator for ALL(*) / full-context decisions
• [x] Labeled alternatives as a per-rule <Rule>Alt enum + <rule>_alt(node)
• [x] Kiln integration: use g from "./X.g4" with { generator: ... } generates the parser at compile time
• [x] gale dump [--atn | --lexer] prediction / automaton / lexer-emit inspector and opt-in trace

This WEP is complete; further development of Gale is tracked in package-gale/ (TODO.md, antlr4-compatibility.md) rather than here.