How to use the SLR(1) Parsing Table Generator
- 1. Type the grammarOne rule per line with | between alternatives. The first rule is the start; the tool adds S' → S.
- 2. Add an inputOptionally type a string like id * id + id. The tool adds $ at the end.
- 3. Read the resultSee item sets with goto moves, FOLLOW sets, the table with any conflicts and the stack trace.
How the SLR(1) table is built
- Augment the grammar with S' → S and build the canonical collection of LR(0) item sets using closure and goto.
- If A → α • a β is in Ii and goto(Ii, a) = Ij, set ACTION[i, a] = shift j.
- If A → α • is in Ii (A ≠ S'), set ACTION[i, b] = reduce A → α for every b in FOLLOW(A).
- If S' → S • is in Ii, set ACTION[i, $] = accept. GOTO entries come from goto on non-terminals.
A cell with two actions is a conflict, and the grammar is not SLR(1).
Worked example (Aho–Ullman expression grammar)
For E → E + T | T, T → T * F | F, F → ( E ) | id there are 12 item sets, I0 to I11. FOLLOW(E) = { +, ), $ } and FOLLOW(T) = FOLLOW(F) = { +, *, ), $ }.
I2 holds E → T • and T → T • * F. LR(0) would have a conflict here, but SLR puts the reduce only under FOLLOW(E), which has no *, so ACTION[2, *] = s7 and ACTION[2, +] = r2. Parsing id * id + id takes 14 steps, as in the Dragon Book.
A grammar that is not SLR(1)
S → L = R | R, L → * R | id, R → L. I2 holds S → L • = R and R → L •. Because = is in FOLLOW(R), ACTION[2, =] gets both shift and reduce. The grammar is not ambiguous; it needs the stronger LALR(1) or canonical LR(1) method.
Frequently asked questions
What is the difference between LR(0) and SLR(1)?
Both use the same LR(0) item sets. LR(0) reduces on every input, while SLR(1) reduces only on terminals in FOLLOW(A), which removes many conflicts.
What do s5 and r2 mean?
s5 means shift the token and go to state 5. r2 means reduce by production 2 of the numbered grammar.
How does the trace handle a conflict?
It prefers shift on a shift/reduce conflict, like yacc does, and says so above the trace.
Can I use ε-productions?
Yes. Write ε, eps or # for the empty string. A → • is a complete item, so it reduces on FOLLOW(A).