LR(0) Grammars

LR(0) Grammars

1. Idea

LR(0): parse Left-to-right, Rightmost derivation in reverse, 0 lookahead in items. Parser decides shift vs reduce from the item set alone. Smallest LR family — base for SLR/LR/LALR.

2. LR(0) Items and Closure

An item marks progress: A → α • β (• = what is parsed so far). Closure adds items for non-terminals after •:

closure({S' → • S}): add S → • ... for every S-production, recursively
goto(I, X) = closure({A → α X • β | A → α • X β in I})

Augmented grammar adds S' → S so accept is S' → S •.

3. Canonical LR(0) Collection (example)

0. S' → • E | E → • E+T | • T (I0)
   --E--> I1: S' → S •, E → E • +T
   --T--> I2: E → T •   (reduce state)

Each state = set of items; edges = goto. Reduces happen when state contains a complete item A → α •.

4. LR(0) Limits — Conflicts

• Shift-reduce: state has A → α • a β and B → γ • → cannot decide without lookahead.
• Reduce-reduce: two complete items A → α •, B → β • in one state.
  Grammars with conflicts are not LR(0) — need SLR/LR(1) lookahead to resolve.

5. Exam Points

• Define LR(0) item, closure, goto — 5 marks, very frequent.
• Construct canonical LR(0) collection for small grammar — 7 marks, frequent.
• Identify shift-reduce / reduce-reduce conflicts — 3-5 marks, frequent.