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

Gale processes .g4 files but ignores any target-language-dependent elements — action blocks ({...}), semantic predicates ({...}?), options { superClass = ... }, and @header/@members sections are to be parsed, warned, and skipped (see Progress). This lets Gale consume real-world .g4 grammars (which often contain these elements) while keeping the generated output purely structural.

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 typed-CST + Visitor design sketched in this section was the original plan. The shipped generator instead emits an error-resilient, untyped flat CST (CstStore; see Progress and package-gale/README.md); the example below is kept as the historical design record.

Generated output is a single .wado file containing:

1. Inlined runtime — Span, Token, ParseError, etc. (see Runtime section)
2. TokenKind variant — one case per lexer rule plus synthetic cases (Eof, Error)
3. CST node types — one struct or variant per parser rule; labeled alternatives become variant cases
4. Visitor trait — one method per labeled alternative (or per unlabeled rule)
5. Lexer function — fn tokenize(input: &String) -> List<Token>
6. Parser functions — one per parser rule, returns the rule's CST type

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

Example: Grammar → Generated Code

Input expr.g4:

grammar Expr;

expr   : expr op=('+' | '-') term  # BinOp
       | term                      # Pass
       ;

term   : INT                       # Num
       | '(' expr ')'              # Paren
       ;

INT    : [0-9]+ ;
WS     : [ \t\n\r]+ -> skip ;

Generated expr_parser.wado:

// Generated by gale v0.1.0 from expr.g4 — do not edit
// Regenerate: gale gen expr.g4 > expr_parser.wado

// === Inlined gale runtime (gale v0.1.0) ===

pub struct Span {
    pub start: i32,
    pub end: i32,
}

pub struct Token {
    pub kind: TokenKind,
    pub text: String,
    pub span: Span,
}

pub struct ParseError {
    pub message: String,
    pub span: Span,
    pub expected: List<String>,
}

// === End inlined runtime ===

// === Generated: token kinds ===

pub variant TokenKind {
    INT,
    Eof,
    Error,
}

// === Generated: CST nodes ===

pub variant ExprNode {
    BinOp(ExprBinOpCtx),
    Pass(ExprPassCtx),
}

pub struct ExprBinOpCtx {
    pub left: ExprNode,
    pub op: Token,
    pub right: TermNode,
    pub span: Span,
}

pub struct ExprPassCtx {
    pub inner: TermNode,
    pub span: Span,
}

pub variant TermNode {
    Num(TermNumCtx),
    Paren(TermParenCtx),
}

pub struct TermNumCtx {
    pub token: Token,
    pub span: Span,
}

pub struct TermParenCtx {
    pub inner: ExprNode,
    pub span: Span,
}

// === Generated: visitor trait ===

pub trait ExprVisitor {
    type Result;

    fn visit_expr_bin_op(&mut self, ctx: &ExprBinOpCtx) -> Self::Result;
    fn visit_expr_pass(&mut self, ctx: &ExprPassCtx) -> Self::Result;
    fn visit_term_num(&mut self, ctx: &TermNumCtx) -> Self::Result;
    fn visit_term_paren(&mut self, ctx: &TermParenCtx) -> Self::Result;
}

fn walk_expr<V: ExprVisitor>(visitor: &mut V, node: &ExprNode) -> V::Result {
    return match *node {
        BinOp(ctx) => visitor.visit_expr_bin_op(&ctx),
        Pass(ctx) => visitor.visit_expr_pass(&ctx),
    };
}

fn walk_term<V: ExprVisitor>(visitor: &mut V, node: &TermNode) -> V::Result {
    return match *node {
        Num(ctx) => visitor.visit_term_num(&ctx),
        Paren(ctx) => visitor.visit_term_paren(&ctx),
    };
}

// === Generated: parser entry point ===

pub fn parse(input: &String) -> Result<ExprNode, ParseError> {
    // generated lexer + recursive descent parser
}

User code stays pure Wado — no grammar file involvement:

use { parse, ExprVisitor, ExprBinOpCtx, ExprPassCtx, TermNumCtx, TermParenCtx,
      walk_expr, walk_term } from "./expr_parser.wado";

struct Eval {}

impl ExprVisitor for Eval {
    type Result = i64;

    fn visit_expr_bin_op(&mut self, ctx: &ExprBinOpCtx) -> i64 {
        let left = walk_expr(self, &ctx.left);
        let right = walk_term(self, &ctx.right);
        return if ctx.op.text == "+" { left + right } else { left - right };
    }

    fn visit_expr_pass(&mut self, ctx: &ExprPassCtx) -> i64 {
        return walk_term(self, &ctx.inner);
    }

    fn visit_term_num(&mut self, ctx: &TermNumCtx) -> i64 {
        return i64::parse(ctx.token.text).unwrap();
    }

    fn visit_term_paren(&mut self, ctx: &TermParenCtx) -> i64 {
        return walk_expr(self, &ctx.inner);
    }
}

export fn run() {
    let tree = parse(&"1 + 2 * 3").unwrap();
    let mut eval = Eval {};
    let result = walk_expr(&mut eval, &tree);
    println(`{result}`);
}

Runtime Inlining: No Version Drift

The runtime lives in src/runtime/*.wado source files inside the gale project. At code generation time, gale reads its own runtime source and emits it verbatim into the generated file using #include_str, gated so each generated parser carries only the fragments it needs (gen_runtime in codegen.wado):

// src/codegen.wado (inside gale's own source)

fn gen_runtime(w: &mut CodeWriter, ctx: &GenContext, highlight: bool) {
    emit_runtime_fragment(w, &#include_str("./runtime/lex.wado"));   // always
    emit_runtime_fragment(w, &#include_str("./runtime/cst.wado"));
    emit_runtime_fragment(w, &#include_str("./runtime/tools.wado"));
    if ctx.emit_follow() { emit_runtime_fragment(w, &#include_str("./runtime/follow.wado")); }
    if highlight         { emit_runtime_fragment(w, &#include_str("./runtime/highlight.wado")); }
    if ctx.needs_atn()   { emit_runtime_fragment(w, &#include_str("./runtime/atn.wado")); }
}

emit_runtime_fragment strips each fragment's sibling use { ... } from "./..." imports, since all fragments are concatenated into the single generated module (lex first). This requires the #include_str language feature (see WEP: Compile-Time File Inclusion).

Why inlining eliminates version drift: Each generated file carries the exact runtime that the generator used when it was generated. There is no external runtime package to keep in sync. Upgrading gale and regenerating automatically upgrades the runtime in every generated file.

The runtime fragments are plain Wado modules and can be tested independently with wado test; they import their sibling runtime/*.wado files (stripped at inline time) and may also import the standard library (core: / wasi:), which is kept and flows into the generated parser.

Project Structure

package-gale/
  wado.toml              ← package manifest (pilot for wado.toml)
  tests/grammars/        ← real-world .g4 files for integration testing
  src/
    main.wado            ← CLI entry: `gale gen grammar.g4 [--output parser.wado]`
    main_test.wado       ← smoke test for top-level API
    g4/
      token.wado         ← G4Token enum and token helpers
      lexer.wado         ← tokenize .g4 source text
      lexer_test.wado    ← lexer unit tests
      parser.wado        ← parse tokens → GrammarIR
      parser_test.wado   ← parser unit tests
      integration_test.wado ← integration tests against real .g4 grammars
    ir.wado              ← GrammarIR: typed grammar representation
    ir_test.wado         ← IR construction tests
    codegen.wado         ← GrammarIR → .wado source string (inlines runtime)
    runtime/             ← inlined runtime, split + gated (lex/cst/tools always;
                           follow/highlight/atn on demand), unit-testable
    runtime_test.wado    ← unit tests for runtime types

The wado.toml:

[package]
name = "gale"
version = "0.1.0"
command = "src/main.wado"

This is intentionally minimal. package-gale/ serves as a pilot project for the wado.toml package manifest system — it is the first non-trivial Wado project with a wado.toml.

CLI

# Generate parser from grammar
gale gen expr.g4                          # prints to stdout
gale gen expr.g4 --output expr_parser.wado  # writes to file

# Inspect grammar structure (debugging)
gale dump expr.g4                         # print GrammarIR
gale dump expr.g4 --tokens               # print .g4 lexer output

Runtime API

The inlined runtime exports these types (all pub):

Span            { start: i32, end: i32 }
Token           { kind: TokenKind, text: String, span: Span }
ParseError      { message: String, span: Span, expected: List<String> }

The TokenKind variant is generated (not part of the shared runtime), since its cases are grammar-specific.

walk_* Functions

For each parser rule with labeled alternatives, gale generates a walk_<rule> free function alongside the Visitor trait. This allows the visitor to dispatch recursively without pattern-matching boilerplate:

fn walk_expr<V: ExprVisitor>(visitor: &mut V, node: &ExprNode) -> V::Result { ... }
fn walk_term<V: ExprVisitor>(visitor: &mut V, node: &TermNode) -> V::Result { ... }

The user calls walk_expr(visitor, &node) from their visitor methods. This is equivalent to ANTLR4's visit(ctx) dispatch, but statically typed and without virtual dispatch.

GrammarIR

The internal grammar IR represents the grammar after parsing and validation:

// ir.wado

pub struct Grammar {
    pub name: String,
    pub parser_rules: List<ParserRule>,
    pub lexer_rules: List<LexerRule>,
}

pub struct ParserRule {
    pub name: String,                    // e.g., "expr"
    pub alternatives: List<Alternative>,
}

pub struct Alternative {
    pub label: Option<String>,           // e.g., Some("BinOp")
    pub elements: List<Element>,
}

pub variant Element {
    RuleRef(String),                     // reference to another parser rule
    TokenRef(String),                    // reference to a lexer rule
    Literal(String),                     // string literal: '+'
    Group(List<Alternative>),           // (a | b | c)
    Repeat(RepeatElement),              // e*, e+, e?
    Label(LabelElement),                // op=('+' | '-')
}

pub struct RepeatElement { pub kind: RepeatKind, pub element: Element }
pub struct LabelElement  { pub name: String, pub element: Element }
pub enum RepeatKind { Star, Plus, Optional }

pub struct LexerRule {
    pub name: String,                    // e.g., "INT"
    pub is_fragment: bool,
    pub skip: bool,                      // -> skip
    pub body: List<LexerAlt>,
}

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.

walk_* functions vs direct visitor dispatch: Some Visitor patterns in ANTLR4 call visit(ctx.child) dynamically. Gale's walk_* functions are statically typed — the grammar structure is fully resolved at code generation time. This gives better type safety at the cost of requiring the grammar to be known at code generation time (which is always the case for generated parsers).

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] prediction/automaton 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.