Canonical Collection of LR0 Items for an Expression Grammar | AI Research

Canonical Collection of LR(0) Items for an Expression Grammar

Verified Sources

Nov 4, 2026

We want the canonical collection of LR(0) items for the grammar:

\begin{aligned} E &\rightarrow E + T \mid T \\ T &\rightarrow T * F \mid F \\ F &\rightarrow (E) \mid id \end{aligned}

We use the standard LR(0) item form:

[A \rightarrow \alpha \,\boldsymbol{\cdot}\, \beta]

where the dot position indicates how much of $\alpha$ has been recognized. The canonical collection is built from an initial item set $I_0$ using closure and goto transitions:

closure adds items implied by dots before nonterminals.
goto moves the dot over a grammar symbol and then applies closure.

Key components:

LR(0) item
closure
goto
canonical collection

Note: To construct the LR(0) collection, we augment the grammar with a new start production:

S' \rightarrow E

This ensures a unique start state and acceptance configuration.

LR(0) Items, Closure, and Goto (Tutorial)

Step-by-step construction of the canonical LR(0) collection

1
Step 1
Use the augmented start production $S'\rightarrow E$ , and the grammar rules for $E,T,F$ as given.
2
Step 2
Start with the single item $[S'\rightarrow \cdot E]$ . Because the dot is before nonterminal $E$ , add all productions of $E$ with dot at the beginning. This includes items for $E\rightarrow E+T$ and $E\rightarrow T$ .
3
Step 3
For each symbol $X$ that appears immediately after a dot in any item of $I_0$ , shift the dot over $X$ in those items to form a new set, then apply closure.
4
Step 4
From each newly created item set $I_k$ , compute $goto(I_k, X)$ for all possible $X$ after dots; each distinct result becomes another state.

Step 1: Production list (for reference)

Let us label productions implicitly by their form:

$S' \rightarrow E$
$E \rightarrow E + T$
$E \rightarrow T$
$T \rightarrow T * F$
$T \rightarrow F$
$F \rightarrow (E)$
$F \rightarrow id$

The LR(0) item sets will contain items of the form $[\text{lhs} \rightarrow \alpha \cdot \beta]$ .

Step 2: Initial state $I_0$

I_0 = closure\{[S' \rightarrow \cdot E]\}

Items in $I_0$ :

From $[S' \rightarrow \cdot E]$ $[S^{'} \to \cdot E]$ , dot is before $E$ $E$ , so include:
- $[E \rightarrow \cdot E + T]$
- $[E \rightarrow \cdot T]$

From $[E \rightarrow \cdot T]$ , dot is before $T$ , so include:

$[T \rightarrow \cdot T * F]$
$[T \rightarrow \cdot F]$

From $[T \rightarrow \cdot F]$ , dot is before $F$ , so include:

$[F \rightarrow \cdot (E)]$
$[F \rightarrow \cdot id]$

Therefore:

\begin{aligned} I_0=\{& [S' \rightarrow \cdot E], \\ &[E \rightarrow \cdot E + T], \\ &[E \rightarrow \cdot T], \\ &[T \rightarrow \cdot T * F], \\ &[T \rightarrow \cdot F], \\ &[F \rightarrow \cdot (E)], \\ &[F \rightarrow \cdot id] \} \end{aligned}

Step 3: Compute transitions and all states

We now compute $goto(I_0, X)$ for each symbol $X$ that can follow a dot in $I_0$ :

$E$ , $T$ , $F$ , $(, id$

State $I_1 = goto(I_0, E)$

Shift dot over $E$ from items where the dot is before $E$ :

$[S' \rightarrow \cdot E] \Rightarrow [S' \rightarrow E \cdot]$
$[E \rightarrow \cdot E + T] \Rightarrow [E \rightarrow E \cdot + T]$

No closure additions (dot is before terminals or end). So:

I_1=\{ [S' \rightarrow E\cdot],\; [E \rightarrow E\cdot + T] \}

State $I_2 = goto(I_0, T)$

Shift dot over $T$ where possible:

$[E \rightarrow \cdot T] \Rightarrow [E \rightarrow T \cdot]$
$[T \rightarrow \cdot T * F] \Rightarrow [T \rightarrow T\cdot * F]$

So:

I_2=\{ [E \rightarrow T\cdot],\; [T \rightarrow T\cdot * F] \}

State $I_3 = goto(I_0, F)$

Shift dot over $F$ :

$[T \rightarrow \cdot F] \Rightarrow [T \rightarrow F\cdot]$

So:

I_3=\{ [T \rightarrow F\cdot] \}

State $I_4 = goto(I_0, id)$

Shift dot over $id$ :

$[F \rightarrow \cdot id] \Rightarrow [F \rightarrow id\cdot]$

So:

I_4=\{ [F \rightarrow id\cdot] \}

State $I_5 = goto(I_0, ()$

Shift dot over $(:

$[F \rightarrow \cdot (E)] \Rightarrow [F \rightarrow ( \cdot E )]$

Now closure applies because dot is before nonterminal $E$ :

add $[E \rightarrow \cdot E + T]$
add $[E \rightarrow \cdot T]$ And then recursively for $T$ and $F$ :
$[T \rightarrow \cdot T * F]$
$[T \rightarrow \cdot F]$
$[F \rightarrow \cdot (E)]$
$[F \rightarrow \cdot id]$

Thus:

\begin{aligned} I_5=\{& [F \rightarrow ( \cdot E )], \\ &[E \rightarrow \cdot E + T], \\ &[E \rightarrow \cdot T], \\ &[T \rightarrow \cdot T * F], \\ &[T \rightarrow \cdot F], \\ &[F \rightarrow \cdot (E)], \\ &[F \rightarrow \cdot id] \} \end{aligned}

Step 4: Continue from newly created states until closure

From $I_1=\{[S'\rightarrow E\cdot],[E\rightarrow E\cdot + T]\}$

Only possible dot-after symbol is $+$ (from $[E\rightarrow E\cdot + T]$ ).

State $I_6 = goto(I_1, +)$ Shift dot over $+$ :

$[E \rightarrow E \cdot + T] \Rightarrow [E \rightarrow E + \cdot T]$

Dot is before $T$ , so closure adds:

$[T \rightarrow \cdot T * F]$
$[T \rightarrow \cdot F]$ And closure for $F$ :
$[F \rightarrow \cdot (E)]$
$[F \rightarrow \cdot id]$

So:

\begin{aligned} I_6=\{& [E \rightarrow E + \cdot T], \\ &[T \rightarrow \cdot T * F], \\ &[T \rightarrow \cdot F], \\ &[F \rightarrow \cdot (E)], \\ &[F \rightarrow \cdot id] \} \end{aligned}

From $I_2=\{[E\rightarrow T\cdot],[T\rightarrow T\cdot * F]\}$

Possible dot-after symbol is $*$ .

State $I_7 = goto(I_2, *)$ Shift over $*$ :

$[T \rightarrow T\cdot * F] \Rightarrow [T \rightarrow T * \cdot F]$

Dot is before $F$ , so closure adds:

$[F \rightarrow \cdot (E)]$
$[F \rightarrow \cdot id]$

Thus:

I_7=\{ [T \rightarrow T * \cdot F],\; [F \rightarrow \cdot (E)],\; [F \rightarrow \cdot id] \}

From $I_5=\{[F\rightarrow ( \cdot E )], ...\}$

We compute transitions for $I_5$ .

Symbols that can appear immediately after a dot in $I_5$ :

$E$ , $T$ , $F$ , $(, id$

State $goto(I_5, E) = I_8$ Shift dot over $E$ :

$[F \rightarrow ( \cdot E )] \Rightarrow [F \rightarrow (E \cdot )]$
$[E \rightarrow \cdot E + T] \Rightarrow [E \rightarrow E \cdot + T]$

No closure additions (dot before terminals or end). So:

I_8=\{ [F \rightarrow (E\cdot )],\; [E \rightarrow E\cdot + T] \}

State $goto(I_5, T) = I_9$ Shift dot over $T$ :

$[E \rightarrow \cdot T] \Rightarrow [E \rightarrow T\cdot]$
$[T \rightarrow \cdot T * F] \Rightarrow [T \rightarrow T\cdot * F]$

So:

I_9=\{ [E \rightarrow T\cdot],\; [T \rightarrow T\cdot * F] \}

Notice $I_9$ has the same contents as $I_2$ ; hence it is not a new state (canonical collection reuses identical item sets). Therefore:

$I_9 \equiv I_2$

State $goto(I_5, F) = I_3$ Shifting over $F$ yields $[T\rightarrow F\cdot]$ again, so it matches $I_3$ .

State $goto(I_5, id) = I_4$ Matches $I_4$ .

State $goto(I_5, () = I_5$ Shifting over $($ from $[F\rightarrow \cdot (E)]$ reproduces the same structure as $I_5$ (it’s the same closure pattern), so:

$goto(I_5, '(') \equiv I_5$

From $I_6=\{[E\rightarrow E+\cdot T], [T\rightarrow \cdot T*F], [T\rightarrow \cdot F], ...\}$

Symbols after dots: $T$ , $F$ , $(, id$ .

State $goto(I_6, T)$ Shift dot over $T$ :

$[E \rightarrow E+\cdot T] \Rightarrow [E \rightarrow E+T\cdot]$
$[T \rightarrow \cdot T * F] \Rightarrow [T \rightarrow T\cdot * F]$

So:

I_{10}=\{ [E \rightarrow E+T\cdot],\; [T \rightarrow T\cdot * F] \}

But $[T \rightarrow T\cdot * F]$ appears in $I_2$ and $I_{10}$ also contains $[E\rightarrow T\cdot]$ ? No: $I_{10}$ contains $[E\rightarrow E+T\cdot]$ , which differs. Hence $I_{10}$ is new.

State $goto(I_6, F)$ Shift over $F$ :

$[T\rightarrow \cdot F] \Rightarrow [T \rightarrow F\cdot]$

So $goto(I_6, F)=I_3$ .

State $goto(I_6, id)=I_4$
State $goto(I_6, '(')=I_5$

From $I_7=\{[T\rightarrow T*\cdot F], [F\rightarrow \cdot (E)], [F\rightarrow \cdot id]\}$

Symbols after dots: $F$ , $(, id$ .

State $goto(I_7, F)$ Shift dot over $F$ :

$[T\rightarrow T* \cdot F] \Rightarrow [T\rightarrow T*F\cdot]$

So:

I_{11}=\{ [T \rightarrow T*F\cdot] \}

State $goto(I_7, '(')=I_5$
State $goto(I_7, id)=I_4$

Quick equality check for item sets

Two LR(0) states are the same iff their item sets are identical (same productions and same dot positions). After each goto, sort/compare the items to reuse states like $I_9 \equiv I_2$ and $goto(I_5,'(')\equiv I_5$ .

Don’t forget grammar augmentation

If you omit $S'\rightarrow E$ , you may miss the unique acceptance-related item $[S'\rightarrow E\cdot]$ in the collection.

Final canonical collection $\mathcal{C}$ of LR(0) item sets

We list the distinct item sets constructed:

$I_0$

\begin{aligned} I_0=\{& [S' \rightarrow \cdot E],\\ [E \rightarrow \cdot E + T],\\ [E \rightarrow \cdot T],\\ [T \rightarrow \cdot T * F],\\ [T \rightarrow \cdot F],\\ [F \rightarrow \cdot (E)],\\ [F \rightarrow \cdot id] \} \end{aligned}

$I_1 = goto(I_0,E)$

I_1=\{ [S' \rightarrow E\cdot],\; [E \rightarrow E\cdot + T] \}

$I_2 = goto(I_0,T)$

I_2=\{ [E \rightarrow T\cdot],\; [T \rightarrow T\cdot * F] \}

$I_3 = goto(I_0,F)$

I_3=\{ [T \rightarrow F\cdot] \}

$I_4 = goto(I_0,id)$

I_4=\{ [F \rightarrow id\cdot] \}

$I_5 = goto(I_0,'(')$

\begin{aligned} I_5=\{& [F \rightarrow ( \cdot E )],\\ [E \rightarrow \cdot E + T],\\ [E \rightarrow \cdot T],\\ [T \rightarrow \cdot T * F],\\ [T \rightarrow \cdot F],\\ [F \rightarrow \cdot (E)],\\ [F \rightarrow \cdot id] \} \end{aligned}

$I_6 = goto(I_1,'+')$

\begin{aligned} I_6=\{& [E \rightarrow E + \cdot T],\\ [T \rightarrow \cdot T * F],\\ [T \rightarrow \cdot F],\\ [F \rightarrow \cdot (E)],\\ [F \rightarrow \cdot id] \} \end{aligned}

$I_7 = goto(I_2,'*')$

I_7=\{ [T \rightarrow T * \cdot F],\; [F \rightarrow \cdot (E)],\; [F \rightarrow \cdot id] \}

$I_8 = goto(I_5,E)$

I_8=\{ [F \rightarrow (E\cdot )],\; [E \rightarrow E\cdot + T] \}

$I_{10} = goto(I_6,T)$

I_{10}=\{ [E \rightarrow E + T\cdot],\; [T \rightarrow T\cdot * F] \}

$I_{11} = goto(I_7,F)$

I_{11}=\{ [T \rightarrow T*F\cdot] \}

So the canonical collection has 11 distinct states:

\mathcal{C}=\{I_0,I_1,I_2,I_3,I_4,I_5,I_6,I_7,I_8,I_{10},I_{11}\}

LR(0) canonical collection build order (conceptual)

Create $I_0$

Start

closure of $[S'\rightarrow \cdot E]$ "

Go from $I_0$

First layer

$goto(I_0,E), goto(I_0,T), goto(I_0,F), goto(I_0,id), goto(I_0,'(')$ "

Go from $I_1$ and $I_2$

Second layer

Create $I_6$ via '+', and $I_7$ via '*'"

Go from $I_5$, $I_6$, $I_7$

Third layer

Create $I_8$ , then $I_{10}$ and $I_{11}$ "

No new goto results

Done

All reachable distinct LR(0) item sets are included"

Common checks and edge cases

Knowledge Check

Question 1 of 4

Q1Single choice

In constructing the canonical collection of LR(0) items, the function closure adds items when:

A dot in an item is before a nonterminal

A dot in an item is after a terminal

The item set already contains the same production with a different dot position

A production ends at the dot

Explore Related Topics

LR(0) / SLR Parsing for $S \rightarrow 0S0 \mid 1S1 \mid 10$

Ambiguity Analysis of an Expression Grammar with +, *, Parentheses, and id

Left Recursion in Context-Free Grammars and Its Elimination (LL Parsing)

Browse all research articles

Canonical Collection of LR(0) Items for an Expression Grammar

LR(0) Items, Closure, and Goto (Tutorial)

Step-by-step construction of the canonical LR(0) collection

Step 1: Production list (for reference)

Step 2: Initial state I0I_0I0​

Step 3: Compute transitions and all states

State I1=goto(I0,E)I_1 = goto(I_0, E)I1​=goto(I0​,E)

State I2=goto(I0,T)I_2 = goto(I_0, T)I2​=goto(I0​,T)

State I3=goto(I0,F)I_3 = goto(I_0, F)I3​=goto(I0​,F)

State I4=goto(I0,id)I_4 = goto(I_0, id)I4​=goto(I0​,id)

State I5=goto(I0,()I_5 = goto(I_0, ()I5​=goto(I0​,()

Step 4: Continue from newly created states until closure

From I1={[S′→E⋅],[E→E⋅+T]}I_1=\{[S'\rightarrow E\cdot],[E\rightarrow E\cdot + T]\}I1​={[S′→E⋅],[E→E⋅+T]}

From I2={[E→T⋅],[T→T⋅∗F]}I_2=\{[E\rightarrow T\cdot],[T\rightarrow T\cdot * F]\}I2​={[E→T⋅],[T→T⋅∗F]}

From I5={[F→(⋅E)],...}I_5=\{[F\rightarrow ( \cdot E )], ...\}I5​={[F→(⋅E)],...}

From I6={[E→E+⋅T],[T→⋅T∗F],[T→⋅F],...}I_6=\{[E\rightarrow E+\cdot T], [T\rightarrow \cdot T*F], [T\rightarrow \cdot F], ...\}I6​={[E→E+⋅T],[T→⋅T∗F],[T→⋅F],...}

From I7={[T→T∗⋅F],[F→⋅(E)],[F→⋅id]}I_7=\{[T\rightarrow T*\cdot F], [F\rightarrow \cdot (E)], [F\rightarrow \cdot id]\}I7​={[T→T∗⋅F],[F→⋅(E)],[F→⋅id]}