CSE411

CSE411: Introduction to Compilers

LR(1) Parsing

Jooyong Yi (UNIST)

2026 Fall
CSE411
(1) S : V = E   (2) S : E
(3) E : V       (4) V : id
(5) V : * E                                            


--------------------------------------------------
       |     Action               |  Goto  
 State |------------------------------------------
       | id     *      =     $    |  S   E   V
 -------------------------------------------------  
   0   |                          | 
   1   |                          | 
   2   |                          | 
   3   |                          |
   4   |                          |
   5   |                          |
   6   |                          |
   7   |                          |
   8   |                          |
   9   |                          |
  10   |                          |
--------------------------------------------------
2026 Fall
CSE411
(1) S : V = E   (2) S : E
(3) E : V       (4) V : id
(5) V : * E                                            

Follow(E) = {$, =}
--------------------------------------------------
       |     Action               |  Goto  
 State |------------------------------------------
       | id     *      =     $    |  S   E   V
 -------------------------------------------------  
   0   | s6    s5                 |  1   4   2
   1   |                     acc  |
   2   |             s3,r3   r3   |
   3   |                          |
   4   |                          |
   5   |                          |
   6   |                          |
   7   |                          |
   8   |                          |
   9   |                          |
  10   |                          |
--------------------------------------------------
  • shift/reduce conflict
  • We can fix this. How?
  • Think about what could happen when .
2026 Fall
CSE411
(1) S : V = E   (2) S : E
(3) E : V       (4) V : id
(5) V : * E   

Follow(E) = {$, =}
--------------------------------------------------
       |     Action               |  Goto  
 State |------------------------------------------
       | id     *      =     $    |  S   E   V
 -------------------------------------------------  
   0   | s6    s5                 |  1   4   2
   1   |                     acc  |
   2   |             s3,r3   r3   |

When I0 -> I2                            
   
    S                 S
    |                 |
    E       or        E
    |                 |
    V                 V
   / \                |
  *   E               id
  • When , '=' ∉ Follow(E)
2026 Fall
CSE411
(1) S : V = E   (2) S : E
(3) E : V       (4) V : id
(5) V : * E   

Follow(E) = {$, =}
--------------------------------------------------
       |     Action               |  Goto  
 State |------------------------------------------
       | id     *      =     $    |  S   E   V
 -------------------------------------------------  
   0   | s6    s5                 |  1   4   2
   1   |                     acc  |
   2   |             s3,r3   r3   |

When I0 -> I5 -> I7
2026 Fall
CSE411
(1) S : V = E   (2) S : E
(3) E : V       (4) V : id
(5) V : * E   

Follow(E) = {$, =}
--------------------------------------------------
       |     Action               |  Goto  
 State |------------------------------------------
       | id     *      =     $    |  S   E   V
 -------------------------------------------------  
   0   | s6    s5                 |  1   4   2
   1   |                     acc  |
   2   |             s3,r3   r3   |

When I0 -> I5 -> I7                            
   
     S                 
   / | \                 
  V  =  E 
 / \
*   E             


'=' ∈ Follow(E)
2026 Fall
CSE411

Solution

Previous New
center center
2026 Fall
CSE411

Solution

LR(0) Automaton LR(1) Automaton
center center
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ───────────┐
│ S' → ·S      ? │
└────────────────┘
  • Which terminal do we expect to see after S?
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ───────────┐
│ S' → ·S      $ │
└────────────────┘
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ────────────┐
│ S' → ·S       $ │
| S  → ·V = E     | 
| S  → ·E         |
└─────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ────────────┐
│ S' → ·S       $ │
| S  → ·V = E   $ │
| S  → ·E       $ │
└─────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ────────────┐
│ S' → ·S       $ │
| S  → ·V = E   $ │
| S  → ·E       $ │
| E  → ·V         |
└─────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
                   |
                   V
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ────────────┐
│ S' → ·S       $ │
| S  → ·V = E   $ │
| S  → ·E       $ │
| E  → ·V       $ |
└─────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
                   |
                   V
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ────────────┐
│ S' → ·S       $ │
| S  → ·V = E   $ │
| S  → ·E       $ │
| E  → ·V       $ |
| V  → ·id        |
└─────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
 |                 |
 id                V
                   |
                   id
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ──────────────┐
│ S' → ·S       $   │
| S  → ·V = E   $   │
| S  → ·E       $   │
| E  → ·V       $   |
| V  → ·id     =, $ |
└───────────────────┘

   S' $            S' $
   |               |
   S        or     S
  /|\              |
 V = E             E
 |                 |
 id                V
                   |
                   id
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ──────────────┐
│ S' → ·S       $   │
| S  → ·V = E   $   │
| S  → ·E       $   │
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E         |
└───────────────────┘

    S' $            S' $
    |               |
    S        or     S
   /|\              |
  V = E             E
 / \                |
*   E               V
                   / \ 
                  *   E
2026 Fall
CSE411

Associating Lookahead

┌─ I0 ──────────────┐
│ S' → ·S       $   │
| S  → ·V = E   $   │
| S  → ·E       $   │
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E    =, $ |
└───────────────────┘

    S' $            S' $
    |               |
    S        or     S
   /|\              |
  V = E             E
 / \                |
*   E               V
                   / \ 
                  *   E
2026 Fall
CSE411
┌─ I0 ──────────────┐
│ S' → ·S       $   │
| S  → ·V = E   $   │
| S  → ·E       $   │
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E    =, $ |
└───────────────────┘

    S' $            S' $
    |               |
    S        or     S
   /|\              |
  V = E             E
 / \                |
*   E               V
                   / \ 
                  *   E

┌──────────────────────┐
| A → α·Xβ    z        |
| X → γ      _______   |
└──────────────────────┘
2026 Fall
CSE411
┌─ I0 ──────────────┐
│ S' → ·S       $   │
| S  → ·V = E   $   │
| S  → ·E       $   │
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E    =, $ |
└───────────────────┘

    S' $            S' $
    |               |
    S        or     S
   /|\              |
  V = E             E
 / \                |
*   E               V
                   / \ 
                  *   E

┌──────────────────────┐
| A → α·Xβ    z        |
| X → γ      FIRST(βz) |
└──────────────────────┘
2026 Fall
CSE411
┌─ I0 ──────────────┐  V     ┌─ I2 ──────────────┐
│ S' → ·S       $   │------> | S → V· = E    $   |
| S  → ·V = E   $   │        | E  → V·       $   |
| S  → ·E       $   │        └───────────────────┘
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E    =, $ |
└───────────────────┘
      * |
        ↓ 
┌─ I5 ──────────────┐  V    ┌─ I7 ──────────────┐
| V →  * ·E    =, $ |------>| E → ·V            |
| E → ·V            |       └───────────────────┘
| V → ·id           |
| V  → ·* E         |
└───────────────────┘
2026 Fall
CSE411
┌─ I0 ──────────────┐  V     ┌─ I2 ──────────────┐
│ S' → ·S       $   │------> | S → V· = E    $   |
| S  → ·V = E   $   │        | E  → V·       $   |
| S  → ·E       $   │        └───────────────────┘
| E  → ·V       $   |
| V  → ·id     =, $ |
| V  → ·* E    =, $ |
└───────────────────┘
      * |
        ↓ 
┌─ I5 ──────────────┐  V    ┌─ I7 ──────────────┐
| V →  * ·E    =, $ |------>| E → ·V      =, $  |
| E → ·V       =, $ |       └───────────────────┘
| V → ·id      =, $ |
| V  → ·* E    =, $ |
└───────────────────┘
2026 Fall
CSE411

LR(0) automaton construction algorithm

// Construct an LR(0) automaton
CS = ∅ // a set of closures
CS = CS ∪ Closure({E'→·E$}) // E is the starting nonterminal of a given grammar
Edges = ∅
repeat
   for each C in CS
      for each item A → α·Xβ in C // X is either a terminal or a nonterminal
         if X is not $
            let J be Goto(C, X)
            CS = CS ∪ {J}
            Edges = Edges ∪ {C -X-> J}
         else
            Edges = Edges ∪ {C -X-> accept}


Closure(I) =
   repeat       
      for any item A → α·Xβ in I // X is either a terminal or a nonterminal
         for any production X → γ
            I = I ∪ {X → ·γ}
   until I does not change
   return I

Goto(I, X) =
   J = ∅
   for any item A → α·Xβ in I
      J = J ∪ {A → αX·β}
   return Closure(J)
2026 Fall
CSE411

LR(1) automaton construction algorithm

// Construct an LR(0) automaton
CS = ∅ // a set of closures
CS = CS ∪ Closure({E'→·E$}) // E is the starting nonterminal of a given grammar
Edges = ∅
repeat
   for each C in CS
      for each item A → α·Xβ in C // X is either a terminal or a nonterminal
         if X is not $
            let J be Goto(C, X)
            CS = CS ∪ {J}
            Edges = Edges ∪ {C -X-> J}
         else
            Edges = Edges ∪ {C -X-> accept}


Closure(I) =
   repeat       
      // z: lookahead terminal
      for any item (A → α·Xβ, z) in I // X is either a terminal or a nonterminal
         for any production X → γ // X is a nonterminal
            for any w ∈ FIRST(βz) 
               I = I ∪ {(X → ·γ, w)}
   until I does not change
   return I

Goto(I, X) =
   J = ∅
   for any item A → α·Xβ in I
      J = J ∪ {A → αX·β}
   return Closure(J)
2026 Fall
CSE411

Summary: SLR(1) and canonical LR(1)

  • Both belong to the LR(1) family
  • SLR(1): Simple LR, using LR(0) automaton plus FOLLOW sets.
  • Canonical LR(1) uses LR(1) automaton; often simply called LR(1).
2026 Fall
CSE411

Disadvantage of LR(1)

LR(0) Automaton LR(1) Automaton
center center
2026 Fall
CSE411

LALR(1): Look-Ahead LR(1)

LR(1) Automaton LALR(1) Automaton
center center
2026 Fall
CSE411

SLR(1) vs LALR(1)

SLR(1) LALR(1)
center center
2026 Fall
CSE411

Parsing Power

center

2026 Fall

\begin{tikzpicture}[node distance=3.5cm] \node (I1) [process] { $I_0$ \vspace{-2ex} \begin{align*} S' &\rightarrow \cdot S \\ S &\rightarrow \cdot V = E \\ S &\rightarrow \cdot E \\ E &\rightarrow \cdot V \\ V &\rightarrow \cdot \text{id} \\ V &\rightarrow \cdot * \, E \end{align*} }; \node (I2) [process, above of=I1] { $I_1$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot \end{align*} }; \node (A) [left of=I2] { accept \vspace{-2ex} }; \node (I3) [process, right of=I2] { $I_2$ \vspace{-2ex} \begin{align*} S &\rightarrow V \cdot = E \\ E &\rightarrow V \cdot \end{align*} }; \node (I4) [process, right of=I3] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow V = \cdot E \\ E &\rightarrow \cdot V \\ V &\rightarrow \cdot \text{id} \\ V &\rightarrow \cdot * \, E \end{align*} }; \node (I5) [process, below=1cm of I3] { $I_4$ \vspace{-2ex} \begin{align*} S &\rightarrow E \cdot \end{align*} }; \node (I6) [process, below of=I1] { $I_5$ \vspace{-2ex} \begin{align*} V &\rightarrow * \cdot E \\ E &\rightarrow \cdot V \\ V &\rightarrow \cdot \text{id} \\ V &\rightarrow \cdot * \, E \end{align*} }; \node (I7) [process, below=1 cm of I5] { $I_6$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot \end{align*} }; \node (I9) [process, right of=I4] { $I_8$ \vspace{-2ex} \begin{align*} S &\rightarrow V = E \cdot \end{align*} }; \node (I8) [process, below=1cm of I7] { $I_{7}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot \end{align*} }; \node (I10) [process, below=1cm of I8] { $I_{9}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot \end{align*} }; \node (I11) [process, below of=I4] { $I_{10}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, \cdot E \\ E &\rightarrow \cdot V \\ V &\rightarrow \cdot \text{id} \\ V &\rightarrow \cdot * \, E \end{align*} }; \draw [arrow] (I2) -- node[anchor=south] {\$} (A); \draw [arrow] (I1) -- node[anchor=east] {S} (I2); \draw [arrow] (I1) -- node[anchor=east] {V} (I3); \draw [arrow] (I3) -- node[anchor=south] {=} (I4); \draw [arrow] (I1) -- node[anchor=south] {E} (I5); \draw [arrow] (I1) -- node[anchor=east] {*} (I6); \path (I6) edge [loop left] node {*} (I6); \path (I11) edge [loop right] node {*} (I11); \draw [arrow] (I4) -- node[anchor=south] {V} (I8); \draw [arrow] (I1) -- node[anchor=south] {id} (I7); \draw [arrow] (I4) -- node[anchor=south] {E} (I9); \draw [arrow] (I6) -- node[anchor=south] {E} (I10); \draw [arrow] (I6) -- node[anchor=south] {V} (I8); \draw [arrow] (I4) -- node[anchor=south] {id} (I7); \draw [arrow] (I4) -- node[anchor=east] {*} (I11); \draw [arrow] (I11) -- node[anchor=south] {E} (I10); \draw [arrow] (I11) -- node[anchor=south] {V} (I8); \draw [arrow] (I11) -- node[anchor=south] {id} (I7); \draw [arrow] (I6) -- node[anchor=south] {id} (I7); \end{tikzpicture}

\begin{tikzpicture}[node distance=3.6cm] \node (I1) [process] { $I_0$ \vspace{-2ex} \begin{align*} S' &\rightarrow \cdot S && \$ \\ S &\rightarrow \cdot V = E && \$ \\ S &\rightarrow \cdot E && \$ \\ E &\rightarrow \cdot V && \$\\ V &\rightarrow \cdot \text{id} &&\$, =\\ V &\rightarrow \cdot * \, E &&\$, = \end{align*} }; \node (I2) [process, above of=I1] { $I_1$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot && \$ \end{align*} }; \node (A) [left=1 cm of I2] { accept \vspace{-2ex} }; \node (I3) [process, right of=I2] { $I_2$ \vspace{-2ex} \begin{align*} S &\rightarrow V \cdot = E && \$ \\ E &\rightarrow V \cdot && \$ \end{align*} }; \node (I4) [process, right of=I3] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow V = \cdot E && \$ \\ E &\rightarrow \cdot V && \$ \\ V &\rightarrow \cdot \text{id} && \$ \\ V &\rightarrow \cdot * \, E && \$ \end{align*} }; \node (I5) [process, below=1cm of I3] { $I_4$ \vspace{-2ex} \begin{align*} S &\rightarrow E \cdot && \$ \end{align*} }; \node (I6) [process, below of=I1] { $I_5$ \vspace{-2ex} \begin{align*} V &\rightarrow * \cdot E && \$, = \\ E &\rightarrow \cdot V && \$, = \\ V &\rightarrow \cdot \text{id} && \$, =\\ V &\rightarrow \cdot * \, E && \$, = \end{align*} }; \node (I7) [process, below=1 cm of I5] { $I_6$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot && \$, = \end{align*} }; \node (I9) [process, right of=I4] { $I_8$ \vspace{-2ex} \begin{align*} S &\rightarrow V = E \cdot && \$ \end{align*} }; \node (I8) [process, below=1cm of I7] { $I_{7}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot && \$, = \end{align*} }; \node (I10) [process, below=1cm of I8] { $I_{9}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot && \$, = \end{align*} }; \node (I11) [process, below of=I4] { $I_{10}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, \cdot E && \$ \\ E &\rightarrow \cdot V && \$\\ V &\rightarrow \cdot \text{id} && \$\\ V &\rightarrow \cdot * \, E && \$ \end{align*} }; \node (I12) [process, below=0.7cm of I9] { $I_{11}$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot && \$ \end{align*} }; \node (I13) [process, below=1.2cm of I12] { $I_{12}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot && \$ \end{align*} }; \node (I14) [process, below=1cm of I13] { $I_{13}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot && \$ \end{align*} }; \draw [arrow] (I2) -- node[anchor=south] {\$} (A); \draw [arrow] (I1) -- node[anchor=east] {S} (I2); \draw [arrow] (I1) -- node[anchor=east] {V} (I3); \draw [arrow] (I3) -- node[anchor=south] {=} (I4); \draw [arrow] (I1) -- node[anchor=south] {E} (I5); \draw [arrow] (I1) -- node[anchor=east] {*} (I6); \path (I6) edge [loop below] node {*} (I6); \path (I11) edge [loop below] node {*} (I11); \draw [arrow] (I4) -- node[anchor=north, pos=0.7] {V} (I13); \draw [arrow] (I1) -- node[anchor=south] {id} (I7); \draw [arrow] (I4) -- node[anchor=south] {E} (I9); \draw [arrow] (I6) -- node[anchor=south] {E} (I10); \draw [arrow] (I6) -- node[anchor=south] {V} (I8); \draw [arrow] (I4) -- node[anchor=south] {id} (I12); \draw [arrow] (I4) -- node[anchor=east] {*} (I11); \draw [arrow] (I11) -- node[anchor=south] {E} (I14); \draw [arrow] (I11) -- node[anchor=south] {V} (I13); \draw [arrow] (I11) -- node[anchor=east] {id} (I12); \draw [arrow] (I6) -- node[anchor=south] {id} (I7); \end{tikzpicture}

\begin{tikzpicture}[node distance=3.6cm] \node (I1) [process] { $I_0$ \vspace{-2ex} \begin{align*} S' &\rightarrow \cdot S && \$ \\ S &\rightarrow \cdot V = E && \$ \\ S &\rightarrow \cdot E && \$ \\ E &\rightarrow \cdot V && \$\\ V &\rightarrow \cdot \text{id} &&\$, =\\ V &\rightarrow \cdot * \, E &&\$, = \end{align*} }; \node (I2) [process, above of=I1] { $I_1$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot && \$ \end{align*} }; \node (A) [left=1 cm of I2] { accept \vspace{-2ex} }; \node (I3) [process, right of=I2] { $I_2$ \vspace{-2ex} \begin{align*} S &\rightarrow V \cdot = E && \$ \\ E &\rightarrow V \cdot && \$ \end{align*} }; \node (I4) [process, right of=I3] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow V = \cdot E && \$ \\ E &\rightarrow \cdot V && \$ \\ V &\rightarrow \cdot \text{id} && \$ \\ V &\rightarrow \cdot * \, E && \$ \end{align*} }; \node (I5) [process, below=1cm of I3] { $I_4$ \vspace{-2ex} \begin{align*} S &\rightarrow E \cdot && \$ \end{align*} }; \node (I6) [process, below of=I1] { $I_5$ \vspace{-2ex} \begin{align*} V &\rightarrow * \cdot E && \$, = \\ E &\rightarrow \cdot V && \$, = \\ V &\rightarrow \cdot \text{id} && \$, =\\ V &\rightarrow \cdot * \, E && \$, = \end{align*} }; \node (I7) [process, below=1 cm of I5] { $I_6$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot && \$, = \end{align*} }; \node (I9) [process, right of=I4] { $I_8$ \vspace{-2ex} \begin{align*} S &\rightarrow V = E \cdot && \$ \end{align*} }; \node (I8) [process, below=1cm of I7] { $I_{7}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot && \$, = \end{align*} }; \node (I10) [process, below=1cm of I8] { $I_{9}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot && \$, = \end{align*} }; \node (I11) [process, below of=I4] { $I_{10}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, \cdot E && \$ \\ E &\rightarrow \cdot V && \$\\ V &\rightarrow \cdot \text{id} && \$\\ V &\rightarrow \cdot * \, E && \$ \end{align*} }; \draw [arrow] (I2) -- node[anchor=south] {\$} (A); \draw [arrow] (I1) -- node[anchor=east] {S} (I2); \draw [arrow] (I1) -- node[anchor=east] {V} (I3); \draw [arrow] (I3) -- node[anchor=south] {=} (I4); \draw [arrow] (I1) -- node[anchor=south] {E} (I5); \draw [arrow] (I1) -- node[anchor=east] {*} (I6); \path (I6) edge [loop below] node {*} (I6); \path (I11) edge [loop below] node {*} (I11); \draw [arrow] (I4) -- node[anchor=east, pos=0.9] {V} (I8); \draw [arrow] (I1) -- node[anchor=south] {id} (I7); \draw [arrow] (I4) -- node[anchor=south] {E} (I9); \draw [arrow] (I6) -- node[anchor=south] {E} (I10); \draw [arrow] (I6) -- node[anchor=south] {V} (I8); \draw [arrow] (I4) -- node[anchor=east, pos=0.8] {id} (I7); \draw [arrow] (I4) -- node[anchor=east] {*} (I11); \draw [arrow] (I11) -- node[anchor=south, pos=0.3] {E} (I10); \draw [arrow] (I11) -- node[anchor=south] {V} (I8); \draw [arrow] (I11) -- node[anchor=south] {id} (I7); \draw [arrow] (I6) -- node[anchor=south] {id} (I7); \end{tikzpicture}