slr8

Takes a grammar and a sentence and walks through SLR(1) parsing: augmented
grammar, FIRST/FOLLOW, canonical LR(0) items, the DFA, the ACTION/GOTO
table, a shift-reduce trace, the parse tree. All computed in Typst, no
external script generating a table beforehand.

It's SLR(1) — LR(0) item sets, but reduce actions only go in when the
symbol's in FOLLOW(LHS). That's the whole difference from plain LR(0).

See example.pdf for what it looks like end to end on:

C → id ( A )
A → A , E | ε | E
E → E + T | T
T → id | num | C

parsing id ( num + id , id ( num + id ) ).

Using it

#import "@preview/slr8:0.0.1": *

#let my-grammar = (
  ("C", ("id", "(", "A", ")")),
  ("A", ("A", ",", "E")),
  ("A", ("\\epsilon",)),
  ("A", ("E",)),
  ("E", ("E", "+", "T")),
  ("E", ("T",)),
  ("T", ("id",)),
  ("T", ("num",)),
  ("T", ("C",)),
)

#let my-sentence = ("id", "(", "num", "+", "id", ",", "id", "(", "num", "+", "id", ")", ")")

#show-grammar(my-grammar)
#show-parse-table(my-grammar)
#show-parse-trace(my-grammar, my-sentence)
#show-parse-tree(my-grammar, my-sentence)

A grammar is just a list of (LHS, RHS) pairs, RHS being a tuple of
symbols. First production's LHS = start symbol. Anything that's not a LHS
anywhere is a terminal. "\\epsilon" for empty productions. Don't use "."
as a symbol — it's the LR item dot internally and things will break in
confusing ways if it collides.

A sentence is just the terminals, no $ at the end, that gets added for
you.

What each function gives you

show-grammar / show-aug-grammar — the production list, plain or with the
S' → S row added.

show-first-follow — FIRST/FOLLOW per non-terminal.

show-canonical-items — every I_n state, with where it came from.

show-automaton(grammar, width: 100%) — the LR(0) DFA, rendered via
diagraph/Graphviz.

show-parse-table — ACTION/GOTO, conflicts called out in red if there are
any.

show-parse-trace / show-parse-tree — take (grammar, sentence), give
you the stack-by-stack trace and the resulting tree.

All of them take the grammar before augmentation — that part's handled
for you.

Known gaps

• SLR(1) conflict resolution, not LALR/LR(1) — if your grammar genuinely
  needs per-state lookahead to be unambiguous, you'll see conflicts here
  even though a stronger parser wouldn't have any.
• FIRST-set computation only skips direct left recursion (A → A α).
  Indirect left recursion through another non-terminal isn't handled.
• When there's a real shift/reduce or reduce/reduce conflict, whichever
  action got inserted first wins — there's no precedence/associativity
  table backing this, it's reported and left at that.