Chapter 14 of 33

LR(0) Items & LR(0) Parsing

In Bottom-Up Parsing & Shift-Reduce Parsing we traced shift-reduce parsers with an "oracle" that always knew whether to shift or reduce. LR parsers replace that oracle with a finite automaton. The automaton keeps track of which productions might be partly matched on the stack, so at every step it knows whether a complete handle is sitting on top.

LR(0) is the simplest member of the LR family. Its states are built from LR(0) items, and the very same item sets are reused by SLR and LALR parsers. Learn to build them quickly and accurately, and the next three chapters become much easier.

An LR(0) parser is a shift-reduce parser driven by a DFA whose states are sets of LR(0) items. It reads input Left to right, builds a Rightmost derivation in reverse, and uses 0 tokens of lookahead when deciding to reduce: in a state containing a complete item A → β•, it reduces by A → β whatever the next token is.


The LR Parser Model

Every LR parser (LR(0), SLR, LALR, CLR) has the same structure. Only the table changes.

Input:  a1  a2  ...  ai  ...  an  $
                     ▲
                     │
 Stack        ┌──────┴───────┐
 ┌─────┐      │  LR parsing  │ ──▶ Output (the reductions)
 │ s_m │◀────▶│   program    │
 │ X_m │      └──────┬───────┘
 │ ... │             │
 │ s_0 │      ┌──────┴───────┐
 └─────┘      │ ACTION  GOTO │  ← the parsing table
              └──────────────┘

The stack holds states (and, for readability, the grammar symbols between them). The state on top summarizes everything the parser needs to know about the stack below it. The table has two parts:

  • ACTION[s, a], for state s and terminal a (or $): one of shift j (written sj), reduce by production k (rk), accept, or error (blank).

  • GOTO[s, A], for non-terminal A: the state to go to after a reduction to A.

The driver loop, with s = top state and a = current token:

if ACTION[s, a] = shift j:   push a and j; advance the input
if ACTION[s, a] = reduce A → β:
       pop |β| symbols and |β| states   (2·|β| items if symbols are stored too)
       let t be the state now on top; push A and GOTO[t, A]
       output A → β
if ACTION[s, a] = accept:    stop, the input is a sentence
if ACTION[s, a] is blank:    report a syntax error

So building an LR parser means building this table. For that we need items.


LR(0) Items

An LR(0) item is a production with a dot (•) somewhere in its right side. The dot marks how much of the right side has already been seen (is on the stack).

The production A → X Y Z gives four items:

A → • X Y Z     we hope to see X Y Z next; nothing of it seen yet
A → X • Y Z     X has been seen; Y Z expected
A → X Y • Z     X Y seen; Z expected
A → X Y Z •     the whole right side is on the stack: ready to reduce

A production A → ε gives just one item, A → •, which is already complete. In general a production with n symbols on the right gives n + 1 items.

Term

Meaning

Complete (final) item

Dot at the right end, e.g. A → X Y Z •. Signals a possible reduction.

Kernel item

The initial item S' → • S, plus every item whose dot is not at the left end.

Non-kernel item

An item with the dot at the left end (other than S' → • S). These are always added by closure, so they can be recomputed from the kernel.


The Augmented Grammar

Before building items we add a new start symbol S' and a production S' → S. This augmented grammar gives the parser one clear moment to accept: when it is about to reduce by S' → S and the input is at $. Without it, reducing to S could happen in the middle of the input too (if S appears in right sides), and the parser could not tell when it is really done.


CLOSURE and GOTO

CLOSURE

If an item A → α • B β is in a state, the parser is expecting to see something derived from B next. So it must also be ready to start any production of B. CLOSURE adds those items:

  1. Start with the given items.

  2. If A → α • B β is in the set and B → γ is a production, add B → • γ (if it is not there yet).

  3. Repeat step 2 until nothing new can be added.

Example with the expression grammar (augmented with E' → E):

CLOSURE({ E' → • E }):
  E' → • E          start
  E  → • E + T      dot before E, add E's productions
  E  → • T
  T  → • T * F      dot before T, add T's productions
  T  → • F
  F  → • ( E )      dot before F, add F's productions
  F  → • id

One kernel item became 7 items. Note that E → • E + T does not add anything new (E's productions are already there), which is how closure stops on left recursion.

GOTO

GOTO(I, X) is the state the parser moves to from state I after seeing grammar symbol X (either shifting terminal X or reducing to non-terminal X):

  1. Take every item in I with the dot immediately before X: A → α • X β.

  2. Move the dot past X: A → α X • β. These are the kernel items of the new state.

  3. Take the CLOSURE of that set.

For example, with I = the 7 items above, GOTO(I, T) starts from E → T • and T → T • * F. Neither has the dot before a non-terminal, so the closure adds nothing: the new state is exactly those two items.


Building the Canonical Collection of LR(0) Items

The states of the LR(0) automaton are found by a simple worklist algorithm:

I0 = CLOSURE({ S' → • S })
C  = { I0 }
repeat
    for each state I in C, and each grammar symbol X that appears right after a dot in I:
        J = GOTO(I, X)
        if J is not already in C: add J to C (give it the next number)
        record the transition I --X--> J
until no new states are added

About state numbering. The numbers themselves do not matter, but exams expect the usual order: process states in the order they were created (I0, I1, I2, …), and inside each state take the symbols in the order they appear after the dot, reading the items from top to bottom. A new state gets the next free number. This is the numbering used in this chapter and in most textbooks.

Worked Example 1: S → AA, A → aA | b

The augmented grammar, with productions numbered for the table:

0.  S' → S
1.  S  → A A
2.  A  → a A
3.  A  → b

Step by step:

  • I0 = CLOSURE({S' → • S}). The dot is before S, so add S → • A A. Now the dot is before A, so add A → • a A and A → • b.

  • Symbols after the dot in I0, in order: S, A, a, b. GOTO(I0, S) = { S' → S • } = I1. GOTO(I0, A) = closure of { S → A • A } = I2 (the dot is before A again, so A's items are added). GOTO(I0, a) = closure of { A → a • A } = I3. GOTO(I0, b) = { A → b • } = I4.

  • I1 has no transitions. From I2: on A we get { S → A A • } = I5; on a and b we get the same sets as before, so I3 and I4 again.

  • From I3: on A we get { A → a A • } = I6; on a we get closure of { A → a • A }, which is I3 itself (a self-loop); on b we get I4.

  • I4, I5 and I6 have no transitions. Done: 7 states.

I0:  S' → • S
     S → • A A
     A → • a A
     A → • b
     goto: S→I1, A→I2, a→I3, b→I4

I1:  S' → S •
     (no transitions)

I2:  S → A • A
     A → • a A
     A → • b
     goto: A→I5, a→I3, b→I4

I3:  A → a • A
     A → • a A
     A → • b
     goto: A→I6, a→I3, b→I4

I4:  A → b •
     (no transitions)

I5:  S → A A •
     (no transitions)

I6:  A → a A •
     (no transitions)

The LR(0) automaton as transitions:

I0 --S--> I1      I2 --A--> I5      I3 --A--> I6
I0 --A--> I2      I2 --a--> I3      I3 --a--> I3   (self-loop)
I0 --a--> I3      I2 --b--> I4      I3 --b--> I4
I0 --b--> I4

Final-item states:  I1 (accept), I4 (A → b •), I5 (S → A A •), I6 (A → a A •)

Constructing the LR(0) Parsing Table

For each state Ii:

  1. If GOTO(Ii, a) = Ij for a terminal a: ACTION[i, a] = shift j.

  2. If GOTO(Ii, A) = Ij for a non-terminal A: GOTO[i, A] = j.

  3. If a complete item A → α • (with A ≠ S') is in Ii: ACTION[i, a] = reduce A → α for every terminal a and for $. This is the "0 lookahead" part: the decision ignores the next token.

  4. If S' → S • is in Ii: ACTION[i, $] = accept.

  5. All other entries are errors.

For our grammar (sj = shift and go to state j, rk = reduce by production k). The a, b and $ columns form the ACTION part; the S and A columns form the GOTO part:

State

a

b

$

S

A

I0

s3

s4

1

2

I1

acc

I2

s3

s4

5

I3

s3

s4

6

I4

r3

r3

r3

I5

r1

r1

r1

I6

r2

r2

r2

Each reduce state fills its entire ACTION row with the same reduction; that is the visual signature of an LR(0) table. There are 6 shift entries and 9 reduce entries, and no cell holds two actions, so the grammar is LR(0).


Parsing a String: a a b b

The stack shows states with the grammar symbols between them; the top is on the right.

Step

Stack (states and symbols)

Input

Action

1

0

a a b b $

shift a, push 3

2

0 a 3

a b b $

shift a, push 3

3

0 a 3 a 3

b b $

shift b, push 4

4

0 a 3 a 3 b 4

b $

reduce by A → b; GOTO[3, A] = 6

5

0 a 3 a 3 A 6

b $

reduce by A → a A; GOTO[3, A] = 6

6

0 a 3 A 6

b $

reduce by A → a A; GOTO[0, A] = 2

7

0 A 2

b $

shift b, push 4

8

0 A 2 b 4

$

reduce by A → b; GOTO[2, A] = 5

9

0 A 2 A 5

$

reduce by S → A A; GOTO[0, S] = 1

10

0 S 1

$

accept

Look at step 5. The stack is 0 a 3 a 3 A 6 and state 6 says "reduce by A → a A". The right side has 2 symbols, so the parser pops two symbol-state pairs (A 6 and a 3), uncovering state 3. Then GOTO[3, A] = 6, so it pushes A and 6 again. The reductions, read from the bottom up, give the rightmost derivation S ⇒ A A ⇒ A b ⇒ a A b ⇒ a a A b ⇒ a a b b.

For an invalid string such as a b a, the parser reaches state 3 with stack 0 A 2 a 3 and next token $. ACTION[3, $] is blank, so it reports an error immediately: an A must still follow, but the input has ended.


Viable Prefixes: What the Automaton Recognizes

A viable prefix is a prefix of a right-sentential form that does not continue past the right end of the handle of that form. These are exactly the strings of grammar symbols that can appear on the stack of a shift-reduce parser.

The key theorem behind LR parsing: the set of viable prefixes is a regular language, and the LR(0) automaton recognizes it. Following the transitions with the symbols on the stack always ends in a valid state, and the items in that state tell you which productions could be in progress.

  • a a A is a viable prefix: I0 → a → I3 → a → I3 → A → I6. State I6 contains A → a A •, so the handle a A is on top.

  • A A a is not: I0 → A → I2 → A → I5, and I5 has no transition on a. Once A A is on the stack, the handle is complete and must be reduced; nothing can be shifted on top of it.

This is why the parser never needs to re-scan the stack: the state on top already encodes the automaton's run over the whole stack.


Conflicts in LR(0)

A grammar is LR(0) if its LR(0) table has no multiply-defined entries. A state causes a conflict when:

Conflict

The state contains

Why it is a conflict

Shift/reduce

a complete item A → α • and an item B → β • a γ with a terminal after the dot

The reduce fills the whole row, including column a, where the shift also wants to go.

Reduce/reduce

two different complete items A → α • and B → β •

Both reductions fill the whole row.

A state with only a complete item and items whose dot is before a non-terminal has no conflict, because non-terminals appear in the GOTO part, not in ACTION. The state containing S' → S • is also normally not counted as a conflict, since accept is placed only in the $ column.

Worked Example 2: The Expression Grammar Is Not LR(0)

0. E' → E     1. E → E + T     2. E → T     3. T → T * F
4. T  → F     5. F → ( E )     6. F → id

The canonical collection has 12 states:

I0:  E' → • E
     E → • E + T
     E → • T
     T → • T * F
     T → • F
     F → • ( E )
     F → • id
     goto: E→I1, T→I2, F→I3, (→I4, id→I5

I1:  E' → E •
     E → E • + T
     goto: +→I6

I2:  E → T •
     T → T • * F
     goto: *→I7

I3:  T → F •
     (no transitions)

I4:  F → ( • E )
     E → • E + T
     E → • T
     T → • T * F
     T → • F
     F → • ( E )
     F → • id
     goto: E→I8, T→I2, F→I3, (→I4, id→I5

I5:  F → id •
     (no transitions)

I6:  E → E + • T
     T → • T * F
     T → • F
     F → • ( E )
     F → • id
     goto: T→I9, F→I3, (→I4, id→I5

I7:  T → T * • F
     F → • ( E )
     F → • id
     goto: F→I10, (→I4, id→I5

I8:  F → ( E • )
     E → E • + T
     goto: )→I11, +→I6

I9:  E → E + T •
     T → T • * F
     goto: *→I7

I10: T → T * F •
     (no transitions)

I11: F → ( E ) •
     (no transitions)

Two states are in trouble:

  • I2 = { E → T •, T → T • * F }. LR(0) puts "reduce 2" in every column, including *, but the second item wants to shift *. Shift/reduce conflict on *.

  • I9 = { E → E + T •, T → T • * F }. Same story: reduce 1 vs shift 7 on *.

I1 = { E' → E •, E → E • + T } is fine: accept goes only under $, the shift under +.

So this unambiguous grammar is not LR(0). The fix is obvious once you see it: in I2, reduce E → T only if the next token can actually follow an E (that is, +, ) or $), never on *. Using FOLLOW sets like this is exactly what SLR Parsing does, with the same 12 states.

Worked Example 3: A Reduce/Reduce Conflict

0. S' → S     1. S → A c     2. S → B d     3. A → a     4. B → a
I0:  S' → • S
     S → • A c
     S → • B d
     A → • a
     B → • a
     goto: S→I1, A→I2, B→I3, a→I4

I1:  S' → S •
     (no transitions)

I2:  S → A • c
     goto: c→I5

I3:  S → B • d
     goto: d→I6

I4:  A → a •
     B → a •
     (no transitions)

I5:  S → A c •
     (no transitions)

I6:  S → B d •
     (no transitions)

State I4 contains both A → a • and B → a •. Both reductions fill the entire row:

State

a

c

d

$

S

A

B

I0

s4

1

2

3

I1

acc

I2

s5

I3

s6

I4

r3 / r4

r3 / r4

r3 / r4

r3 / r4

I5

r1

r1

r1

r1

I6

r2

r2

r2

r2

(Columns a, c, d and $ are ACTION; S, A and B are GOTO.) Every ACTION column of I4 has r3 / r4, so the grammar is not LR(0). The language is just { ac, ad }, and one token of lookahead (c or d) would settle the choice. LR(0) simply refuses to look.


Quick Facts About LR(0)

  • The number of LR(0) states depends only on the grammar, and SLR and LALR parsers use the same number of states as LR(0).

  • Every LR(0) grammar is unambiguous, and is also SLR(1), LALR(1) and LR(1).

  • An ε-production does not automatically cause a conflict. For S → A a, A → ε, state I0 contains A → • together with items whose dot is before S or A only, so there is nothing to shift and no conflict. But for S → a S | ε, I0 contains S → • and S → • a S, which gives a shift/reduce conflict on a.

  • Few practical grammars are LR(0). Its real value is as the foundation: the same item sets, with better lookahead rules, give SLR and LALR parsers.


Common Mistakes

  • Forgetting to augment the grammar. Without S' → S there is no single accept item.

  • Stopping closure too early. After adding B → • C δ, you must also add C's productions. Keep going until nothing changes.

  • Applying closure to the old state instead of the new kernel. GOTO(I, X) = CLOSURE of the moved items only.

  • Creating duplicate states. Before numbering a new state, compare it with all existing states (comparing kernels is enough). In Example 1, GOTO(I3, a) is I3 itself.

  • Putting reduce entries only under FOLLOW. That is SLR. In LR(0), a reduce fills the whole ACTION row.

  • Popping the wrong amount. A reduction by A → β pops |β| states (2|β| entries if symbols are also stored). A → ε pops nothing.

  • Counting a dot-before-non-terminal item as a shift conflict. Only terminals after the dot create shift actions.


GATE & Interview Questions

Q1. How many states does the LR(0) automaton of S → AA, A → aA | b have (augmented grammar)?

7 (I0 to I6), as constructed above. SLR(1) and LALR(1) parsers for this grammar also have 7 states.

Q2. How many items are in CLOSURE({E' → •E}) for E → E + T | T, T → T * F | F, F → (E) | id?

7: E' → •E, E → •E+T, E → •T, T → •T*F, T → •F, F → •(E), F → •id.

Q3. Which states of the expression grammar's LR(0) automaton have conflicts, and what kind?

I2 {E → T•, T → T•*F} and I9 {E → E+T•, T → T•*F}. Both are shift/reduce conflicts on *. There is no reduce/reduce conflict.

Q4. Is S → Ac | Bd, A → a, B → a an LR(0) grammar?

No. GOTO(I0, a) = {A → a•, B → a•} gives a reduce/reduce conflict. (It is SLR(1), because FOLLOW(A) = {c} and FOLLOW(B) = {d} are disjoint.)

Q5. How many LR(0) items does the production A → XYZ give? And A → ε?

A → XYZ gives 4 (dot in each of 4 positions). A → ε gives 1, the item A → •.

Q6. Is S → aABe, A → Abc | b, B → d LR(0)?

Yes. Its automaton has 10 states, and every state with a complete item contains only that one item (A → b•, B → d•, A → Abc•, S → aABe•, S' → S•), so there are no conflicts.

Q7. In the LR(0) table for S → AA, A → aA | b, how many reduce entries are there?

States I4, I5 and I6 are reduce states, and each fills all 3 ACTION columns (a, b, $): 9 reduce entries. There are 6 shift entries and 1 accept entry.

Q8. Does the grammar S → aS | ε have an LR(0) conflict?

Yes. I0 = {S' → •S, S → •aS, S → •}. The complete item S → • reduces on every column, including a, where S → •aS shifts. Shift/reduce conflict.

Q9. What is a viable prefix, and why does it matter?

A prefix of a right-sentential form that does not extend past the end of its handle; exactly the possible stack contents of a shift-reduce parser. The set of viable prefixes is regular, and the LR(0) automaton is a DFA for it. That is why a finite set of states is enough to find every handle.


Summary

  • An LR parser is a shift-reduce parser driven by a table with ACTION (shift, reduce, accept, error) and GOTO parts; its stack holds states.

  • An LR(0) item is a production with a dot showing how much has been seen. A → XYZ has 4 items; A → ε has one, A → •.

  • Augment the grammar with S' → S, then build states with CLOSURE (add B → •γ for every dot before B) and GOTO (move the dot over X, then close).

  • The canonical collection is built with a worklist; number states in order of creation. S → AA, A → aA | b has 7 states; the expression grammar has 12.

  • LR(0) table: shifts from terminal transitions, GOTO from non-terminal transitions, a complete item reduces in every column, and S' → S• accepts on $.

  • A grammar is LR(0) if no cell has two actions. Shift/reduce conflicts come from a complete item next to a dot-before-terminal; reduce/reduce from two complete items.

  • The LR(0) automaton recognizes viable prefixes. LR(0) ignores lookahead, which is too weak for most grammars. The next chapter, SLR Parsing, keeps the same states but reduces only on FOLLOW tokens.