CLR(1) Parser and Canonical LR(1) Items: Worked Closure, GOTO and Parse Table

An LR(1) item adds one lookahead to an LR(0) item, changing closure, state identity, and permitted reductions. A bottom-up parsing construction runs from augmentation through ACTION/GOTO to acceptance of ccdd. For the broader parser family, see Parsing in Compiler Design: Top-Down and Bottom-Up Explained.

What a CLR(1) item actually records

In [A -> alpha . beta, a], the dot records recognised input. Lookahead a controls a completed item's reduction. It need not follow the dot, and GOTO neither moves nor consumes it.

A -> alpha . beta is the LR(0) core; closure supplies lookaheads; a CLR state contains all resulting items. [C -> d ., c] reduces only on c.

Augment with S' -> S and start at [S' -> . S, $]. Only [S' -> S ., $] accepts under $.

Closure and GOTO with explicit lookaheads

For [A -> alpha . B beta, a], each B -> gamma, and b in FIRST(beta a), add [B -> . gamma, b] to a fixed point. Review First and Follow in Compiler Design: Solved Examples if needed.

GOTO moves each applicable dot across X, retains lookaheads, then closes. Terminal moves enter ACTION; non-terminal moves enter GOTO.

[S -> . C C, $] gives FIRST(C$) = {c, d}. [S -> C . C, $] has empty beta, so FIRST($) = {$}.

Build the complete canonical collection

Use (0) S' -> S, (1) S -> C C, (2) C -> c C, (3) C -> d, with FIRST(C) = {c, d}.

Closure adds [S -> . C C, $], then two lookaheads per C production. [C -> . c C, c] and [C -> . c C, d] remain distinct items.

• I0 = {[S' -> . S, $], [S -> . C C, $], [C -> . c C, c], [C -> . d, c], [C -> . c C, d], [C -> . d, d]}

• I1 = {[S' -> S ., $]}

• I2 = {[S -> C . C, $], [C -> . c C, $], [C -> . d, $]}

• I3 = {[C -> c . C, c], [C -> c . C, d], [C -> . c C, c], [C -> . d, c], [C -> . c C, d], [C -> . d, d]}

• I4 = {[C -> d ., c], [C -> d ., d]}

• I5 = {[S -> C C ., $]}

• I6 = {[C -> c . C, $], [C -> . c C, $], [C -> . d, $]}

• I7 = {[C -> d ., $]}

• I8 = {[C -> c C ., c], [C -> c C ., d]}

• I9 = {[C -> c C ., $]}

The non-empty transitions are:

• I0 --S--> I1, I0 --C--> I2, I0 --c--> I3, I0 --d--> I4

• I2 --C--> I5, I2 --c--> I6, I2 --d--> I7

• I3 --C--> I8, I3 --c--> I3, I3 --d--> I4

• I6 --C--> I9, I6 --c--> I6, I6 --d--> I7

There are 10 states and 26 individual items: 6+1+3+6+2+1+3+1+2+1 = 26.

Convert item sets into ACTION and GOTO

A terminal transition gives shift j; [A -> alpha ., a] reduces only under a; [S' -> S ., $] accepts; a non-terminal transition fills GOTO. Let r1: S -> C C, r2: C -> c C, r3: C -> d.

No cell has both a shift and reduction or two reductions, so the table is conflict-free. I4 and I7 share core C -> d ., but reduce on {c,d} and $ respectively.

Trace ccdd$ from shift to accept

Derive S => C C => c C C => c c C C => c c d C => c c d d. The first C uses C -> c C twice then C -> d; the second uses C -> d.

At step 4, r3 pops d,4, exposing state 3. GOTO(3,C)=8 produces 0 c 3 c 3 C 8, including the required state transition.

How questions test CLR(1) and where errors start

Problems ask for closure, state count, table entries, conflicts, a trace, or merging. See SLR vs CLR vs LALR Parsers for GATE: States & Conflicts for comparison.

Keep I4/I7 and I3/I6 separate. Merging equal cores creates LALR states; check conflicts after lookahead union.

CLR(1) in the short version

Augment; start at [S' -> . S, $]; close with FIRST(beta a); generate GOTO states without merging; enter shifts, specific reductions, GOTOs, and accept. Now reproduce all 10 states and justify each non-error cell.

Use CS Fundamentals for the broader subject map, or revisit the opening parsing guide. For a sequenced core-CS path, continue with ZERO TO HERO.