LR Parsers

An LR parser is the most popular kind of bottom-up parser. The two letters mean:

Real-world parser generators — yacc, bison, GNU Bison, Java CUP, Menhir — all generate LR parsers. If you have ever used a .y file, you have used an LR parser.

Why LR Is Powerful

The last row is the key. LR waits until it has seen the full right-hand side of a production on the stack before reducing — so it commits only when the evidence is overwhelming.

The LR Family

There are four common variants of LR, in increasing order of power:

They all share the same runtime engine and the same DFA of states. They differ only in how reductions are decided. We will cover the variants in the next three topics — for now, just know they exist.

Before we worry about how to build an LR parser, let's see what the runtime engine looks like. It is surprisingly simple.

The Three Ingredients

The stack starts with the initial state. The parser reads the next input token, looks up ACTION, and performs one of three actions.

The Three Actions

(An empty ACTION cell means syntax error.)

That's it. Whether the parser is SLR, LALR, or CLR, the engine is exactly the same — only the tables change.

A Picture

If we can build those two tables, we have an LR parser. Building them is what the rest of this topic is about.

To build the tables, we need a way to talk about "how much of a production have we matched so far?" That's what an LR item is.

What is an Item?

An item is a production with a dot · showing the current position.

For a production A → B C D, there are four items:

A dot at the end is the signal that a complete handle is on top of the stack.

What is a State?

A state of the parser is a set of items — every production we might currently be in the middle of.

For example, a state might contain:

The parser is always in exactly one state. The state plus the lookahead token uniquely determines the action.

Two Operations Build States

We compute states using CLOSURE and GOTO.

Starting from the augmented start state and applying GOTO on every symbol, we get a DFA whose states are sets of items. That DFA is the backbone of the parse table.

Canonical Items

The complete set of states produced by this process — every reachable set of items — is called the canonical collection of LR(0) items, and each individual state is a canonical item set (often just "canonical items"). When textbooks say "build the canonical collection", they mean exactly this: keep applying CLOSURE and GOTO from the start state until no new states appear.

The same idea, but with lookaheads attached to each item, gives the canonical collection of LR(1) items — which is where the C in CLR (Canonical LR) comes from. We will see that in the CLR topic.

The next section makes all of this concrete with one small grammar — start to finish.

Let's build a pure LR(0) parser end-to-end on a small grammar, explaining every step in detail. LR(0) is the simplest LR variant — it uses no lookahead at all when deciding to reduce.

The Grammar

It generates simple additions of identifiers: id, id + id, id + id + id, and so on.

Small, but interesting:

• E → E + T is left-recursive — something an LL parser cannot handle, but LR can.
• It has multi-symbol reductions (E → E + T has three symbols on the right).
• It has chained single-symbol reductions (id → T → E).
• It is genuinely LR(0): every reduce state in its DFA has no outgoing transitions, so the parser can decide to reduce without any lookahead at all.

Augment the Grammar

Add one extra production at the very top:

Why augment?

The original grammar's start symbol is E. But E appears inside another production (E → E + T), so "we just finished an E" is ambiguous — it could mean "we're done" or "we're about to read a +."

Adding E' → E gives the parser a unique signal for done: we accept only when we have reduced all the way to E'. The dot at the end of this rule (E' → E ·) cannot occur anywhere else, so there's no confusion.

Conventions

• Non-terminals: E', E, T
• Terminals: id, +, $ ($ = end of input)
• Production numbers: r1 = E → E + T, r2 = E → T, r3 = T → id.

We build the DFA by starting with the augmented item E' → · E and applying CLOSURE and GOTO repeatedly until no new states appear.

The grammar has 3 productions, so the DFA is small — only 6 states. Let's build them one at a time.

State I₀ — the start

We always begin with the kernel item E' → · E. The dot at the start means "we haven't parsed anything yet, but we expect to parse an E."

Now apply CLOSURE step by step:

I₀ = { E' → · E, E → · E + T, E → · T, T → · id }

This state means: "we are ready to start parsing an E, in any of its three forms."

Transitions out of I₀

Look at every item in I₀ and note the symbol right after each dot. That tells us which transitions the state has.

So I₀ has three outgoing transitions: on E, on T, and on id. We compute each next.

State I₁ — GOTO(I₀, E)

"What state do we land in if we read an E from I₀?"

Step 1 — take every item in I₀ with the dot before E:

Step 2 — move the dot past E:

Step 3 — apply CLOSURE. In E' → E · the dot is at the end. In E → E · + T the dot is before a terminal (+). Neither needs closure.

I₁ = { E' → E ·, E → E · + T }

Notice: E' → E · is complete — this is the future ACCEPT state.

State I₂ — GOTO(I₀, T)

"What if we read a T from I₀?"

Items with dot before T: E → · T. Move the dot:

CLOSURE: dot at end, nothing to do.

I₂ = { E → T · }

Complete item — reduce-only state.

State I₃ — GOTO(I₀, id)

"What if we read an id from I₀?"

Items with dot before id: T → · id. Move the dot:

I₃ = { T → id · }

Another reduce-only state.

State I₄ — GOTO(I₁, +)

I₁ has E → E · + T, which has the dot before +. So I₁ has one transition: on +.

Take the item, move the dot past +:

Now CLOSURE: dot before T, so add T productions.

T → · id has the dot before terminal id — nothing more to close.

I₄ = { E → E + · T, T → · id }

State I₅ — GOTO(I₄, T)

I₄ has items with dots before T and id. Two outgoing transitions.

Take items with dot before T: E → E + · T. Move:

I₅ = { E → E + T · }

Reduce-only state.

GOTO(I₄, id) — already exists!

Take items with dot before id: T → · id. Move:

This is exactly the same item set as I₃. So we reuse I₃ — no new state is created.

This is important: two transitions can lead to the same state whenever they would produce identical item sets. The DFA is a graph, not a tree.

The Complete DFA — 6 States

Visual Diagram of the DFA

Each box is a state with its items inside. Each arrow is a transition labelled by the symbol that triggers it. Note that I₃ is a single state — both I₀ (on id) and I₄ (on id) point to it.

How to read it:

• Blue — the start state (I₀).
• Cyan — the accept state (I₁, on lookahead $).
• Amber — reduce-only states (I₂, I₃, I₅).
• Arrow labels — the grammar symbol that triggers the transition.

Notice how I₃ has two incoming arrows (from I₀ and from I₄) but is only one node. That is the DFA's signature: identical item sets share a single state.

That's the entire canonical collection. Six states.

Now we turn the DFA into a parse table. Because we are building a pure LR(0) parser, the rule for reductions is very simple:

Whenever a state contains a complete item A → α ·, reduce by A → α on every terminal — no lookahead is consulted.

That is the entire difference between LR(0) and SLR/LALR/CLR. LR(0) reduces "blindly"; the more advanced variants add lookahead to be more selective. No FOLLOW sets are needed here at all.

The Three Table-Filling Rules

Now we apply these rules state by state.

State I₀ — { E' → · E, E → · E + T, E → · T, T → · id }

No complete items, so no reductions. Just shifts and gotos:

State I₁ — { E' → E ·, E → E · + T }

Two items deserve attention here:

• E' → E · is complete and uses the augmented start E'. By Rule 3 we set the accept entry:
  Example

  Copy

  ACTION[1][$] = accept
• E → E · + T has a transition on + to state 4:
  Example

  Copy

  ACTION[1][+] = s4

No conflicts: the accept entry is on $, the shift is on + — different columns.

State I₂ — { E → T · }

Complete item E → T ·. This is production 2 (E → T). By the LR(0) rule we reduce on every terminal:

There are no outgoing transitions from I₂, so reducing blindly is safe.

State I₃ — { T → id · }

Complete item T → id · — production 3 (T → id). Reduce on every terminal:

State I₄ — { E → E + · T, T → · id }

No complete items. Just shifts and gotos:

State I₅ — { E → E + T · }

Complete item E → E + T · — production 1. Reduce on every terminal:

The Complete Parse Table

Reading the table:

• s3 — shift, go to state 3.
• r2 — reduce by production 2 (E → T).
• acc — accept.
• Empty cells — syntax error.

Every cell has at most one entry → no shift/reduce or reduce/reduce conflicts → the grammar is genuinely LR(0).

Why This Worked Without Lookahead

Notice that every reduce state (I₂, I₃, I₅) has no outgoing transitions. The state itself unambiguously says "reduce" — there is no shift to compete with the reduction, so the parser can decide blindly. That is exactly the property that makes a grammar LR(0).

Many real-world grammars are not LR(0). They have states with both a complete item and outgoing terminal transitions — a shift/reduce conflict in LR(0). To resolve those, the parser needs to peek at the next token. That is the lookahead added by SLR(1), LALR(1), and CLR(1), covered in the next three topics.

Now we use the table to parse id + id. The stack starts with just state 0, and the input ends with $.

At each step:

1. Look at the top state of the stack and the next input token.
2. Look up ACTION[state][token] in the table.
3. Do what it says — shift, reduce, or accept.

Mechanics:

• shift t → push the token, then push state t.
• reduce A → β → pop 2 × |β| items, then push A and GOTO[top][A].

The Trace

What Each Step Does

• Step 1 — Shift the first id; the parser enters state 3.
• Step 2 — In state 3 the only item is T → id ·, so reduce T → id. The stack becomes 0 T 2 (because GOTO[0][T] = 2).
• Step 3 — In state 2 we have E → T ·, so reduce E → T. Stack becomes 0 E 1.
• Step 4 — Shift the +. The parser now waits for the right operand.
• Step 5 — Shift the second id, entering state 3 again.
• Step 6 — Reduce T → id again. This time GOTO[4][T] = 5, so the top state becomes 5.
• Step 7 — Multi-symbol reduction: E → E + T pops 6 stack items (3 symbols × 2). The whole expression collapses to a single E.
• Step 8 — Stack holds 0 E 1, input is empty. ACTION[1][$] = acc → accept.

Rightmost Derivation

Reading the reductions in order — T → id, E → T, T → id, E → E + T — and reversing them gives the rightmost derivation of id + id:

Every bottom-up parser produces exactly this: a rightmost derivation, played back in reverse.

We built the table using the SLR(1) rule (reduce on FOLLOW). The other LR variants differ only in how the reduce entries are decided:

Everything else — the DFA construction, the shift entries, the GOTO table, the runtime engine — is identical across all four.

Which One Should You Use?

The next three topics build full parse tables for each variant. SLR(1) continues with this same expression grammar, so you can see it refine the LR(0) table directly. CLR(1) and LALR(1) then switch to a grammar that actually triggers lookahead splitting, since this one is already LR(0) and would hide their differences.