Grammar.LRTable.Automaton (Ichor v0.2.0)

Copy Markdown View Source

Canonical LR(0) item-set construction (closure/goto over Grammar.LRTable.Desugar's flat production list), plus SLR(1) action/goto table construction on top of it.

SLR(1), not full canonical LR(1) or LALR(1) -- a deliberate, simpler choice for a from-scratch v1 (no per-item lookahead propagation graph needed at all): a reduce action for a complete item [A -> α ·] is only offered on a lookahead terminal in FOLLOW(A), computed once over the whole grammar rather than per state. This accepts every LR(0)-unambiguous grammar plus a useful chunk of real ones, at the cost of occasionally reporting a conflict a full LALR(1) table wouldn't -- Grammar.GLR forks on any multi-action cell regardless of why it's there, so a weaker table only means it forks a little more often, never that it parses incorrectly. Strengthening this to true LALR(1) later is a pure internal upgrade (same table shape, smarter lookahead), not a public API change.

Summary

Types

action()
item()
state_id()
t()

Functions

action_goto_tables(automaton, productions, follow, start_symbol, end_symbol)

Builds the SLR(1) action table (%{state => %{terminal => [action]}} -- more than one action in a cell is a conflict, left for the caller to decide whether that's fatal) and goto table (%{state => %{nonterminal => state}}, always single-valued -- goto transitions are deterministic by DFA construction, never a conflict).

build(productions, start_symbol)

Builds the canonical LR(0) collection for productions, starting from start_symbol's own production.

Types

action()

@type action() ::
  {:shift, state_id()} | {:reduce, production_id :: non_neg_integer()} | :accept

item()

@type item() :: {production_id :: non_neg_integer(), dot :: non_neg_integer()}

state_id()

@type state_id() :: non_neg_integer()

t()

@type t() :: %Grammar.LRTable.Automaton{
  start_state: state_id(),
  states: %{required(state_id()) => MapSet.t(item())},
  transitions: %{
    required({state_id(), Grammar.LRTable.Production.symbol()}) => state_id()
  }
}

Functions

action_goto_tables(automaton, productions, follow, start_symbol, end_symbol)

@spec action_goto_tables(
  t(),
  [Grammar.LRTable.Production.t()],
  %{required(atom()) => MapSet.t(atom())},
  atom(),
  atom()
) ::
  {action_table :: %{required(state_id()) => %{required(atom()) => [action()]}},
   goto_table :: %{required(state_id()) => %{required(atom()) => state_id()}}}

Builds the SLR(1) action table (%{state => %{terminal => [action]}} -- more than one action in a cell is a conflict, left for the caller to decide whether that's fatal) and goto table (%{state => %{nonterminal => state}}, always single-valued -- goto transitions are deterministic by DFA construction, never a conflict).

build(productions, start_symbol)

@spec build([Grammar.LRTable.Production.t()], atom()) :: t()

Builds the canonical LR(0) collection for productions, starting from start_symbol's own production.