LR(0) items, CLOSURE, GOTO, the canonical collection and the LR(0) table

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• What is a handle, and where does it appear during shift-reduce parsing? from Lesson 2.4.1
• Compute FOLLOW(T) for E → T E′, E′ → + T E′ | ε, T → F T′, …. from Lesson 2.3.2
• What does subset construction produce from an NFA, and how many states can it have at most? from Lesson 0.2.3

1 · The Story

📖

Cards with a dot

To know when to fold, Kabir writes progress cards: one rule per card, with a dot showing how much of the rule is already on the pile. “A → a • A” means: “I have seen an a; I now expect an A.” A card with the dot at the end, “A → b •”, means: “the whole right side is here; fold now.”

If a card expects a category, say A, Kabir also lays out fresh cards for every rule of A, dot at the start, because the next thing on the pile could begin an A. A bundle of cards laid out together is a state of his mind.

When a word or category arrives, he moves the dot past it on every card that was waiting for it, collects those cards, adds the fresh cards they call for, and gets the next bundle. Kabir numbers every distinct bundle and writes the whole collection on a wall: a finite machine that tells him, for any pile, what to do next.

2 · Predict First

🤔

For S → A A, A → a A | b, how many distinct bundles (states) does the collection have? Write your guess down. The answer is in the vault.

3 · Core Concept

LR(0) items

An LR(0) item is a production with a dot somewhere in its right side. A → X Y Z gives four items: A → •XYZ, A → X•YZ, A → XY•Z, A → XYZ•. A → ε gives one item, A → •. An item with the dot at the end is complete (a reduce candidate). A production with k symbols on the right gives k + 1 items.

First augment the grammar with a new start production S′ → S. Reducing by it means accept.

CLOSURE and GOTO

CLOSURE(I) of a set of items I: start with I; whenever A → α•Bβ is in it and B → γ is a production, add B → •γ; repeat until nothing new.

GOTO(I, X) = CLOSURE of { A → αX•β : A → α•Xβ ∈ I }: move the dot past X in every item that expects X.

The items placed by the GOTO step (plus S′ → •S) are the kernel items; the ones added by CLOSURE (dot at the start) are non-kernel.

Canonical collection

Start with I₀ = CLOSURE({S′ → •S}). For every set I already found and every grammar symbol X with GOTO(I, X) non-empty, add GOTO(I, X) as a new set (if not already present). The sets are the states of a DFA, the LR(0) automaton, which recognises exactly the viable prefixes.

The LR(0) parsing table

• If A → α•aβ ∈ Iᵢ (a terminal) and GOTO(Iᵢ, a) = Iⱼ: ACTION[i, a] = shift j (sj).
• If A → α• ∈ Iᵢ (complete, A ≠ S′): ACTION[i, a] = reduce A → α for every terminal a and $.
• If S′ → S• ∈ Iᵢ: ACTION[i, $] = accept.
• GOTO[i, A] = j for nonterminals A with GOTO(Iᵢ, A) = Iⱼ.

A grammar is LR(0) if this table has no multiple entries: no state contains a complete item together with another complete item (reduce/reduce) or with an item expecting a terminal (shift/reduce).

The LR parsing algorithm

Stack of states (symbols shown for clarity), starting with 0. With state s on top and token a: shift j pushes a and j; reduce A → β pops |β| symbol-state pairs, then pushes A and GOTO[top, A]; accept stops.

Story → compiler term

4 · Visual

(0) S' → S
(1) S → A A
(2) A → a A
(3) A → b

The LR(0) automaton of S → A A, A → a A | b: 7 states. Each box is a state; edges are GOTO on the labelled symbol.

LR(0) table: complete items reduce in every column. No cell has two entries, so the grammar is LR(0).

5 · Worked Examples

Example 1 Easy

Build the canonical LR(0) collection for S → A A, A → a A | b.

Solution

I₀ = CLOSURE({S′ → •S}) = { S′ → •S, S → •AA, A → •aA, A → •b }. GOTO(I₀, S) = { S′ → S• }, GOTO(I₀, A) = { S → A•A, A → •aA, A → •b }, GOTO(I₀, a) = { A → a•A, A → •aA, A → •b }, GOTO(I₀, b) = { A → b• }, and so on. The graph above shows all 7 states; like Kabir’s bundles, each is a set of cards with dots.

Example 2 Medium

Parse a a b b with the LR(0) table above.

Solution

10 rows. Each reduce pops 2 entries per right-side symbol in the state-and-symbol stack (here shown as symbol-state pairs) and then uses GOTO.

Example 3 GATE

The expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id has how many LR(0) states, and is it LR(0)?

Solution

The canonical collection has 12 states (I₀ … I₁₁). It is not LR(0): state I2 = { E → T•, T → T•*F } has a complete item and an item expecting *, so ACTION[2, *] holds both reduce and shift (likewise I9 = { E → E + T•, T → T•*F }). The next lesson repairs this by reducing only when the next token can follow E.

6 · Shortcuts

⚡

Count items: Σ over augmented productions of (|right side| + 1). For S → AA, A → aA | b: 2 + 3 + 3 + 2 = 10. Valid when: questions about the number of LR(0) items (not states).

⚡

LR(0) conflict spotting: look only at states with a complete item; any other item in that state that expects a terminal (S/R) or is also complete (R/R) is a conflict. Valid when: deciding LR(0) quickly.

7 · GATE Traps

⚠️

• Augment first: forgetting S′ → S changes the state count.
• In the LR(0) table a complete item reduces in every column, including $.
• The state count is not the item count.
• A → ε contributes the complete item A → • (it can cause conflicts in many states).
• GOTO on a nonterminal fills the GOTO part of the table; on a terminal it becomes a shift.

8 · Memory Hook

🧠

The dot is a bookmark in the rule. CLOSURE lays out what could start next; GOTO moves the bookmark.

9 · Connect the Dots

LR(0) reduces blindly, whatever comes next, which is why the expression grammar fails. The next lesson keeps the same automaton but reduces A → α only when the next token is in FOLLOW(A).

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markItems

How many LR(0) items does the augmented grammar of S → A A, A → a A | b have?

Numerical answer: ________

Q2NAT2 marksStates

How many states does the canonical LR(0) collection of E → E + T | T, T → T * F | F, F → ( E ) | id have?

Numerical answer: ________

Q3MCQ1 markCLOSURE

If I = { S → A•B } and B → b | c B, then CLOSURE(I) contains:

• (A) only S → A•B
• (B) S → A•B, B → •b, B → •cB
• (C) S → AB•
• (D) B → b•, B → cB•

Q4MCQ2 marksLR(0)

Why is E → E + T | T, T → T * F | F, F → ( E ) | id not LR(0)?

• (A) It is ambiguous.
• (B) A state contains E → T• together with T → T•*F.
• (C) It has ε-productions.
• (D) It is left recursive.

Q5MSQ1 markFacts

Which are true about the LR(0) automaton?

• (A) Its states are sets of items.
• (B) It recognises the viable prefixes of the grammar.
• (C) It is built only for LR(0) grammars.
• (D) GOTO on a terminal becomes a shift entry.

11 · Rule Card

• Item: production with a dot; |rhs| + 1 items per production; A → ε gives A → •.
• Augment: S′ → S.
• CLOSURE: A → α•Bβ adds B → •γ.
• GOTO(I, X): advance the dot over X, then CLOSURE.
• LR(0) table: shift on terminals after the dot; complete item reduces in all columns; S′ → S• accepts on $.
• LR(0) conflict: complete item with another complete item (R/R) or with a terminal-after-dot item (S/R).

12 · Concept Ledger

LR(0) itemcomplete itemaugmented grammar S′ → SCLOSURE(I)GOTO(I, X)kernel / non-kernel itemscanonical LR(0) collectionLR(0) automatonACTION / GOTO tableLR(0) grammar

13 · Answer Vault