CSE411: Introduction to Compilers

SLR, LR(0), LR(1) and LALR(1)

Jooyong Yi (UNIST)

How to construct a bottom-up parsing table

  1. Construct the LR(0) automaton.
  2. Construct the parsing table.

How to construct an LR(0) automaton

// 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)

SLR Parsing Table

---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   | s5             s4             |  1  2  3
   1   |       s6                  acc |
   2   |       r2  s7        r2     r2 |
   3   |       r4  r4        r4     r4 |
   4   | s5             s4             |  8  2  3
   5   |       r6  r6        r6     r6 |
   6   | s5             s4             |     9  3
   7   | s5             s4             |        10
   8   |       s6            s11       |  
   9   |       r1  s7        r1     r1 |
  10   |       r3  r3        r3     r3 |
  11   |       r5  r5        r5     r5 |
--------------------------------------------------                                                        

for each C -X-> C' in Edges
   if X is a terminal
      Action[C, X] = shift C'
   else if X is a nonterminal
      Goto[C, X] = C'


for each C in CS
   if C contains an item E' → E·
      Action[C, $] = accept


for each C in CS
   if C contains an item A → α·
      for each terminal t in FOLLOW(A)
         Action[C, t] = reduce A → α

SLR and LR(0)

// SLR (Simple LR)
for each C in CS
   if C contains an item A → α·
      for each terminal t in FOLLOW(A)
         Action[C, t] = reduce A → α                                                  

// LR(0)
for each C in CS
   if C contains an item A → α·
      for each terminal t
         Action[C, t] = reduce A → α

SLR and LR(0)

// SLR (Simple LR)
for each C in CS
   if C contains an item A → α·
      for each terminal t in FOLLOW(A)
         Action[C, t] = reduce A → α                                                                               

// LR(0)
for each C in CS
   if C contains an item A → α·
      for each terminal t
         Action[C, t] = reduce A → α                                                                             

SLR Table
---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   | s5             s4             |  1  2  3
   1   |       s6                  acc |
   2   |       r2  s7        r2     r2 |
   3   |       r4  r4        r4     r4 |
   4   | s5             s4             |  8  2  3
   5   |       r6  r6        r6     r6 |
   6   | s5             s4             |     9  3
   7   | s5             s4             |        10
   8   |       s6            s11       |  
   9   |       r1  s7        r1     r1 |
  10   |       r3  r3        r3     r3 |
  11   |       r5  r5        r5     r5 |
--------------------------------------------------

SLR and LR(0)

// SLR (Simple LR)
for each C in CS
   if C contains an item A → α·
      for each terminal t in FOLLOW(A)
         Action[C, t] = reduce A → α                                                                               

// LR(0)
for each C in CS
   if C contains an item A → α·
      for each terminal t
         Action[C, t] = reduce A → α                                                                             

LR(0) Table
------------------------------------------------------
       |     Action                       |  Goto  
 State |----------------------------------------------
       | id    +    *       (    )    $   |  E  T  F
 -----------------------------------------------------
   0   | s5                s4             |  1  2  3
   1   |       s6                     acc |
   2   | r2    r2  r2,s7   r2   r2     r2 |
   3   | r4    r4  r4      r4   r4     r4 |
   4   | s5                s4             |  8  2  3
   5   | r6    r6  r6      r6   r6     r6 |
   6   | s5                s4             |     9  3
   7   | s5                s4             |        10
   8   |       s6               s11       |  
   9   | r1    r1  r1,s7   r1   r1     r1 |
  10   | r3    r3  r3      r3   r3     r3 |
  11   | r5    r5  r5      r5   r5     r5 |
------------------------------------------------------

Grammars and LR Parsing

  |--------------------------------|
  |                                |
  |             SLR                |
  |      |--------------------|    |
  |      |                    |    |
  |      |      LR(0)         |    |
  |      |                    |    |
  |      |--------------------|    |
  |                                |
  |--------------------------------|

Construct an SLR Table

(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   |                          | 
   1   |                          |
   2   |              ??          |
   3   |                          |
   4   |                          |
   5   |                          |
   6   |                          |
   7   |                          |
   8   |                          |
   9   |                          |
  10   |                          |
--------------------------------------------------

Construct an SLR Table

(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   |                          | 
   1   |                          |
   2   |              r3,s4  r3   |
   3   |                          |
   4   |                          |
   5   |                          |
   6   |                          |
   7   |                          |
   8   |                          |
   9   |                          |
  10   |                          |
--------------------------------------------------

Why Does SLR Fail?

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

id = id $                                 
↑

Stack: 0

⇩

id = id $                                 
   ↑

Stack: 0 6

Why Does SLR Fail?

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

id = id $                                 
   ↑

Stack: 0 6

⇩

 V
 |
id = id $                                 
   ↑

Stack: 0 2

Why Does SLR Fail?

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

 V
 |
id = id $                                 
   ↑

Stack: 0 2

⇩

 E
 |
 V
 |
id = id $                                 
   ↑

Stack: 0 4

Why Does SLR Fail?

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

 E
 |
 V
 |
id = id $                                 
   ↑

Stack: 0 4

⇩?

     S
   / | \
  V  |  E
  |  |  |     
  |  |  V
  |  |  |
 id  =  id

Main Culprit: Follow Set

'=' ∈ Follow(E)                 '=' ∉ Follow(E) 

     S                                 S
   / | \                             / | \
  V  =  E                           V  =  E
 /\                                 |
*  E                               id
  • For a nonterminal A, Follow(A) is defined as the set of terminals that can (may) appear immediately to the right of A.

Solution: more sensitive to the context

LR(0) Automaton LR(1) Automaton
center center

Construct an LR(1) Table

(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   |                          | 
   1   |                          |
   2   |               s4    r3   |
   3   |                          |
   4   |                          |
   5   |                          |
   6   |                          |
   7   |                          |
   8   |                          |
   9   |                          |
  10   |                          |
--------------------------------------------------

Constructing an LR(1) Automaton

// Construct an LR(1) 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 → γ
            for any w ∈ FIRST(βz) // ADDED
               I = I ∪ {(X → ·γ, w)}
   until I does not change
   return I


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

Disadvantage of LR(1)

LR(0) Automaton LR(1) Automaton
center center

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

LR(1) Automaton LALR(1) Automaton
center center

Grammars and LR Parsing

  • LR(1)?, LALR(1)?
  |--------------------------------|
  |                                |
  |             SLR                |
  |      |--------------------|    |
  |      |                    |    |
  |      |      LR(0)         |    |
  |      |                    |    |
  |      |--------------------|    |
  |                                |
  |--------------------------------|

Grammars and LR Parsing

|----------------------------------------|
|                 LR(1)                  |
|   |--------------------------------|   |
|   |                                |   |
|   |             SLR                |   |
|   |      |--------------------|    |   |
|   |      |                    |    |   |
|   |      |      LR(0)         |    |   |
|   |      |                    |    |   |
|   |      |--------------------|    |   |
|   |                                |   |
|   |--------------------------------|   |
|                                        |
|----------------------------------------|

Grammars and LR Parsing

|----------------------------------------------|
|                  LR(1)                       |
|   |--------------------------------------|   |
|   |             LALR(1)                  |   |
|   |     |---------------------------|    |   |
|   |     |         SLR               |    |   |
|   |     |   |--------------------|  |    |   |
|   |     |   |                    |  |    |   |
|   |     |   |      LR(0)         |  |    |   |
|   |     |   |                    |  |    |   |
|   |     |   |--------------------|  |    |   |
|   |     |                           |    |   |
|   |     |---------------------------|    |   |
|   |                                      |   |
|   |--------------------------------------|   |
|                                              |
|----------------------------------------------|

Grammars and LR Parsing

  • LR(k)?
|----------------------------------------------|
|                  LR(1)                       |
|   |--------------------------------------|   |
|   |             LALR(1)                  |   |
|   |     |---------------------------|    |   |
|   |     |         SLR               |    |   |
|   |     |   |--------------------|  |    |   |
|   |     |   |                    |  |    |   |
|   |     |   |      LR(0)         |  |    |   |
|   |     |   |                    |  |    |   |
|   |     |   |--------------------|  |    |   |
|   |     |                           |    |   |
|   |     |---------------------------|    |   |
|   |                                      |   |
|   |--------------------------------------|   |
|                                              |
|----------------------------------------------|

Grammars and LR Parsing

  • LR(k)?
|-------------------------------------------------------------|
|                          LR(k)                              |
|      |----------------------------------------------|       |
|      |                  LR(1)                       |       |
|      |   |--------------------------------------|   |       |
|      |   |             LALR(1)                  |   |       |
|      |   |     |---------------------------|    |   |       |
|      |   |     |         SLR               |    |   |       |
|      |   |     |   |--------------------|  |    |   |       |
|      |   |     |   |                    |  |    |   |       |
|      |   |     |   |      LR(0)         |  |    |   |       |
|      |   |     |   |                    |  |    |   |       |
|      |   |     |   |--------------------|  |    |   |       |
|      |   |     |                           |    |   |       |
|      |   |     |---------------------------|    |   |       |
|      |   |                                      |   |       |
|      |   |--------------------------------------|   |       |
|      |                                              |       |
|      |----------------------------------------------|       |                                      
|-------------------------------------------------------------|

Grammars and Parsing

center

\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}