LR(0) Parser Explained: Bottom-Up Parsing, Item Sets and a Worked Example

Bottom-up parsing sounds intuitive until dots, item sets, ACTION/GOTO entries and stack reductions appear together. Then one changed state number can invalidate the entire solution. The construction runs from the augmented grammar through closure, GOTO, a seven-state LR(0) automaton, the complete parsing table and acceptance of cdd$. Each shift, reduction and GOTO in that trace follows from one table cell, and each table cell follows from one item set, so a wrong state number is always traceable to the exact item set that produced it.

Related reading: top-down and bottom-up parsing and parsing MCQs.

Bottom-up parsing means finding handles in reverse

Bottom-up parsing starts with the input and reduces handles until only the start symbol remains. A handle matches the production used in one step of a rightmost derivation. It is not an arbitrary match: the viable prefix and parser state decide whether it is legal.

The parsing table can prescribe four outcomes:

• shift j: consume the next terminal and push it with state j.

• reduce A -> beta: pop 2 x |beta| interleaved entries, then push A and GOTO[top,A].

• accept: succeed only for the completed augmented item with $.

• error: no legal action exists.

For our input, the rightmost derivation is S => C C => C d => c C d => c d d. The parser reverses it using d -> C, cC -> C, d -> C, then CC -> S.

LR(0) items, closure and GOTO without lookahead

An LR(0) item is a production with a dot showing progress. C -> c C gives C -> . c C, C -> c . C and C -> c C .. The dot is parser position, not input; at the far right, the item is complete.

For closure(I), if an item has A -> alpha . B beta, add B -> . gamma for every production of B; repeat to a fixed point. GOTO(I,X) moves every eligible dot across X, then takes closure. Terminals lead to shifts; non-terminals fill GOTO.

The zero means no lookahead. Thus A -> beta . reduces in every terminal column, including $; S' -> S . instead puts accept only under $. SLR restricts reductions using FOLLOW sets, which this LR(0) construction does not use.

Build the seven LR(0) item sets for one grammar

Use (0) S' -> S, (1) S -> C C, (2) C -> c C, (3) C -> d. The terminals are {c,d,$} and the non-terminals are {S,C}. Starting with closure({S' -> . S}), not a memorised state, gives:

I0: S' -> . S
    S  -> . C C
    C  -> . c C
    C  -> . d

I1: S' -> S .

I2: S  -> C . C
    C  -> . c C
    C  -> . d

I3: C  -> c . C
    C  -> . c C
    C  -> . d

I4: C  -> d .

I5: S  -> C C .

I6: C  -> c C .

Every non-empty transition is:

I0 --S--> I1    I0 --C--> I2    I0 --c--> I3    I0 --d--> I4
I2 --C--> I5    I2 --c--> I3    I2 --d--> I4
I3 --C--> I6    I3 --c--> I3    I3 --d--> I4

GOTO(I3,c)=I3 because moving across c produces C -> c . C; closure then restores C -> . c C and C -> . d.

Convert the item sets into the LR(0) ACTION/GOTO table

Let r1 mean S -> C C, r2 mean C -> c C, and r3 mean C -> d. A terminal edge creates a shift, a non-terminal edge fills GOTO, and a completed ordinary item fills its reduction across c, d and $. Only S' -> S . creates accept, under $.

No ACTION cell contains a shift-reduce or reduce-reduce pair. This absence of conflicts, not merely having a table, makes the grammar LR(0).

Parse cdd$ from the first shift to accept

Read each row before performing its action:

At step 3, r3 pops d 4, exposes 3, uses GOTO(3,C)=6, then pushes C 6. At step 4, r2 pops c 3 C 6, exposes 0, uses GOTO(0,C)=2, then pushes C 2. Reductions do not advance input.

The reduction order C -> d, C -> cC, C -> d, S -> CC exactly reverses S => CC => Cd => cCd => cdd.

Detect LR(0) conflicts and avoid common construction traps

For (0) S' -> S, (1) S -> a A, (2) A -> b, (3) A -> b c, the state after ab contains A -> b . and A -> b . c. The first reduces everywhere; the second shifts on c. Their shift-reduce conflict means the grammar is not LR(0).

Useful checks are that I3 has a self-loop on c; I4, I5 and I6 reduce under all three terminals; and only I1 accepts, only on $.

How exams test LR(0) construction and tracing

Common tasks ask you to complete closure or GOTO, count states, fill a cell, find a conflict, classify a grammar, or trace input. Here the answers are 7 states, GOTO(I3,C)=I6, ACTION[4,$]=r3, and final stack 0 S 1.

A 45-second order is: augment, close I0, generate and deduplicate GOTO states, number productions, fill shifts and GOTOs, add all-terminal reductions and accept, then scan ACTION cells for multiple entries. State count alone proves nothing.

Next, compare SLR, CLR and LALR parsers, which keep this item-set machinery but restrict where each reduction may fire, using FOLLOW sets or explicit lookaheads. The stack discipline from the cdd$ trace carries over to all three unchanged.

LR(0) in the short version, then the next study step

Remember: dotted items recognise viable prefixes; closure expands after a non-terminal; GOTO moves the dot; completed ordinary items reduce on every terminal; multiple ACTION entries mean conflict. Recall 7 states -> cdd$ accepted.

For a complete core-CS sequence, use ZERO TO HERO, Complete CS Course. For broader GATE preparation, see GATE Guidance by Sanchit Sir. Browse adjacent subjects in CS Fundamentals. Now build the states, trace cdd$, and spot a conflict without the finished table.