Drawtomata / SLR, CLR and LALR parsing table generator
SLR, CLR and LALR parsing table generator
Type a grammar above and choose LR(0), SLR(1), CLR(1) or LALR(1). Drawtomata builds the canonical collection of items, draws the automaton, fills in ACTION and GOTO, marks every conflict and traces a shift-reduce parse.
Which table is which
- LR(0): reduce on every terminal whenever an item A → α· is complete.
- SLR(1): same LR(0) items, but reduce A → α only on the terminals in FOLLOW(A).
- CLR(1): LR(1) items carry a lookahead, and A → α· [a] reduces only on a. Most powerful, most states.
- LALR(1): merge LR(1) states with the same core. As many states as SLR, almost the power of CLR. This is what yacc builds.
Conflicts
A shift-reduce conflict means a cell asks for both a shift and a reduce; a reduce-reduce conflict means two reductions. Ambiguous expression grammars can be fixed with yacc-style %left and %right precedence, which the tool applies when you tick the box.
Classic examples
S → CC, C → cC | d is LR(0) and so in every class. S → L = R | R, L → *R | id, R → L is LALR(1) but not SLR(1). Both are in the example list above.