Consider the following grammar: S \to CC C \to cC | d Find the LR1 set of items. | AI Research

Consider the following grammar: $S \to CC$ $C \to cC | d$ Find the LR(1) set of items.

Verified Sources

Sep 12, 2026

We compute the canonical LR(1) sets (states) for the grammar:

S \to CC,\quad C \to cC \mid d

We will build LR(1) items of the form

[A \to \alpha \,\boldsymbol{\cdot}\, \beta,\; a]

where $a$ is the lookahead terminal. The core mechanics are:

Closure adds items for nonterminals immediately after the dot, with lookaheads propagated using FIRST.
GOTO (or transition) moves the dot over a given grammar symbol and then applies closure.

Key terms: LR(1) item , closure , GOTO , FIRST.

Augmented grammar

Use the standard augmented start rule:

S' \to S

and end-of-input marker $\$ ,$ is the lookahead for the initial state.

We will denote the canonical LR(1) sets by $I_0, I_1, \dots$ .

LR(1) Items: Closure, GOTO, and Lookaheads

Construct LR(1) item sets for the grammar

1
Step 1
We need FIRST sets for suffixes of the form FIRST(βa). Since C can derive terminal strings starting with c or d, FIRST(C) = {c, d}. Also FIRST(X) for a terminal X is {X}.
2
Step 2
Start with [S' → · S, $]. Since dot is before nonterminal S, add items for S with lookahead$ . S→CC means we need items for C that will appear in the right-hand side of S.
3
Step 3
Whenever we have [A→α·Bβ, a], for each production B→γ we add [B→·γ, b] for every b in FIRST(βa) where FIRST(βa) includes terminals that can appear first in strings derived from β followed by a.
4
Step 4
For each state I_k and each symbol X such that some item has dot immediately before X, compute goto(I_k, X) as closure of shifted items [A→αX·β, a].
5
Step 5
Continue generating goto transitions until closure/goto yields the full finite canonical collection.

FIRST facts used for lookahead propagation

From $C \to cC \mid d$ :

\text{FIRST}(C) = \{c, d\}

Also for the augmented start:

The only terminal that can appear immediately from a derivation of $S$ is the first terminal of $CC$ , which is the first terminal of the first $C$ . So:

\text{FIRST}(S) = \{c, d\}

We will also use:

For any terminal $a$ , FIRST( $a$ ) = { $a$ }.
If a string β can begin with terminals in FIRST(β), those are the candidate lookaheads.

Compute canonical LR(1) sets

We list items explicitly. Recall items are $[A \to \alpha \cdot \beta,\; a]$ .

State $I_0$

Start item:

[S' \to \cdot S,\; \$]

Closure on $S$ adds items for $S \to CC$ with lookahead $\$ $:

[S \to \cdot CC,\; \$]

Now dot is before $C$ in $S \to \cdot C C$ . For items of the form $[S \to \cdot C C,\; \$ ] $, we add items for$ C $with lookahead in FIRST($ C,$, $) i.e., FIRST(first-symbols of the remaining suffix$ C $followed by$ $ $). Since the remaining suffix begins with the next$ C$, the lookaheads are:

\text{FIRST}(C\$) = \text{FIRST}(C) = \{c,d\}

Thus closure adds:

[C \to \cdot cC,\; c],\quad [C \to \cdot d,\; c],\quad [C \to \cdot cC,\; d],\quad [C \to \cdot d,\; d]

So:

$I_0 =$

\{ [S' \to \cdot S,\; \$],\; [S \to \cdot CC,\; \$],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

Compute GOTO transitions from I0

1
Step 1
Shift dot over S: [S'→S·, $]. This yields a state with only the completed start production item.
2
Step 2
From [S→·CC, $], shifting over the first C gives [S→C·C,$ ]. Since dot is before another C, we add closure items for C with lookahead FIRST(C$)= {c,d}.
3
Step 3
From items [C→·cC, c] and [C→·cC, d], shifting yields [C→c·C, c] and [C→c·C, d] and closure on dot-before-C introduces [C→·cC, lookahead] and [C→·d, lookahead] for those lookaheads.
4
Step 4
From [C→·d, c] and [C→·d, d], shifting yields completed items [C→d·, c] and [C→d·, d].

State $I_1 = \text{GOTO}(I_0, S)$

I_1 = \{[S' \to S \cdot,\; \$]\}

State $I_2 = \text{GOTO}(I_0, C)$

Shift dot in $[S \to \cdot CC,\; \$ ] $over the first$ C$:

[S \to C\cdot C,\; \$]

Dot is before the second $C$ , so closure adds $C$ items with lookahead in FIRST( $C\$ )={c,d}$:

[C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d]

Thus:

I_2 = \{ [S \to C\cdot C,\; \$],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

State $I_3 = \text{GOTO}(I_0, c)$

From $[C\to \cdot cC,\; c]$ :

[C \to c\cdot C,\; c]

From $[C\to \cdot cC,\; d]$ :

[C \to c\cdot C,\; d]

Now dot is before $C$ ; closure adds items for $C$ with lookahead equal to the lookahead of each item (because the “β” after the dot is empty, so FIRST( $\epsilon a$ ) = { $a$ }): So from lookahead $c$ add:

[C \to \cdot cC,\; c],\ [C \to \cdot d,\; c]

from lookahead $d$ add:

[C \to \cdot cC,\; d],\ [C \to \cdot d,\; d]

Hence:

I_3 = \{ [C \to c\cdot C,\; c],\; [C \to c\cdot C,\; d],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

State $I_4 = \text{GOTO}(I_0, d)$

Shift in:

$[C\to \cdot d,\; c] \mapsto [C\to d\cdot,\; c]$
$[C\to \cdot d,\; d] \mapsto [C\to d\cdot,\; d]$

Thus:

I_4 = \{[C \to d\cdot,\; c],\ [C \to d\cdot,\; d]\}

More states from I2, I3

We now compute transitions similarly.

From $I_2$

$I_2$ has items:

$[S \to C\cdot C,\; \$ ] $(dot before$ C$)
the same $C$ -items as $I_0$ for both lookaheads $c,d$ .

So transitions:

$\text{GOTO}(I_2, C)$ : shift to $[S\to CC\cdot,\; \$ ]$ (completed)
$\text{GOTO}(I_2, c)$ and $\text{GOTO}(I_2, d)$ : same as from the closure items for $C$ but with the same lookahead behavior as in $I_0$ / $I_3$ .

This yields new state:

I_5 = \text{GOTO}(I_2, C) = \{[S \to CC\cdot,\; \$]\}

Also:

\text{GOTO}(I_2, c) = I_3,\quad \text{GOTO}(I_2, d)= I_4

(because the relevant $C$ -items are identical in structure and lookahead sets).

From $I_3$

$I_3$ contains:

$[C \to c\cdot C,\; c]$ and $[C \to c\cdot C,\; d]$ (dot before $C$ )
plus the closure items $[C\to \cdot cC,\; c]$ , $[C\to \cdot d,\; c]$ , and similarly for lookahead $d$ .

So:

$\text{GOTO}(I_3, C)$ shifts dot in $[C\to c\cdot C,\; a]$ to completion $[C\to cC\cdot,\; a]$ for $a\in\{c,d\}$ . This creates a state:

I_6 = \{[C \to cC\cdot,\; c],\ [C \to cC\cdot,\; d]\}

$\text{GOTO}(I_3, c)$ and $\text{GOTO}(I_3, d)$ reproduce $I_3$ and $I_4$ respectively (by the same reasoning as earlier).

Thus no further distinct LR(1) sets arise.

Canonical LR(1) collection construction (state discovery order)

Initial closure

$I_0$

Start with [S'→·S, $], then expand via S→CC and C→cC|d."

Accept state

$I_1$

From I0 via goto(S): [S'→S·, $]."

After first C in S→CC

$I_2$

From I0 via goto(C): [S→C·C, $] plus closure for C with lookahead {c,d}."

After reading a c in C productions

$I_3$

From I0 via goto(c): items like [C→c·C, a] with a∈{c,d}."

Completed terminal d in C

$I_4$

From I0 via goto(d): [C→d·, c] and [C→d·, d]."

Completed S→CC

$I_5$

From I2 via goto(C): [S→CC·, $]."

Completed C→cC

$I_6$

From I3 via goto(C): [C→cC·, c] and [C→cC·, d]."

Lookahead propagation shortcut

When you have [A→α·Bβ, a], the lookaheads for items of B are FIRST(βa). If β is empty, FIRST(βa) = { $a$ }.

Avoid confusing canonical LR(1) with LR(0)

In LR(1) you must keep the lookahead terminal $a$ in every item; otherwise states merge incorrectly and you won’t get the canonical collection.

Final answer: the LR(1) item sets

The canonical LR(1) sets for the given grammar are the six distinct collections below.

$I_0$

\{ [S' \to \cdot S,\; \$],\; [S \to \cdot CC,\; \$],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

$I_1$

\{[S' \to S \cdot,\; \$]\}

$I_2$

\{ [S \to C\cdot C,\; \$],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

$I_3$

\{ [C \to c\cdot C,\; c],\; [C \to c\cdot C,\; d],\; [C \to \cdot cC,\; c],\; [C \to \cdot d,\; c],\; [C \to \cdot cC,\; d],\; [C \to \cdot d,\; d] \}

$I_4$

\{[C \to d\cdot,\; c],\ [C \to d\cdot,\; d]\}

$I_5$

\{[S \to CC\cdot,\; \$]\}

$I_6$

\{[C \to cC\cdot,\; c],\ [C \to cC\cdot,\; d]\}

Knowledge Check

Question 1 of 4

Q1Single choice

In LR(1) closure, for an item [A→α·Bβ, a], the lookaheads added for B→γ are computed from which set?

FIRST(βa)

FOLLOW(A)

FIRST(A)

FOLLOW(β)

Explore Related Topics

Similarity Between SLR(1), LALR(1), and LR(1): Correct Choice and Learning Path

Constructing an LALR(1) Parsing Table for a Given Grammar (and Proving It Is Not SLR(1))

Linear Grammar in the Chomsky Hierarchy (CF Grammar with ≤ 1 Nonterminal on RHS)

Browse all research articles

Consider the following grammar: S→CCS \to CCS→CC C→cC∣dC \to cC | dC→cC∣d Find the LR(1) set of items.

Augmented grammar

LR(1) Items: Closure, GOTO, and Lookaheads

Construct LR(1) item sets for the grammar

FIRST facts used for lookahead propagation

Compute canonical LR(1) sets

State I0I_0I0​

Compute GOTO transitions from I0

State I1=GOTO(I0,S)I_1 = \text{GOTO}(I_0, S)I1​=GOTO(I0​,S)

State I2=GOTO(I0,C)I_2 = \text{GOTO}(I_0, C)I2​=GOTO(I0​,C)

State I3=GOTO(I0,c)I_3 = \text{GOTO}(I_0, c)I3​=GOTO(I0​,c)

State I4=GOTO(I0,d)I_4 = \text{GOTO}(I_0, d)I4​=GOTO(I0​,d)

More states from I2, I3

From I2I_2I2​

From I3I_3I3​

Canonical LR(1) collection construction (state discovery order)

Initial closure

Accept state

After first C in S→CC

After reading a c in C productions

Completed terminal d in C

Completed S→CC

Completed C→cC

Lookahead propagation shortcut

Avoid confusing canonical LR(1) with LR(0)

Final answer: the LR(1) item sets

I0I_0I0​

I1I_1I1​

I2I_2I2​

I3I_3I3​

I4I_4I4​

I5I_5I5​

I6I_6I6​

Knowledge Check

Explore Related Topics

Consider the following grammar: $S \to CC$ $C \to cC | d$ Find the LR(1) set of items.

State $I_0$

State $I_1 = \text{GOTO}(I_0, S)$

State $I_2 = \text{GOTO}(I_0, C)$

State $I_3 = \text{GOTO}(I_0, c)$

State $I_4 = \text{GOTO}(I_0, d)$

From $I_2$

From $I_3$

$I_0$

$I_1$

$I_2$

$I_3$

$I_4$

$I_5$

$I_6$