5.2 LR(0) Parsing: Canonical Collection of Items, Closure, GOTO & Table Construction

Back to DBMS Notes

📚Module 01LR(0) Parsing & Canonical Item Collections⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Assembly Progress Tracker

Imagine building a complex piece of flat-pack furniture with an instruction manual:

• The Production Blueprint: $\text{Chair} \to \text{Legs} \ \text{Seat} \ \text{Backrest}$
• The Progress Bookmark (The Dot $\cdot$):
  • $\text{Chair} \to \cdot \ \text{Legs} \ \text{Seat} \ \text{Backrest}$: You have opened the box, but haven't assembled anything yet. You are actively searching for the Legs.
  • $\text{Chair} \to \text{Legs} \cdot \text{Seat} \ \text{Backrest}$: The legs are fully attached! Your eyes now shift to the next instruction: grab the Seat.
  • $\text{Chair} \to \text{Legs} \ \text{Seat} \ \text{Backrest} \cdot$: The entire chair is completely assembled! You don't need any more parts; you proudly mark this unit finished (Reduce to Chair).

💻 Bridging to Computer Science: Tracking Viable Prefixes via Dot Items

In bottom-up LR parsing, the compiler does not guess which production to apply ahead of time. Instead, it tracks all partially matched productions simultaneously using LR(0) Items:

• An LR(0) item is simply a grammar production with a marker dot ($\cdot$) placed at some position on the right-hand side.
• The symbols to the left of the dot represent what has already been pushed and verified on the parser stack.
• The symbols to the right of the dot represent what the parser expects to see next in the input stream.
• When the dot reaches the extreme right end ($A \to \alpha \cdot$), the entire handle has been matched, signaling an immediate Reduce action.

📑Table of Contents

• 🏗️ Architectural Foundations: The LR(0) State Machine Pipeline
• 📐 Formal Mathematical Foundations: Items, Closure & GOTO
  • ➕ The Augmented Grammar
  • 📌 The LR(0) Item
• ⚙️ The Canonical Collection Engine: CLOSURE & GOTO
  • 🔒 The CLOSURE Algorithm
  • 🚀 The GOTO Function
• 🏗️ LR(0) Parsing Table Construction Algorithm
  • Deterministic Population Rules
• 🤼 Conflicts in LR(0) Grammars
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Complete Canonical Collection & LR(0) Table Construction
  • Example 2: Proving an Arithmetic Expression Grammar is NOT LR(0)
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: The LR(0) State Machine Pipeline

Architecture Flow

The Canonical LR(0) Collection Pipeline

Generating the DFA of viable prefixes through augmented grammar, closure expansion, and GOTO transitions

➕Step 1

Augment Grammar G'

Introduce unique start rule S' → S to define an unambiguous accept state.

→

Seed Item

🔒Step 2

CLOSURE Expansion

Inductively add B → •γ whenever dot precedes non-terminal B.

→

State I0

🚀Step 3

GOTO(I, X) Transitions

Advance dot past symbol X and take CLOSURE of resulting items.

→

Fixed Point

⚡Step 4

Canonical DFA

Complete collection of item sets forming parser ACTION and GOTO tables.

---

📐 Formal Mathematical Foundations: Items, Closure & GOTO

➕ The Augmented Grammar

Given a context-free grammar $G = (V, \Sigma, R, S)$, the Augmented Grammar $G'$ is formed by introducing a fresh start symbol $S'$ and a single auxiliary production:

$$S' \to S$$

Why augment? In the original grammar, the start symbol $S$ may appear on the right-hand side of some production rules (e.g. $S \to a S b$). Without augmentation, the parser cannot distinguish between completing a nested sub-derivation of $S$ and completing the entire compilation. Reducing $S' \to S$ signals an unambiguous termination condition: the parser halts and safely Accepts the program.

📌 The LR(0) Item

An LR(0) Item of a grammar $G$ is a production $A \to \alpha \beta$ with a distinguished dot • placed at some position in the right-hand side:

$$A \to \alpha \cdot \beta$$

• For a production with right-hand side of length $n = |\alpha \beta|$, there are exactly $n + 1$ distinct LR(0) items.

• Special Case for Epsilon: For an empty production $A \to \epsilon$, there is only one LR(0) item:

  $$A \to \cdot$$

  (Which functions immediately as a completed reduce item!)

The 4 Canonical LR(0) Item Categories

How the position of the dot determines the parser's operational action

⏩

Shift Item

Action: Shift

• Dot immediately precedes a terminal symbol: A → α • a β.
• Triggers a SHIFT action: pushes terminal 'a' and target state onto the stack.
• Consumes exactly one terminal from the input lookahead stream.

Key Abstractions / Calls

ACTION[i, a] = sjAdvance Input Pointer

🔀

GOTO Item

Action: Non-Terminal Transition

• Dot immediately precedes a non-terminal symbol: A → α • B β.
• Triggers CLOSURE expansion: pulls all initial items B → •γ into current state.
• Governs parser state transitions after a reduction: GOTO[state, B].

Key Abstractions / Calls

CLOSURE(I)GOTO[i, B] = j

🎯

Reduce Item

Action: Reduction

• Dot has reached the extreme right of the production: A → γ •.
• Entire production handle has been matched and verified on stack.
• Pops |γ| states and symbols from stack; exposes previous state.

Key Abstractions / Calls

ACTION[i, *] = rkPop |γ| Elements

🏆

Accept Item

Action: Parser Acceptance

• Special item derived from the augmented start symbol: S' → S •.
• Occurs when entire input has been successfully reduced to start symbol S.
• Parser terminates with success: program is grammatically valid.

Key Abstractions / Calls

ACTION[i, $] = accHalt with Success

---

⚙️ The Canonical Collection Engine: CLOSURE & GOTO

The collection of all sets of LR(0) items forms the state space of the DFA of Viable Prefixes.

🔒 The CLOSURE Algorithm

If $I$ is a set of items for grammar $G$, $\text{CLOSURE}(I)$ is constructed inductively:

1. Basis: Every item in $I$ is added to $\text{CLOSURE}(I)$.

2. Induction: If $[A \to \alpha \cdot B \beta] \in \text{CLOSURE}(I)$ and $B$ is a non-terminal, then for every production $B \to \gamma$ in $G$, add the initial item:

   $$B \to \cdot \gamma$$

   to $\text{CLOSURE}(I)$, if it is not already present.

3. Repeat step 2 until no new items can be added.

🚀 The GOTO Function

Let $I$ be a set of items, and let $X \in (V \cup \Sigma)$ be a grammar symbol. $\text{GOTO}(I, X)$ represents the state reached by transitioning across symbol $X$:

📖Formal Definition: The LR(0) GOTO Transition Functiondefinition

$$\text{GOTO}(I, X) = \text{CLOSURE}\big( \{ A \to \alpha X \cdot \beta \mid A \to \alpha \cdot X \beta \in I \} \big)$$

Intuitively, $\text{GOTO}(I, X)$ advances the dot one position to the right across symbol $X$ for all items in $I$ where the dot precedes $X$, and then expands the closure of the resulting set.

---

🏗️ LR(0) Parsing Table Construction Algorithm

An LR parsing table contains two distinct components:

• $\text{ACTION}[i, a]$: Indexed by parser state $i$ and terminal token $a$ (where $a \in \Sigma$ or $a =$ $).
• $\text{GOTO}[i, A]$: Indexed by parser state $i$ and non-terminal symbol $A \in V$.

Deterministic Population Rules

For each state $I_i$ in the canonical collection:

1. Shift Actions: If $[A \to \alpha \cdot a \beta] \in I_i$ where $a \in \Sigma$ is a terminal, and $\text{GOTO}(I_i, a) = I_j$:

   $$\text{ACTION}[i, a] = \text{Shift } j \quad (\text{written } s_j)$$

2. Reduce Actions (The Zero-Lookahead Invariant): If $[A \to \alpha \cdot] \in I_i$ (where $A \neq S'$ and $A \to \alpha$ is production rule $k$):

   $$\text{ACTION}[i, a] = \text{Reduce } k \quad (\text{written } r_k) \quad \text{\bf for ALL terminals } a \in \Sigma \cup \{ \$ \}$$

   (In an LR(0) parser, reductions are placed blindly across every single terminal column in the row!)

3. Accept Action: If $[S' \to S \cdot] \in I_i$:

   $$\text{ACTION}[i, \$] = \text{Accept}$$

4. GOTO Entries: If $\text{GOTO}(I_i, A) = I_j$ for non-terminal $A \in V$:

   $$\text{GOTO}[i, A] = j$$

5. Blank Entries: All unpopulated cells in the table represent syntax error states.

---

🤼 Conflicts in LR(0) Grammars

Because LR(0) places reductions unconditionally across all terminal columns without checking lookahead, very few practical grammars are strictly LR(0):

• Shift/Reduce (S/R) Conflict: A state contains both a shift item ($A \to \alpha \cdot a \beta$) and a reduce item ($B \to \gamma \cdot$). When terminal $a$ arrives, the table cannot decide whether to shift or reduce.
• Reduce/Reduce (R/R) Conflict: A state contains two distinct completed reduce items ($A \to \alpha \cdot$ and $B \to \beta \cdot$). The parser cannot decide which reduction to execute.

Definition: A grammar is LR(0) if and only if its LR(0) parsing table contains zero multiply-defined entries (no S/R or R/R conflicts).

---

🏭 Real-World Production Context: How Industry Builds This

While pure LR(0) parsers are rarely used directly in production compilers because practical languages have operator precedence that causes LR(0) conflicts:

The LR(0) Canonical Collection of Items is the exact DFA backbone utilized by both SLR(1) and LALR(1) parser generators (such as GNU Bison, Yacc, and Menhir):

• An LALR(1) generator constructs the exact same LR(0) state machine first.
• Only after building the LR(0) state graph does the generator compute lookahead sets to restrict where reductions are placed, transforming row-wide reductions into targeted lookahead slots.

Because the LR(0) state machine merges all derivation contexts with identical cores, the number of states generated is compact—typically on the order of several hundred to a few thousand states for an entire C or Rust grammar.

---

📐 Numerical Applications & Worked Examples

Example 1: Complete Canonical Collection & LR(0) Table Construction

Construct the complete canonical collection of LR(0) items and the parsing table for the grammar:

$$\begin{aligned} S &\to A A \\ A &\to a A \mid b \end{aligned}$$

Step-by-Step Analytical Solution:

Step 1: Number the Productions in Augmented Grammar $G'$

• Production (0): $S' \to S$
• Production (1): $S \to A A$
• Production (2): $A \to a A$
• Production (3): $A \to b$

Step 2: Construct the Canonical Collection of States

Initial State $I_0$:

• Seed item: $S' \to \cdot S$
• Dot precedes $S \implies$ add $S \to \cdot A A$
• Dot precedes $A \implies$ add $A \to \cdot a A$ and $A \to \cdot b$
• $I_0 = \{ S' \to \cdot S, \ S \to \cdot A A, \ A \to \cdot a A, \ A \to \cdot b \}$

Transitions from $I_0$:

• $\text{GOTO}(I_0, S) = \text{CLOSURE}(\{ S' \to S \cdot \}) = \mathbf{I_1} = \{ S' \to S \cdot \}$
• $\text{GOTO}(I_0, A) = \text{CLOSURE}(\{ S \to A \cdot A \})$:
  • Dot precedes $A \implies$ add $A \to \cdot a A$ and $A \to \cdot b$
  • $\mathbf{I_2} = \{ S \to A \cdot A, \ A \to \cdot a A, \ A \to \cdot b \}$
• $\text{GOTO}(I_0, a) = \text{CLOSURE}(\{ A \to a \cdot A \})$:
  • Dot precedes $A \implies$ add $A \to \cdot a A$ and $A \to \cdot b$
  • $\mathbf{I_3} = \{ A \to a \cdot A, \ A \to \cdot a A, \ A \to \cdot b \}$
• $\text{GOTO}(I_0, b) = \text{CLOSURE}(\{ A \to b \cdot \}) = \mathbf{I_4} = \{ A \to b \cdot \}$

Transitions from $I_2$:

• $\text{GOTO}(I_2, A) = \text{CLOSURE}(\{ S \to A A \cdot \}) = \mathbf{I_5} = \{ S \to A A \cdot \}$
• $\text{GOTO}(I_2, a) = I_3$ (same items as $I_3$)
• $\text{GOTO}(I_2, b) = I_4$ (same items as $I_4$)

Transitions from $I_3$:

• $\text{GOTO}(I_3, A) = \text{CLOSURE}(\{ A \to a A \cdot \}) = \mathbf{I_6} = \{ A \to a A \cdot \}$
• $\text{GOTO}(I_3, a) = I_3$ (self-loop)
• $\text{GOTO}(I_3, b) = I_4$

States $I_1, I_4, I_5, I_6$ have dots at the end (completed items).
Total Canonical States = 7 states ($I_0$ through $I_6$).

Step 3: Construct the LR(0) Parsing Table

State	Action: a	Action: b	Action: $	GOTO: S	GOTO: A
0	$s_3$	$s_4$		1	2
1			Accept
2	$s_3$	$s_4$			5
3	$s_3$	$s_4$			6
4	$r_3$	$r_3$	$r_3$
5	$r_1$	$r_1$	$r_1$
6	$r_2$	$r_2$	$r_2$

Notice that in States 4, 5, and 6, reductions $r_3, r_1, r_2$ are placed unconditionally across all terminal columns (a, b, and $)!
Because every single cell contains at most one action, the grammar is strictly LR(0)!

---

Example 2: Proving an Arithmetic Expression Grammar is NOT LR(0)

Consider the grammar:

$$\begin{aligned} S &\to E \\ E &\to E + T \mid T \\ T &\to \text{id} \end{aligned}$$

Prove analytically that this grammar is NOT LR(0) by constructing the conflicting state.

Step-by-Step Analytical Proof:

1. Augment the grammar: $S' \to S$.

2. Compute state $I_0 = \text{CLOSURE}(\{ S' \to \cdot S \})$:

   • Includes $S' \to \cdot S$
   • Includes $S \to \cdot E$
   • Includes $E \to \cdot E + T$ and $E \to \cdot T$
   • Includes $T \to \cdot \text{id}$

3. Compute state $I_1 = \text{GOTO}(I_0, E)$:

   $$I_1 = \text{CLOSURE}(\{ S \to E \cdot, \ E \to E \cdot + T \})$$

4. Inspect state $I_1$:

   • Item $S \to E \cdot$ is a completed reduce item. In LR(0), it requires Reduce $S \to E$ placed in ALL terminal columns, including + and $.
   • Item $E \to E \cdot + T$ is a shift item on terminal +. It requires Shift on column +.

5. Evaluate table cell $\text{ACTION}[1, +]$:

   $$\text{ACTION}[1, +] = \{ \text{Shift}, \quad \text{Reduce } S \to E \}$$

6. A severe Shift/Reduce Conflict exists in state $I_1$. Therefore, the grammar is NOT LR(0).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "How many LR(0) items are generated by a production rule of length n, and what is the rule for epsilon productions?"
Key Focus Points:

• A production $A \to X_1 X_2 \dots X_n$ has $n$ symbols on its right-hand side and generates exactly $n + 1$ LR(0) items (the dot can occupy positions $0, 1, \dots, n$).
• For an epsilon production $A \to \epsilon$, length $n = 0$. It generates exactly 1 item: $A \to \cdot$. This item is immediately a complete reduce item.

Question 2: "Why does LR(0) table construction place reductions in every terminal column, and why does this cause conflicts?"
Key Focus Points:

• Zero Lookahead: The '0' in LR(0) denotes zero tokens of lookahead. The parser makes reduction decisions based solely on the stack contents without inspecting the next input symbol.
• Resulting Fragility: Whenever a state contains both a shift item and a completed reduce item, placing the reduction across the entire row creates an unavoidable Shift/Reduce conflict under the shift terminal.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Placing reductions only under FOLLOW symbols in an LR(0) table.
Answer: Fatal concept mix-up. Placing reductions only under $\text{FOLLOW}(A)$ is the definition of SLR(1), NOT LR(0). In LR(0), reductions MUST be placed in every terminal column plus $.

Trap 2: Believing left-recursive grammars cannot be parsed by LR(0).
Answer: Misconception carried over from LL(1). Bottom-up LR parsers naturally handle left-recursive grammars without infinite loops or stack overflow. In fact, left recursion is preferred in bottom-up parsing because it keeps the stack depth bounded during list processing!

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic5.1 Shift-Reduce Parsing Mechanics, Handles & Operator PrecedenceNext Topic →5.3 SLR(1) Parsing: FOLLOW Lookaheads & Conflict Resolution