Grammar.LRTable (Ichor v0.1.1)

Copy Markdown View Source

Builds an SLR(1) action/goto table from an @engine lr/@engine glr grammar -- shared by both Grammar.LR (which additionally requires the result be conflict-free) and Grammar.GLR (which accepts conflicts and forks over them at runtime).

Pipeline: Grammar.LRTable.Desugar flattens grammar.rules' PEG-shaped IR into a flat CFG production list; Grammar.LRTable.Sets computes nullable/FIRST/FOLLOW over that list; Grammar.LRTable.Automaton builds the canonical LR(0) item-set collection and, on top of it, the SLR(1) action/goto tables. build/1 never itself decides a conflict is fatal -- a cell with more than one action is simply present in action as a list of length > 1; it's each engine's own call whether that's acceptable.

Summary

Types

state_id()
t()

Functions

build(grammar)

Builds the SLR(1) table for grammar, or every unsupported-construct error found.

conflicts(lr_table)

Every {state, symbol, [actions]} cell with more than one action -- a shift/reduce or reduce/reduce conflict.

current_terminal(stream, pos, end_symbol)

The current lookahead terminal name at pos in stream, or end_symbol once input is exhausted -- shared by every LR-family engine (Grammar.LR, Grammar.GLR.Runtime, and generated Grammar.Native.LR/.GLR code alike), interpreted or compiled.

unexpected_error(stream, pos)

The shared "no action applies here" parse error, naming the offending token (or end of input).

Types

state_id()

@type state_id() :: Grammar.LRTable.Automaton.state_id()

t()

@type t() :: %Grammar.LRTable{
  action: %{
    required(state_id()) => %{
      required(atom()) => [Grammar.LRTable.Automaton.action()]
    }
  },
  end_symbol: atom(),
  goto: %{required(state_id()) => %{required(atom()) => state_id()}},
  productions: %{required(non_neg_integer()) => Grammar.LRTable.Production.t()},
  root: atom(),
  start_state: state_id(),
  start_symbol: atom()
}

Functions

build(grammar)

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

Builds the SLR(1) table for grammar, or every unsupported-construct error found.

conflicts(lr_table)

@spec conflicts(t()) :: [{state_id(), atom(), [Grammar.LRTable.Automaton.action()]}]

Every {state, symbol, [actions]} cell with more than one action -- a shift/reduce or reduce/reduce conflict.

current_terminal(stream, pos, end_symbol)

@spec current_terminal(tuple(), non_neg_integer(), atom()) :: atom()

The current lookahead terminal name at pos in stream, or end_symbol once input is exhausted -- shared by every LR-family engine (Grammar.LR, Grammar.GLR.Runtime, and generated Grammar.Native.LR/.GLR code alike), interpreted or compiled.

unexpected_error(stream, pos)

@spec unexpected_error(tuple(), non_neg_integer()) :: Ichor.Error.t()

The shared "no action applies here" parse error, naming the offending token (or end of input).