ToolSphere

LR Parser (LR(0), SLR, LALR, CLR)

Computer science

Build LR(0) or LR(1) item sets and the ACTION/GOTO table for LR(0), SLR(1), LALR(1) or canonical LR(1), see every conflict explained, and trace a parse.

Type a grammar and a token string to build the selected LR table and follow its parse trace.

Accepted: the input matches this grammar.

Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

Table type
Operator precedence for ambiguous grammars (optional)

One line per level, lowest first, as in yacc: %left groups a + b + c as (a + b) + c, %right groups to the right, %nonassoc makes a < b < c an error. Shift/reduce conflicts are settled by these; the rest stay.

Is it SLR(1)?

No conflicts: this grammar is SLR(1).

Numbered productions

  1. r0E' → E(added start rule)
  2. r1E → E + T
  3. r2E → T
  4. r3T → T * F
  5. r4T → F
  6. r5F → ( E )
  7. r6F → id

Test a string

Accepted in 14 steps

StepStackInputAction
10id * id + id $Shift id, go to state 5
20 id 5* id + id $Reduce by F → id (r6)
30 F 3* id + id $Reduce by T → F (r4)
40 T 2* id + id $Shift *, go to state 7
50 T 2 * 7id + id $Shift id, go to state 5
60 T 2 * 7 id 5+ id $Reduce by F → id (r6)
70 T 2 * 7 F 10+ id $Reduce by T → T * F (r3)
80 T 2+ id $Reduce by E → T (r2)
90 E 1+ id $Shift +, go to state 6
100 E 1 + 6id $Shift id, go to state 5
110 E 1 + 6 id 5$Reduce by F → id (r6)
120 E 1 + 6 F 3$Reduce by T → F (r4)
130 E 1 + 6 T 9$Reduce by E → E + T (r1)
140 E 1$Accept

FOLLOW sets (where SLR(1) places reduces)

Non-terminalFOLLOW
E{ $, +, ) }
T{ $, +, *, ) }
F{ $, +, *, ) }

SLR(1) parsing table

sN = shift and go to state N · rN = reduce by production N · acc = accept

StateACTIONGOTO
+*()id$ETF
0s4s5123
1s6acc
2r2s7r2r2
3r4r4r4r4
4s4s5823
5r6r6r6r6
6s4s593
7s4s510
8s6s11
9r1s7r1r1
10r3r3r3r3
11r5r5r5r5

Canonical LR(0) item sets (12 states)

I0
  • E' → • E
  • E → • E + T
  • E → • T
  • T → • T * F
  • T → • F
  • F → • ( E )
  • F → • id
on E → I1on T → I2on F → I3on ( → I4on id → I5
I1
  • E' → E •
  • E → E • + T
on + → I6
I2
  • E → T •
  • T → T • * F
on * → I7
I3
  • T → F •
I4
  • F → ( • E )
  • E → • E + T
  • E → • T
  • T → • T * F
  • T → • F
  • F → • ( E )
  • F → • id
on E → I8on T → I2on F → I3on ( → I4on id → I5
I5
  • F → id •
I6
  • E → E + • T
  • T → • T * F
  • T → • F
  • F → • ( E )
  • F → • id
on T → I9on F → I3on ( → I4on id → I5
I7
  • T → T * • F
  • F → • ( E )
  • F → • id
on F → I10on ( → I4on id → I5
I8
  • F → ( E • )
  • E → E • + T
on ) → I11on + → I6
I9
  • E → E + T •
  • T → T • * F
on * → I7
I10
  • T → T * F •
I11
  • F → ( E ) •

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use LR Parser (LR(0), SLR, LALR, CLR)

  1. 1Paste your grammar, one rule per line, or load an example.
  2. 2Choose LR(0), SLR(1), LALR(1) or CLR / LR(1) to build the ACTION/GOTO parsing table and see any conflicts.
  3. 3Type an input string to trace the shift-reduce parse, and inspect the item sets below it (LR(1) items show their lookaheads, as [A → α • β, a/b]).

About LR Parser (LR(0), SLR, LALR, CLR)

LR(0) Parsing and Canonical Item Sets

LR parsers read input left-to-right and build a rightmost derivation in reverse — a bottom-up parsing strategy used by many real compiler-generator tools (like yacc/bison), in contrast to the top-down approach LL parsers use. Building an LR(0) parser starts with augmenting the grammar with a new start symbol, then computing the canonical collection of item sets: each item set tracks which productions could be "in progress" at a given parsing state, marked with a dot showing how far into the production the parser has read.

The closure operation expands an item set by adding new items whenever the dot sits before a non-terminal — since that non-terminal's own productions could now also be starting. GOTO transitions connect item sets together based on which symbol is consumed, forming the parsing automaton's state graph, which ultimately becomes the parsing table an actual parser implementation would use to decide shift/reduce actions.

This is genuinely intricate to trace by hand for anything beyond a toy grammar, which is exactly why automating the construction — closure, GOTO, and the resulting state table — matters for verifying compiler-construction coursework.

LR(0) vs SLR(1)

Both tables are built from the same canonical collection of LR(0) item sets; they differ only in where reduce actions go. LR(0) puts a reduce in every column of a state that holds a completed item, while SLR(1) only puts the reduce for A → α under the terminals in FOLLOW(A). That one change resolves many conflicts.

Worked example

The expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id has 12 LR(0) states. As an LR(0) table it has two shift/reduce conflicts on *, in the states holding E → T • and E → E + T •, which also hold T → T • * F. SLR(1) resolves both because * is not in FOLLOW(E) = { +, ), $ }, so the grammar is SLR(1) and id * id + id parses successfully.

The grammar S → L = R | R, L → * R | id, R → L is the textbook case that is not SLR(1): "=" is in FOLLOW(R), so one state gets a shift/reduce conflict on "=". It needs LALR(1) or canonical LR(1) lookaheads.

Reading a conflict

Every conflict lists the items behind it. On that grammar the tool shows state 2 on "=": a shift because of S → L • = R, and a reduce by R → L because R → L • is complete and = ∈ FOLLOW(R). In LR(0) mode it also says when SLR(1) would resolve the conflict, which is the usual exam question: "is this grammar LR(0)? Is it SLR(1)?"

LALR(1) and canonical LR(1)

Canonical LR(1) (CLR) items carry a lookahead: [A → α • β, a] means "after recognising α β, reduce only if the next token is a". The closure of [A → α • B β, a] adds [B → • γ, b] for every b in FIRST(β a), so each item knows exactly which tokens may follow it, rather than the whole FOLLOW set SLR(1) uses. That is why S → L = R | R is LR(1): the item R → L • only has "=" as a lookahead where an "=" can really follow.

The price is size. LALR(1) keeps LR(1) lookaheads but merges states with the same core (the same items ignoring lookaheads), so it always has as many states as LR(0). It is what yacc and bison build. The textbook grammar S → C C, C → c C | d shows the difference: 10 canonical LR(1) states, merged into 7 LALR(1) states, both conflict-free.

Merging can occasionally create a reduce/reduce conflict that canonical LR(1) does not have. Load the example "LR(1) but not LALR(1)" (S → a A d | b B d | a B e | b A e, A → c, B → c): LR(1) parses it, LALR(1) gets a reduce/reduce conflict between A → c and B → c, and the tool says the merge caused it. The four table types form a ladder, each accepting more grammars: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1).

Where this fits

SLR(1) relies on the FOLLOW sets from the FIRST and FOLLOW calculator; LALR(1) and CLR(1) compute their own lookaheads. For the top-down alternative, and to see why left recursion breaks it, compare with the LL(1) parser. Once a parser accepts the input, the next compiler phase turns it into intermediate code: see the three-address code generator.

Guides and tutorials

student

LR(1) vs LALR(1) Parsing and Conflicts

Learn how LR(1) items work, how LALR(1) merges identical cores, and why state merging causes reduce/reduce conflicts that LR(1) avoids, with worked tables.

Read guide →
student

Yacc Precedence and Associativity Explained

Resolve every expression-grammar shift/reduce conflict with left, right and nonassoc declarations, using generated LR decisions and parse traces.

Read guide →
student

LALR and CLR Parsing Table Worked Example

Build canonical LR(1) items, merge ten states into seven LALR states, read both tables, and see why an assignment grammar is LALR but not SLR.

Read guide →
student

SLR Parsing Table Example With LR(0) Items

Build the canonical LR(0) items and the SLR(1) parsing table for the expression grammar, see why LR(0) has conflicts, and trace a parse of id * id + id.

Read guide →
student

Compiler Bootstrapping and Error Recovery

Learn compiler bootstrapping, cross-compilers and T-diagrams, then compare syntax-error recovery methods with computed LL(1) and LR traces.

Read guide →
student

Ambiguous Grammar Examples With Parse Trees

See generated ambiguity witnesses, two parse trees and leftmost derivations for expressions, dangling else and a recursive equal-count grammar.

Read guide →
student

Operator Precedence Parsing: Worked Example

Build LEADING/TRAILING sets, a precedence table and f/g functions, then follow a generated shift-reduce trace for id + id * id.

Read guide →
student

Left Recursion and Left Factoring Examples

Worked direct and indirect left-recursion removal, left factoring and LL(1) tables, including why factoring dangling else does not remove its conflict.

Read guide →

Frequently asked questions

How do I build an LR table for an ambiguous grammar like E -> E + E | E * E?

Open the operator precedence box and declare the operators as yacc does, lowest first: %left + on one line, %left * on the next, %right ^ for powers. Each shift/reduce conflict is then settled by precedence and associativity, the tool lists how every one was settled, and the parse groups id + id * id as id + (id * id). The grammar itself stays ambiguous.

What does the dot in an LR item actually represent?

It marks how far the parser has progressed through a production's right-hand side — symbols before the dot have been matched, symbols after it are still expected.

Why does closure only expand items where the dot precedes a non-terminal?

Because only a non-terminal has its own productions that could start being parsed from that point — a dot before a terminal just means the parser needs to shift that specific symbol next, with no further items to add.

Is LR(0) parsing used in real compilers?

Directly, rarely — most practical parser generators use more powerful variants (SLR, LALR, or full LR(1)) that resolve more grammars without conflicts, but LR(0) is the foundational construction those variants build on.

What is the difference between a shift-reduce and a reduce-reduce conflict?

In a shift-reduce conflict one table cell says both "shift the next token" and "reduce by a rule"; in a reduce-reduce conflict two different rules could be reduced. Either one means the grammar is not LR(0) or SLR(1) as built, and the tool highlights the conflicting cells.

Can an LR parser handle left-recursive grammars?

Yes. Unlike LL(1), LR parsers handle left recursion naturally, so the expression grammar E → E + T | T works as written.

What is the difference between LALR(1) and CLR(1)?

Both use LR(1) items with lookaheads. Canonical LR(1) keeps every distinct set of items as its own state; LALR(1) merges states whose items are the same apart from lookaheads, giving the same number of states as LR(0). LALR(1) tables are much smaller, and the merge only rarely causes a reduce/reduce conflict that CLR(1) avoids.

How do I check whether a grammar is LALR(1)?

Choose LALR(1) and look at the conflict count. If it is zero, the grammar is LALR(1). If there is a conflict, switch to CLR / LR(1): if that one is conflict-free, the grammar is LR(1) but not LALR(1); if it still conflicts, the grammar is not LR(1) and is usually ambiguous.

How are LR(1) lookaheads computed?

Start with [S' → • S, $]. When closing an item [A → α • B β, a], add [B → • γ, b] for every production of B and every terminal b in FIRST(β a). If β can derive ε, the lookahead a itself is carried down. GOTO moves the dot and keeps each item's lookahead.

How do I find which items cause a shift-reduce conflict?

Look at the state with the conflict: the shift comes from an item with the dot before the terminal (A → α • a β), and the reduce from a complete item (B → γ •) whose lookahead includes that terminal. The tool prints both items for every conflict.

Have a suggestion for LR Parser (LR(0), SLR, LALR, CLR)?Share your feedback ↗