Grammar.Analysis (Ichor v0.2.1)

Copy Markdown View Source

The analysis pass between a front-end (Aether.Parser, or one of the ABNF/BNF/EBNF/PEG importers) and either backend (Grammar.VM or native codegen):

  • reference checks -- every RuleRef must name a declared token or rule; checked first, since the other passes assume a valid namespace.
  • left-recursion rewrite -- a rule that references itself as its own leftmost derivation is rewritten from A := A op b | base into the iterative A := base (op b)*, the standard PEG/packrat transform. Only direct self-recursion through a bare (uncaptured) leading reference is rewritten automatically; anything else (indirect cycles through other rules, or a self-reference buried under a capture) is reported as an error instead of guessed at.
  • possibly-empty-match repetition detection -- Star/Plus wrapping an expression that can match the empty string never terminates; flagged as an error, not just a lint, since it's a real runtime hang, not a style nit.
  • duplicate-alternative lint -- two structurally identical alternatives in the same Choice are dead code under PEG's first-match-wins semantics -- the second can never be reached.

Predefined-token override-ordering validation is already enforced by Aether.Parser itself, as it happens -- it's entirely about Aether's own five predefined tokens (DIGIT/ALPHA/ALNUM/SPACE/HEX), so it doesn't generalize to other front-ends the way the checks above do, and isn't repeated here.

Summary

Functions

Runs every check above against grammar, returning the grammar with direct left recursion rewritten to its iterative form, or every error found (not just the first -- a grammar author fixing errors one at a time via single-error feedback is slower than seeing everything at once).

Functions

run(grammar)

@spec run(Aether.Grammar.t()) ::
  {:ok, Aether.Grammar.t()} | {:error, [Ichor.Error.t()]}

Runs every check above against grammar, returning the grammar with direct left recursion rewritten to its iterative form, or every error found (not just the first -- a grammar author fixing errors one at a time via single-error feedback is slower than seeing everything at once).