⚙️ LR(0) — The Foundation
Problem: No lookahead at all — decisions are made blindly on the current state alone.
Result: Conflicts whenever a state can both shift AND reduce.
Fixed by: SLR (next page) — uses FOLLOW sets to restrict reductions to meaningful terminals only.
Parser 4 of 5

LR(0) Parsing

Build the DFA of LR(0) items, construct the parsing table, and watch the bottom-up parser accept ccdd step by step. Every shift, reduce, and goto — explained.

Section 1

What Does "LR(0)" Actually Mean?

L
Left-to-right
Scan the input from left to right — just like you read text.
R
Rightmost derivation
We reconstruct a rightmost derivation, but in reverse (bottom-up).
(0)
Zero lookahead
Decisions are made without peeking at any future input tokens.
DFA
State machine
A finite automaton of item sets tracks where we are in every possible parse.

How Parsing ccdd Works — The Big Picture

Read c
→
Read c
→
Read d
→
Reduce d → C
→
Reduce cC → C
→
Reduce cC → C
Read d
→
Reduce d → C
→
Reduce CC → S
→
✓ Accept!
Key insight: Reading left-to-right and reducing bottom-up gives us the rightmost derivation in reverse. The DFA of LR(0) items tells us when to reduce.
Section 2

The Grammar & Augmentation

Original Grammar

S → CC
C → cC | d
This grammar generates strings of the form cmdcnd. For example: cd, ccd, cdd, ccdd…

Augmented Grammar

S' → S ← NEW (augmented)
S → CC
C → cC
C → d

Why Augment?

Without augmentation, the parser doesn't know when it's done. Consider: after we reduce everything to S, the original grammar has S as the start — but so might other productions. The augmented rule S' → S gives us a unique way to detect acceptance:

When the parser reaches state S' → S• (dot at the end), it knows the entire input has been successfully parsed. This is the Accept action.

Production Numbering (used in the table)

[0] S' → S
[1] S → CC
[2] C → cC
[3] C → d
Section 3

LR(0) Items & Dot Notation

What Is an LR(0) Item?

An LR(0) item is a production rule with a • (dot) somewhere in its right-hand side. The dot represents how much of the production we've already matched.

C → •cC
Initial — Haven't seen anything yet. We expect to see c then C.
C → c•C
Partial — We've matched c. Now we expect C.
C → cC•
Complete — Matched all of cC. Reduce! Replace cC with C.

All LR(0) Items for Our Grammar

Every production generates one item per dot position. Items with the dot at the end are reduce items.

Section 4

DFA Construction — Step by Step

Step 1: Build I₀ via Closure

We start with the kernel item S' → •S and apply the closure operation: whenever the dot is before a non-terminal, add all that non-terminal's productions with the dot at the start.

I₀ Closure (building...)
Explanation

Step 2: Compute GOTO from I₀

For each symbol after a dot in I₀, we move the dot past that symbol and apply closure to get a new state.

Step 3: Complete States I₀ – I₆

After computing all GOTO transitions, we have 7 states. States where all items are complete are reduce states. The state with S' → S• is the accept state.

Step 4: The Complete LR(0) DFA

Nodes are item sets (states). Edges are labeled with the grammar symbol that triggers the transition. Green edges = terminal (shift), Blue edges = non-terminal (goto).

● Shift transition (terminal) ● Goto transition (non-terminal) ● Reduce state (dot at end) ● Accept state
Section 5

LR(0) Parsing Table

How the Table Is Built

SHIFT
If Goto(Ii, a) = Ij for terminal a, set action[i][a] = sj.
REDUCE
If state Ii contains a complete item A→α•, set action[i][t] = rk for ALL terminals t.
GOTO
If Goto(Ii, A) = Ij for non-terminal A, set goto[i][A] = j.
State ACTION GOTO
c d $ S C

Reading Every Entry

Section 6

Parsing Simulation: ccdd$

Watch the LR(0) parser process c c d d $. The parser uses a stack of states and matches the input left-to-right, shifting terminals and reducing when a complete item is found.

Stack (states) Remaining Input Action Notes
Current DFA State
Section 7

LR(0) Conflicts — Where It Falls Apart

Example: Adding C → c to the Grammar

Consider what happens if we add C → c (allowing C to derive just c). This creates a state where we've just seen c — but we don't know if we should shift (to match cC) or reduce (treating c alone as C).

⚠️ Conflict State

State I₃ (with C → c added)
C → c•C
C → c•   ← COMPLETE! Reduce C→c
C → •cC
C → •d
On seeing c: should we shift (pursue C→cC) or reduce (apply C→c)?
LR(0) has NO lookahead — it cannot decide!

Conflict in the Table

State c d $
3 s3 / r(C→c) s4 r(C→c)
The red cell shows a shift-reduce conflict. On terminal c, the parser doesn't know which action to take.
LR(0) Cannot Resolve This: Without any lookahead, there's no way to distinguish between the two valid actions. This is why most real grammars are not LR(0).
SLR to the rescue: SLR(1) uses FOLLOW sets — "reduce C→c only if the next token is in FOLLOW(C)". This resolves many (but not all) such conflicts. See SLR →
← 6. LL(1) 8. SLR →