Coursify

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

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

Verified Sources
Nov 3, 2026

We study the grammar [ S \rightarrow 0S0 \mid 1S1 \mid 10 ] and build (a) the LR(0) collection of items, (b) the SLR parsing table, and (c) the SLR parse trace for the string 01100.

Throughout, we use the standard LR method with the augmented grammar: [ S' \rightarrow S ] and LR(0) items of the form ([A \rightarrow \alpha ,\boldsymbol{\cdot}, \beta]), where (\boldsymbol{\cdot}) indicates how much of the RHS (\alpha\beta) has been recognized.

Key concepts: LR(0) item; closure; goto; FOLLOW set.

type="tip" title="Tip: Always augment the grammar" content="For LR parsing tables, add (S' \rightarrow S) and include the accept action when you reach ([S' \rightarrow S\boldsymbol{\cdot}])."

LR(0) / SLR Parsing (intuition + mechanics)

Step 0: List terminals, nonterminals, and productions

Nonterminal: (S) (and augmented (S')). Terminals: ({0,1}).

Productions (augmented):

  • (S' \rightarrow S)
  • (S \rightarrow 0S0)
  • (S \rightarrow 1S1)
  • (S \rightarrow 10)

Define LR(0) items for each production with dots at all possible positions.

We will compute:

  • (I_0 = \text{closure}({[S' \rightarrow \boldsymbol{\cdot}S]}))
  • then repeatedly apply goto for each grammar symbol that can appear immediately after a dot.

Construct the LR(0) item sets (collection) for the grammar

  1. 1
    Step 1

    I0 = {[S'→·S], [S→·0S0], [S→·1S1], [S→·10]} because closure adds productions of the nonterminal immediately after the dot (here S).

  2. 2
    Step 2

    From I0: dot is before S (in [S'→·S]), before 0 (in [S→·0S0]), before 1 (in [S→·1S1]), and before 1 (in [S→·10]). Thus:

    • goto(I0, S) gives items with dot advanced in [S'→·S] → [S'→S·]
    • goto(I0, 0) advances [S→·0S0] → [S→0·S0] and closure adds [S→·0S0],[S→·1S1],[S→·10]
    • goto(I0, 1) advances [S→·1S1] and [S→·10] appropriately
  3. 3
    Step 3

    Continue until no new item sets appear. Each goto moves the dot past the chosen symbol, then applies closure if a dot lands before a nonterminal.

  4. 4
    Step 4

    Assign each distinct item set an index (I_0, I_1, \dots).

LR(0) item sets

We compute the full collection manually.

(I_0 = \text{closure}({[S' \rightarrow \boldsymbol{\cdot}S]}))

[ I_0 = { [S' \rightarrow \boldsymbol{\cdot}S],; [S \rightarrow \boldsymbol{\cdot}0S0],; [S \rightarrow \boldsymbol{\cdot}1S1],; [S \rightarrow \boldsymbol{\cdot}10] } ]

Transitions out of (I_0)

  • ( \text{goto}(I_0, S) ): [ I_1 = {[S' \rightarrow S\boldsymbol{\cdot}]} ]
  • ( \text{goto}(I_0, 0) ): Start from ([S \rightarrow \cdot 0S0]) ⇒ ([S \rightarrow 0\cdot S0]). Closure adds items for (S): [ I_2 = { [S \rightarrow 0\boldsymbol{\cdot}S0],; [S \rightarrow \boldsymbol{\cdot}0S0],; [S \rightarrow \boldsymbol{\cdot}1S1],; [S \rightarrow \boldsymbol{\cdot}10] } ]
  • ( \text{goto}(I_0, 1) ): From ([S \rightarrow \cdot 1S1]) ⇒ ([S \rightarrow 1\cdot S1]), and from ([S \rightarrow \cdot 10]) ⇒ ([S \rightarrow 1\cdot 0]) (note: dot is before (0), not before a nonterminal). Closure does not add anything further because the dots are before terminal symbols (S) (nonterminal) and (0) (terminal) respectively; for ([S \rightarrow 1\cdot S1]), closure adds productions of (S) because dot is before (S). Thus: [ I_3 = { [S \rightarrow 1\boldsymbol{\cdot}S1],; [S \rightarrow \boldsymbol{\cdot}0S0],; [S \rightarrow \boldsymbol{\cdot}1S1],; [S \rightarrow \boldsymbol{\cdot}10],; [S \rightarrow 1\boldsymbol{\cdot}0] } ]

Now proceed transitions from each set.

Transitions from (I_2)

[ I_2: [S \rightarrow 0\cdot S0], ; [S \rightarrow \cdot 0S0], ; [S \rightarrow \cdot 1S1], ; [S \rightarrow \cdot 10] ]

  • ( \text{goto}(I_2, S) ): [ I_4 = {[S \rightarrow 0S\boldsymbol{\cdot}0]} ]
  • ( \text{goto}(I_2, 0) ): From ([S \rightarrow \cdot 0S0]) ⇒ ([S \rightarrow 0\cdot S0]) which is exactly the same core as in (I_2), plus closure items: this yields (I_2) again. [ \text{goto}(I_2,0)=I_2 ]
  • ( \text{goto}(I_2, 1) ): From ([S \rightarrow \cdot 1S1]) ⇒ ([S \rightarrow 1\cdot S1]) and with closure for (S), plus ([S\rightarrow \cdot 10]) etc: this produces (I_3). [ \text{goto}(I_2,1)=I_3 ]

Transitions from (I_3)

[ I_3: [S \rightarrow 1\cdot S1],; [S \rightarrow \cdot 0S0],; [S \rightarrow \cdot 1S1],; [S \rightarrow \cdot 10],; [S \rightarrow 1\cdot 0] ]

  • ( \text{goto}(I_3, S) ): From ([S \rightarrow 1\cdot S1]) ⇒ ([S \rightarrow 1S\cdot 1]): [ I_5 = {[S \rightarrow 1S\boldsymbol{\cdot}1]} ]
  • ( \text{goto}(I_3, 0) ): Two sources:
    • ([S \rightarrow \cdot 0S0]) ⇒ ([S \rightarrow 0\cdot S0]) with closure ⇒ (I_2)
    • ([S \rightarrow 1\cdot 0]) ⇒ ([S \rightarrow 10\cdot]) (completed item) So we must include both: [ I_6 = { [S \rightarrow 0\boldsymbol{\cdot}S0],; [S \rightarrow \boldsymbol{\cdot}0S0],; [S \rightarrow \boldsymbol{\cdot}1S1],; [S \rightarrow \boldsymbol{\cdot}10],; [S \rightarrow 10\boldsymbol{\cdot}] } ] Wait—careful: for goto on terminal (0), we shift the dot over (0). From ([S \rightarrow \cdot 0S0]) that yields ([S\rightarrow 0\cdot S0]) plus closure for (S). From ([S\rightarrow 1\cdot 0]) it yields ([S\rightarrow 10\cdot]). Hence (I_6) is correct.
  • ( \text{goto}(I_3, 1) ): From ([S \rightarrow \cdot 1S1]) ⇒ ([S \rightarrow 1\cdot S1]) with closure ⇒ (I_3) core; also ([S\rightarrow \cdot 1S1]) is included in closure, so: [ \text{goto}(I_3,1)=I_3 ]

Transitions from (I_4)

[ I_4={[S \rightarrow 0S\boldsymbol{\cdot}0]} ] Only dot before terminal (0): [ \text{goto}(I_4,0)={[S \rightarrow 0S0\boldsymbol{\cdot}]}=I_7 ]

Transitions from (I_5)

[ I_5={[S \rightarrow 1S\boldsymbol{\cdot}1]} ] Only dot before terminal (1): [ \text{goto}(I_5,1)={[S \rightarrow 1S1\boldsymbol{\cdot}]}=I_8 ]

Transitions from (I_6)

[ I_6 \text{ contains } [S\rightarrow 10\cdot] \text{ (completed) and also the same “prefix” items as } I_2. ]

  • Since (I_6) includes ([S\rightarrow 0\cdot S0]), (\text{goto}(I_6,0)) gives the same as (\text{goto}(I_2,0)=I_2), and (\text{goto}(I_6,1)=I_3), etc.
  • The completed item ([S\rightarrow 10\cdot]) does not create new goto transitions.

At this point the collection is complete.

Final LR(0) collection summary

We list all item sets encountered:

  • (I_0={[S' \rightarrow \cdot S],[S\rightarrow \cdot 0S0],[S\rightarrow \cdot 1S1],[S\rightarrow \cdot 10]})
  • (I_1={[S' \rightarrow S\cdot]})
  • (I_2={[S\rightarrow 0\cdot S0],[S\rightarrow \cdot 0S0],[S\rightarrow \cdot 1S1],[S\rightarrow \cdot 10]})
  • (I_3={[S\rightarrow 1\cdot S1],[S\rightarrow \cdot 0S0],[S\rightarrow \cdot 1S1],[S\rightarrow \cdot 10],[S\rightarrow 1\cdot 0]})
  • (I_4={[S\rightarrow 0S\cdot 0]})
  • (I_5={[S\rightarrow 1S\cdot 1]})
  • (I_6={[S\rightarrow 0\cdot S0],[S\rightarrow \cdot 0S0],[S\rightarrow \cdot 1S1],[S\rightarrow \cdot 10],[S\rightarrow 10\cdot]})
  • (I_7={[S\rightarrow 0S0\cdot]})
  • (I_8={[S\rightarrow 1S1\cdot]})

type="warning" title="Warning: LR(0) lookahead is NOT used" content="In LR(0), completed items would cause reduce actions on all terminals. In SLR, reduces are restricted to terminals in FOLLOW sets, preventing many conflicts."

(b) Construct the SLR parsing table

Step 1: Compute FOLLOW(S)

Because the augmented start symbol is (S') and (S) is its only production:

  • ($\in \text{FOLLOW}(S)) since (S) can appear at the end of the input (via (S'\rightarrow S)).

Also, examine occurrences of (S) in RHS:

  • From (S \rightarrow 0S0): after (S) comes terminal (0), so (0 \in \text{FOLLOW}(S)).
  • From (S \rightarrow 1S1): after (S) comes terminal (1), so (1 \in \text{FOLLOW}(S)).
  • From (S \rightarrow 10): no occurrence of (S).

So: [ \text{FOLLOW}(S)={0,1,$} ]

Key terms: SLR; shift action; reduce action; accept action.

Fill SLR(Parsing) table ACTION and GOTO

  1. 1
    Step 1

    If there is a goto transition I --a--> J, then ACTION[I,a] = shift J. If I contains [A→α·] (completed), then for SLR use ACTION[I, b] = reduce A→α for all b in FOLLOW(A). If I contains [S'→S·], then ACTION[I,$] = accept.

  2. 2
    Step 2

    If there is goto transition I --A--> J, then GOTO[I,A]=J.

  3. 3
    Step 3

    Number productions as: (1) S'→S, (2) S→0S0, (3) S→1S1, (4) S→10. Only (2)(3)(4) are used for reduce since (1) is the accept case.

  4. 4
    Step 4

    Use the completed items in each state for reduce rows, and dot-before-symbol items for shift/goto rows.

Production numbering

Let:

  1. (S' \rightarrow S) (not reduced; used for accept)
  2. (S \rightarrow 0S0)
  3. (S \rightarrow 1S1)
  4. (S \rightarrow 10)

ACTION/GOTO table

Terminals: (0,1,$). Nonterminal: (S).

We list transitions (from the LR(0) collection):

  • From (I_0):

    • goto on (S) → (I_1)
    • goto on (0) → (I_2)
    • goto on (1) → (I_3)

  • From (I_2):

    • goto on (S) → (I_4)
    • goto on (0) → (I_2)
    • goto on (1) → (I_3)

  • From (I_3):

    • goto on (S) → (I_5)
    • goto on (0) → (I_6)
    • goto on (1) → (I_3)

  • From (I_4):

    • goto on (0) → (I_7)

  • From (I_5):

    • goto on (1) → (I_8)

  • From (I_6):

    • goto on (0) → (I_2)
    • goto on (1) → (I_3) (completed item ([S\rightarrow 10\cdot]) causes reductions)

  • (I_1) contains ([S'\rightarrow S\cdot]) ⇒ accept on ($).

  • (I_7) contains ([S\rightarrow 0S0\cdot]) ⇒ reduce by (2) on FOLLOW(S) = ({0,1,$}).

  • (I_8) contains ([S\rightarrow 1S1\cdot]) ⇒ reduce by (3) on ({0,1,$}).

  • (I_6) contains ([S\rightarrow 10\cdot]) ⇒ reduce by (4) on ({0,1,$}).

Now the tables.

StateACTION on 0ACTION on 1ACTION on $GOTO on S
0shift 2shift 31
1accept
2shift 2shift 34
3shift 6shift 35
4shift 7
5shift 8
6reduce 4reduce 4reduce 4
7reduce 2reduce 2reduce 2
8reduce 3reduce 3reduce 3

(c) Trace acceptance of string "01100"

We trace using the standard LR stack method.

Input string: 0 1 1 0 0 then ($).

We will use configuration format: [ [\text{states stack}], [\text{symbols stack}], \text{remaining input} ] But we can keep it compact by tracking only state stack and actions.

Start:

  • State stack: ([0])
  • Input: (0,1,1,0,0$)

Trace table (SLR)

We use actions from the SLR table.

StepStateLookaheadActionResulting states stack
100shift 2[0,2]
221shift 3[0,2,3]
331shift 3[0,2,3,3]
430shift 6[0,2,3,3,6]
560reduce 4: (S\rightarrow 10)pop 2 states → [0,2,3,3]; then goto from top on S = goto(3,S)=5 → [0,2,3,3,5]
650error (no ACTION for state 5 on lookahead 0)reject

Why step 5 reduction is valid:

  • In state 6 we have item ([S\rightarrow 10\cdot]), hence reduce by production (4) on lookahead in FOLLOW(S) = ({0,1,$}).

But at step 6, after the reduction, the parser is in state 5 expecting terminal 1 (since (I_5) has ([S\rightarrow 1S\cdot 1]) meaning dot is before terminal 1). Lookahead is 0, so ACTION[5,0] is undefined ⇒ parsing fails.

Therefore "01100" is NOT accepted by this SLR parser.

Common pitfalls / sanity checks

Where reductions occur in the SLR table (intuition)

Completed-item states that trigger reduce actions.

Knowledge Check

Question 1 of 4
Q1Single choice

In the augmented grammar for LR parsing, the usual added production is:

Explore Related Topics

1

LL(1) Check for the Grammar \(S \rightarrow iEtSA \mid a,\; A \rightarrow eS \mid \epsilon,\; E \rightarrow b\)

2

LR Parsing Power: SLR(1), CLR(1), and LALR(1) (Low → High)

3

Constructing and Using an SLR(1) Parser for the Grammar $E \rightarrow E+T \mid T$, $T \rightarrow T*F \mid F$, $F \rightarrow (E) \mid id$

Browse all research articles