Grammar.GLR (Ichor v0.2.1)

Copy Markdown View Source

The interpreted graph-structured-stack backend: runs the same Grammar.LRTable SLR(1) table Grammar.LR does, but accepts conflicts instead of requiring their absence -- every action in a conflict cell is taken, forking the parse across a real Grammar.GLR.GSS (node-sharing, not independent per-branch stacks: two derivations that reach the same state at the same position merge, which is what keeps this from blowing up combinatorially on a grammar with only a handful of local conflicts). The GSS-driving loop itself lives in Grammar.GLR.Runtime, shared unchanged with Grammar.Native.GLR -- this module's own job is just building the table (recompiled on every call, the same "VM interpreted" convention Grammar.VM and Grammar.LR already follow) and wrapping its plain action/goto maps into the closures Runtime.run/6 expects.

This is resolved GLR, not full unresolved GLR: it never returns a parse forest. If more than one derivation survives all the way to accepting the whole input (genuine ambiguity, not just a table conflict that only one branch lived through), the winner is whichever one took the earliest-declared action at its first point of divergence from the others -- the same "first alternative, in file order, wins" convention plain PEG's ordered choice already uses (see Grammar.LRTable.Automaton's action_rank/1, which sorts every conflict cell shift-then-reduce-by-production-id so this comparison means what it says). A grammar with no conflicts anywhere behaves identically to Grammar.LR on the same table.

Only ever runs @engine glr grammars, same as Grammar.LR requires @engine lr and the PEG backends require @engine peg -- the tag is the grammar author's own declared choice of backend.

Summary

Functions

Builds grammar's SLR(1) table -- conflicts are fine here, Grammar.LR.compile/1 is what rejects them.

Matches input against grammar's root, requiring the entire (tokenized) input to be consumed. A bare recognizer -- no Ichor.Actions involved.

Like parse/3, but runs the match through actions_module starting from initial_context, returning the grammar's actual evaluated result.

Types

t()

@type t() :: %Grammar.GLR{
  capture_shapes: Ichor.Actions.capture_shapes(),
  table: Grammar.LRTable.t()
}

Functions

compile(grammar)

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

Builds grammar's SLR(1) table -- conflicts are fine here, Grammar.LR.compile/1 is what rejects them.

parse(grammar, input, context \\ nil)

@spec parse(Aether.Grammar.t(), String.t(), term()) ::
  {:ok, non_neg_integer()} | {:error, Ichor.Error.t() | [Ichor.Error.t()]}

Matches input against grammar's root, requiring the entire (tokenized) input to be consumed. A bare recognizer -- no Ichor.Actions involved.

run(grammar, input, actions_module, initial_context \\ nil)

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

Like parse/3, but runs the match through actions_module starting from initial_context, returning the grammar's actual evaluated result.