Grammar.LRTable.Sets (Ichor v0.2.0)

Copy Markdown View Source

Standard textbook nullable/FIRST/FOLLOW fixpoint algorithms, over Grammar.LRTable.Desugar's flat CFG production list rather than the original PEG IR -- recomputed fresh (not reusing Grammar.Analysis's own compute_nullable/1) since the augmented nonterminal set here includes every helper nonterminal a Star/Plus/Opt/Rep/group desugared into, which Grammar.Analysis never sees.

Summary

Functions

first_sets(productions, nullable_set)

FIRST(N) for every nonterminal N -- FIRST of a terminal is just itself, never stored here.

follow_sets(productions, nullable_set, first, start_symbol, end_symbol)

FOLLOW(N) for every nonterminal N. start_symbol's FOLLOW seeds with end_symbol -- the synthetic end-of-input terminal, never a real token.

nullable(productions)

Every nonterminal that can derive the empty string.

Functions

first_sets(productions, nullable_set)

@spec first_sets([Grammar.LRTable.Production.t()], MapSet.t(atom())) :: %{
  required(atom()) => MapSet.t(atom())
}

FIRST(N) for every nonterminal N -- FIRST of a terminal is just itself, never stored here.

follow_sets(productions, nullable_set, first, start_symbol, end_symbol)

@spec follow_sets(
  [Grammar.LRTable.Production.t()],
  MapSet.t(atom()),
  %{required(atom()) => MapSet.t(atom())},
  atom(),
  atom()
) :: %{required(atom()) => MapSet.t(atom())}

FOLLOW(N) for every nonterminal N. start_symbol's FOLLOW seeds with end_symbol -- the synthetic end-of-input terminal, never a real token.

nullable(productions)

@spec nullable([Grammar.LRTable.Production.t()]) :: MapSet.t(atom())

Every nonterminal that can derive the empty string.