CSE411

CSE411: Introduction to Compilers

Parsing #6 (LR Parsing)

Jooyong Yi (UNIST)

2023 Spring
CSE411

Left-most Derivation and Top-Down Parsing

Top-down parsing performs left-most derivation.

2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

Bottom-up parsing is closely related to right-most derivation.

2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

  • Parse int * int + int using the right-most derivation.
2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

  • Parse int * int + int using the right-most derivation.
2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

  • Parse int * int + int using the right-most derivation.
  • The following diagram is copied from the previous lecture slide.
  • The diagram is obtained by reading the above derivation chain in reverse order.
                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
2023 Spring
CSE411

Right-most Derivation and Bottom-Up Parsing

  • The diagram is obtained by reading the above derivation chain in reverse order.
  • This is not a coincidence.
    • This happens because of the way how the shift/reduce operations are used during the bottom-up parsing.
                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
2023 Spring
CSE411

LR Parsing

  • Bottom-up parsing is also called LR parsing or a shift-reduce parsing.
  • L: scanning from left to right.
  • R: using the right-most derivation.
2023 Spring
CSE411

LR Parsing Table

Input
□□□□□□□□
  ↓
|---------|    Stack
| Control | ⇔  |__|
|  Unit   |    |__|
|---------|    |__|
  • We need a control unit that can resolve conflicts.
2023 Spring
CSE411

LR Parsing Table Example

  • Example 4.45 of the dragon book
Grammar SLR Parsing Table
center center
2023 Spring
CSE411

LR Parsing Table Example

  • Parse id * id + id
Stack Input Action
0/ id * id + id$ s5
0/ 5/id * id + id$ r6
0/ 3/F * id + id$ r4
0/ 2/T * id + id$ s7
0/ 2/T 7/* id + id$ s5
0/ 2/T 7/* 5/id + id$ r6
0/ 2/T 7/* 10/F + id$ r3
0/ 2/T + id$ r2
0/ 1/E + id$ s6
0/ 1/E 6/+ id$ s5
0/ 1/E 6/+ 5/id $ r6
0/ 1/E 6/+ 3/F $ r4
0/ 1/E 6/+ 9/T $ r1
0/ 1/E $ accept
2023 Spring
CSE411

Building an LR(0) Parsing Table

Grammar LR(0) Automaton Parsing Table
center center center
2023 Spring
CSE411

LR(0) Parsing Example: (int,int)

                                                                                        L                  L               L
                                                                                        |                  |               |
                                                    S                 S                 S                  S               S
          -s3->          -s2->           -r2(1)->   |       -r2(2)->  |       -r3(1)->  |       -r3(2)->   |       -s8->   |       -s2->
·(int,int)     (·int,int)      (int·,int)         (int·,int)        (int·,int)        (int·,int)         (int·,int)      (int,·int)
                           
  | 1 |           | 1 |           | 1 |            | 1 |              | 1 |             | 1 |              | 1 |            | 1 |
                  | 3 |           | 3 |            | 3 |              | 3 |             | 3 |              | 3 |            | 3 | 
                                  | 2 |                               | 7 |                                | 5 |            | 5 |
                                                                                                                            | 8 |

                                                                                                                 S                   S
                                                                                                               / | \               / | \
                                                             L                 L              L               /  L  \             /  L  \
                                                            /|\               /|\            /|\             |  /|\  |           |  /|\  |
    L                 L                 L                  L | |             L | |          L | |            | L | | |           | L | | |
    |                 |                 |                  | | |             | | |          | | |            | | | | |           | | | | |
    S                 S   S             S   S              S | S             S | S          S | S            | S | S |           | S | S |
    |       -r2(1)->  |   |   -r2(2)->  |   |   -r4(1)->   | | |   -r4(2)->  | | |   -s6->  | | |   -r1(1)-> | | | | |  -r1(2)-> | | | | |
  (int,int·)        (int,int·)        (int,int·)         (int,int·)        (int,int·)     (int,int)·         (int,int)·          (int,int)·
                           
    | 1 |             | 1 |             | 1 |             | 1 |              | 1 |           | 1 |            | 1 |                | 1 |
    | 3 |             | 3 |             | 3 |             | 3 |              | 3 |           | 3 |                                 | 4 |
    | 5 |             | 5 |             | 5 |                                | 5 |           | 5 |
    | 8 |             | 8 |             | 8 |                                                | 6 |
    | 2 |                               | 9 |
2023 Spring
CSE411

Closure of Item Sets

center

  • Item: a production with a dot indicating the scanner position
  • : the closure of an item set containing 
Closure(I) =
  repeat
     for any item A → α·Xβ in I
        for any production X → γ of G // G: Gramamr
           I := I ∪ {X → ·γ} 
  until I does not change
  return I
2023 Spring
CSE411

Accept Action

center

  • If the lookahead is $ at state 4, accept.
// Grammar whose 
// starting non-terminal
// is S
                                          S'→ S $
S → ...                   --convert-->    S → ...
2023 Spring
CSE411

Example of a Non-LR(0) Grammar

Grammar LR(0) Automaton Parsing Table
center center center
2023 Spring
CSE411

Example of a Conflict: int+int

                                           E
                                           |
                            T              T
        -s5->        -r3->  |        -r2-> |
·int+int     int·+int      int·+int       int·+int 
  
  | 1 |        | 1 |         | 1 |          | 1 |
               | 5 |         | 3 |          | 2 |
2023 Spring
CSE411

Example of a Conflict: int+int

                                           E
                                           |
                            T              T
        -s5->        -r3->  |        -r2-> |
·int+int     int·+int      int·+int       int·+int 
  
  | 1 |        | 1 |         | 1 |          | 1 |
               | 5 |         | 3 |          | 2 |
  • Problem: + cannot follow E.
2023 Spring
CSE411

Building a SLR (Simple LR) Parsing Table

Grammar LR(0) Automaton Follow Parsing Table
center center center center
2023 Spring
CSE411

Example of a Non-SLR Grammar

Grammar LR(0) Automaton Follow Parsing Table
center center center center
2023 Spring
CSE411

Example of a Conflict: id=id

                                  E
                                  |
                       V          V
      -s7->      -r4-> |    -r3-> |
·id=id     id·=id     id·=id     id·=id
 
 | 1 |      | 1 |      | 1 |      | 1 |
            | 7 |      | 3 |      | 5 |
2023 Spring
CSE411

Example of a Conflict: id=id

                                  E
                                  |
                       V          V
      -s7->      -r4-> |    -r3-> |
·id=id     id·=id     id·=id     id·=id
 
 | 1 |      | 1 |      | 1 |      | 1 |
            | 7 |      | 3 |      | 5 |
  • Problem: = follows E only in a specific context.
Case 1: = follows E          Case 2: = does not follow E

     S                                 S
   / | \                             / | \
  V  =  E                           V  =  E
 /\                                 |
*  E                               id
2023 Spring
CSE411

LR(1) Automaton

  • Distinguish different contexts with lookaheads
Grammar LR(0) Automaton LR(1) Automaton
center center center
2023 Spring
CSE411

Building an LR(1) Parsing Table

Grammar LR(1) Automaton Parsing Table
center center center
2023 Spring
CSE411

Constructing an LR(1) Automaton

center

Closure(I) =
  repeat
     for any item (A → α·Xβ, z) in I
        for any production X → γ of G // G: Gramamr
           for any w ∈ FIRST(βz)
              I := I ∪ {(X → ·γ, w)} 
  until I does not change
  return I
2023 Spring
CSE411

LR(1) Parsing Table vs SLR Prasing Table

  • | LR(1) parsing table | > | SLR parsing table |
Grammar LR(1) Parsing Table SLR Parsing Table
center center center
2023 Spring
CSE411

LR(1) Automaton vs LALR(1) Automaton

  • LALR(1): Look-Ahead LR(1)
  • Merge the item sets whose core (the part without the lookahead) is the same.
Grammar LR(1) Automaton LALR(1) Automaton
center center center
2023 Spring
CSE411

SLR Automaton vs LALR(1) Automaton

Grammar SLR Automaton LALR(1) Automaton
center center center
2023 Spring
CSE411

SLR Parsing Table vs LALR(1) Parsing Table

Grammar SLR Parsing Table LALR(1) Parsing Table
center center center
2023 Spring
CSE411

Hierarchy between Grammars (LR(k))

center

2023 Spring
CSE411

Hierarchy between Grammars (SLR)

center

2023 Spring
CSE411

Hierarchy between Grammars (LALR)

center

2023 Spring
CSE411

Hierarchy between Grammars (LL(k) vs LR(k))

center

2023 Spring
CSE411

Hierarchy between Grammars (Overall)

center

2023 Spring

\begin{align*} (0) \,\, S' &\rightarrow S \$ \\ (1) \,\, S &\rightarrow ( L ) \\ (2) \,\, S &\rightarrow \text{int} \\ (3) \,\, L &\rightarrow S \\ (4) \,\, L &\rightarrow L , S \end{align*}

\begin{tabular}{c|ccccc|cc}\toprule \multirow{2}{*}{State} & \multicolumn{5}{c}{Action} & \multicolumn{2}{c}{GOTO} \\ \cline{2-8} & ( & ) & int & , & \$ & S & L \\ \midrule 1 & s3 & & s2 & & & 4 \\ 2 & r2 & r2 & r2 & r2 & r2 & \\ 3 & s3 & & s2 & & & 7 & 5\\ 4 & & & & & a &\\ 5 & & s6 & & s8 & & \\ 6 & r1 & r1 & r1 & r1 & r1 & \\ 7 & r3 & r3 & r3 & r3 & r3 & \\ 8 & s3 & & s2 & & & 9 &\\ 9 & r4 & r4 & r4 & r4 & r4 & \\ \end{tabular}

\begin{tikzpicture}[node distance=2.7cm] \node (I1) [process] { $I_1$ \vspace{-2ex} \begin{align*} S' &\rightarrow \cdot S \$ \\ S &\rightarrow \cdot (L) \\ S &\rightarrow \cdot \text{int} \end{align*} }; \node (I2) [process, right of=I1] { $I_2$ \vspace{-2ex} \begin{align*} S \rightarrow \text{int} \cdot \end{align*} }; \node (I3) [process, below of=I2] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow ( \cdot L ) \\ L &\rightarrow \cdot S \\ L &\rightarrow \cdot L , S \\ S &\rightarrow \cdot ( L ) \\ S &\rightarrow \cdot \text{int} \end{align*} }; \node (I4) [process, below=2.4cm of I1] { $I_4$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot \$ \end{align*} }; \node (I5) [process, right of=I3] { $I_5$ \vspace{-2ex} \begin{align*} S &\rightarrow ( L \cdot ) \\ L &\rightarrow L \cdot , S \end{align*} }; \node (I6) [process, below of=I5] { $I_6$ \vspace{-2ex} \begin{align*} S &\rightarrow ( L ) \cdot \end{align*} }; \node (I7) [process, below of=I3] { $I_7$ \vspace{-2ex} \begin{align*} L &\rightarrow S \cdot \end{align*} }; \node (I8) [process, right of=I2] { $I_8$ \vspace{-2ex} \begin{align*} L &\rightarrow L , \cdot S \\ S &\rightarrow \cdot ( L )\\ S &\rightarrow \cdot \text{int} \end{align*} }; \node (I9) [process, right of=I8] { $I_9$ \vspace{-2ex} \begin{align*} L &\rightarrow L , S \cdot \end{align*} }; \draw [arrow] (I1) -- node[anchor=south] {int} (I2); \draw [arrow] (I1) -- node[anchor=east] {(} (I3); \draw [arrow] (I3) -- node[anchor=east] {int} (I2); \draw [arrow] (I1) -- node[anchor=east] {S} (I4); \path (I3) edge [loop left] node {(} (I3); \draw [arrow] (I3) -- node[anchor=south] {L} (I5); \draw [arrow] (I5) -- node[anchor=east] {)} (I6); \draw [arrow] (I3) -- node[anchor=east] {S} (I7); \draw [arrow] (I8) -- node[anchor=south] {int} (I2); \draw [arrow] (I8) -- node[anchor=south] {(} (I3); \draw [arrow] (I5) -- node[anchor=east] {,} (I8); \draw [arrow] (I8) -- node[anchor=south] {S} (I9); \end{tikzpicture}

\begin{tikzpicture}[node distance=2.7cm] \node (I1) [process] { $I_1$ \vspace{-2ex} \begin{align*} S' &\rightarrow \cdot S \$ \\ S &\rightarrow \cdot (L) \\ S &\rightarrow \cdot \text{int} \end{align*} }; \end{tikzpicture}

\begin{tikzpicture}[node distance=2.7cm] \node (I4) [process] { $I_4$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot \$ \end{align*} }; \end{tikzpicture}

\begin{align*} (0) \,\, S &\rightarrow E \$ \\ (1) \,\, E &\rightarrow T + E \\ (2) \,\, E &\rightarrow T \\ (3) \,\, T &\rightarrow \text{int} \end{align*}

\begin{tikzpicture}[node distance=2.5cm] \node (I1) [process] { $I_1$ \vspace{-2ex} \begin{align*} S &\rightarrow \cdot E & \\ E &\rightarrow \cdot T + E \\ E &\rightarrow \cdot T \\ T &\rightarrow \cdot \text{int} \end{align*} }; \node (I2) [process, right of=I1] { $I_2$ \vspace{-2ex} \begin{align*} S \rightarrow E \cdot \$ \end{align*} }; \node (I3) [process, below of=I2] { $I_3$ \vspace{-2ex} \begin{align*} E &\rightarrow T \cdot + E \\ E &\rightarrow T \cdot \end{align*} }; \node (I4) [process, below of=I3] { $I_4$ \vspace{-2ex} \begin{align*} E &\rightarrow T + \cdot E \\ E &\rightarrow \cdot T + E \\ E &\rightarrow \cdot T \\ T &\rightarrow \cdot \text{int} \end{align*} }; \node (I5) [process, below of=I1] { $I_5$ \vspace{-2ex} \begin{align*} T &\rightarrow \text{int} \cdot \end{align*} }; \node (I6) [process, right of=I4] { $I_6$ \vspace{-2ex} \begin{align*} E \rightarrow T + E \cdot \end{align*} }; \draw [arrow] (I1) -- node[anchor=south] {E} (I2); \draw [arrow] (I1) -- node[anchor=east] {T} (I3); \draw [arrow] (I1) -- node[anchor=east] {int} (I5); \draw [arrow] (I3.east) .. controls +(right:10mm) .. node[anchor=east] {+} (I4.east); \draw [arrow] (I4) -- node[anchor=east] {T} (I3); \draw [arrow] (I4) -- node[anchor=east] {int} (I5); \draw [arrow] (I4) -- node[anchor=north] {E} (I6); \end{tikzpicture}

\begin{tabular}{c|ccc|cc}\toprule \multirow{2}{*}{State} & \multicolumn{3}{c}{Action} & \multicolumn{2}{c}{GOTO} \\ \cline{2-6} & int & + & \$ & E & T \\ \midrule 1 & s5 & & & 2 & 3 \\ 2 & & & a & & \\ 3 & r2 & r2, s4 & r2 \\ 4 & s5 & & & 6 & 3 \\ 5 & r3 & r3 & r3 & \\ 6 & r1 & r1 & r1 \\ \end{tabular}

\begin{tabular}{c|ccc|cc}\toprule \multirow{2}{*}{State} & \multicolumn{3}{c}{Action} & \multicolumn{2}{c}{GOTO} \\ \cline{2-6} & int & + & \$ & E & T \\ \midrule 1 & s5 & & & 2 & 3 \\ 2 & & & a & & \\ 3 & \st{r2} & \st{r2,} s4 & r2 \\ 4 & s5 & & & 6 & 3 \\ 5 & \st{r3} & r3 & r3 & \\ 6 & \st{r1} & \st{r1} & r1 \\ \end{tabular}

\begin{align*} \text{Follow}(S) &= \{\$\} \\ \text{Follow}(E) &= \{\$\} \\ \text{Follow}(T) &= \{+, \$\} \end{align*}

\begin{align*} (0) \,\, S' &\rightarrow S \$ \\ (1) \,\, S &\rightarrow V = E \\ (2) \,\, S &\rightarrow E \\ (3) \,\, E &\rightarrow V \\ (4) \,\, V &\rightarrow \text{id} \\ (5) \,\, V &\rightarrow * \, E \end{align*}

\begin{tikzpicture}[node distance=3.5cm] \node (I1) [process] { $I_1$ \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_2$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot \$ \end{align*} }; \node (I3) [process, right of=I2] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow V \cdot = E \\ E &\rightarrow V \cdot \end{align*} }; \node (I4) [process, right of=I3] { $I_4$ \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_5$ \vspace{-2ex} \begin{align*} S &\rightarrow E \cdot \end{align*} }; \node (I6) [process, below of=I1] { $I_6$ \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_7$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot \end{align*} }; \node (I9) [process, right of=I4] { $I_9$ \vspace{-2ex} \begin{align*} S &\rightarrow V = E \cdot \end{align*} }; \node (I8) [process, below=1cm of I7] { $I_{8}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot \end{align*} }; \node (I10) [process, below=1cm of I8] { $I_{10}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot \end{align*} }; \node (I11) [process, below of=I4] { $I_{11}$ \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] (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{tabular}{c|cccc|ccc}\toprule \multirow{2}{*}{State} & \multicolumn{4}{c}{Action} & \multicolumn{3}{c}{GOTO} \\ \cline{2-8} & id & * & = & \$ & S & E & V \\ \midrule 1 & s7 & s6 & & & 2 & 5 & 3 \\ 2 & & & & a & & & \\ 3 & & & r3,s4 & r3 & \\ 4 & s7 & s11 & & & & 9 & 8 \\ 5 & & & & r2 & \\ 6 & s7 & s6 & & & & 10 & 8 \\ 7 & & & r4 & r4 & \\ 8 & & & r3 & r3 & \\ 9 & & & & r1 &\\ 10 & & & r5 & r5 &\\ 11 & s7 & s11 & & & & 10 & 8 \end{tabular}

\begin{tikzpicture}[node distance=3.6cm] \node (I1) [process] { $I_1$ \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_2$ \vspace{-2ex} \begin{align*} S' &\rightarrow S \cdot \$ && ? \end{align*} }; \node (I3) [process, right of=I2] { $I_3$ \vspace{-2ex} \begin{align*} S &\rightarrow V \cdot = E && \$ \\ E &\rightarrow V \cdot && \$ \end{align*} }; \node (I4) [process, right of=I3] { $I_4$ \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_5$ \vspace{-2ex} \begin{align*} S &\rightarrow E \cdot && \$ \end{align*} }; \node (I6) [process, below of=I1] { $I_6$ \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_7$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot && \$, = \end{align*} }; \node (I9) [process, right of=I4] { $I_9$ \vspace{-2ex} \begin{align*} S &\rightarrow V = E \cdot \end{align*} }; \node (I8) [process, below=1cm of I7] { $I_{8}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot && \$, = \end{align*} }; \node (I10) [process, below=1cm of I8] { $I_{10}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot && \$, = \end{align*} }; \node (I11) [process, below of=I4] { $I_{11}$ \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_{12}$ \vspace{-2ex} \begin{align*} V &\rightarrow \text{id} \cdot && \$ \end{align*} }; \node (I13) [process, below=1.2cm of I12] { $I_{13}$ \vspace{-2ex} \begin{align*} E &\rightarrow V \cdot && \$ \end{align*} }; \node (I14) [process, below=1cm of I13] { $I_{14}$ \vspace{-2ex} \begin{align*} V &\rightarrow * \, E \cdot && \$ \end{align*} }; \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{tabular}{c|cccc|ccc}\toprule \multirow{2}{*}{State} & \multicolumn{4}{c}{Action} & \multicolumn{3}{c}{GOTO} \\ \cline{2-8} & id & * & = & \$ & S & E & V \\ \midrule 1 & s7 & s6 & & & 2 & 5 & 3 \\ 2 & & & & a & & & \\ 3 & & & s4 & r3 & \\ 4 & s12 & s11 & & & & 9 & 13 \\ 5 & & & & r2 & \\ 6 & s7 & s6 & & & & 10 & 8 \\ 7 & & & r4 & r4 & \\ 8 & & & r3 & r3 & \\ 9 & & & & r1 &\\ 10 & & & r5 & r5 &\\ 11 & s12 & s11 & & & & 9 & 13 \\ 12 & & & & r4 & \\ 13 & & & & r3 & \\ 14 & & & & r5 & \end{tabular}

\begin{tikzpicture}[node distance=2.7cm] \node (I1) [process] { $I_1$ \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*} }; \end{tikzpicture}

\begin{tabular}{c|cccc|ccc}\toprule \multirow{2}{*}{State} & \multicolumn{4}{c}{Action} & \multicolumn{3}{c}{GOTO} \\ \cline{2-8} & id & * & = & \$ & S & E & V \\ \midrule 1 & s7 & s6 & & & 2 & 5 & 3 \\ 2 & & & & a & & & \\ 3 & & & s4 & r3 & \\ 4 & s7 & s11 & & & & 9 & 8 \\ 5 & & & & r2 & \\ 6 & s7 & s6 & & & & 10 & 8 \\ 7 & & & r4 & r4 & \\ 8 & & & r3 & r3 & \\ 9 & & & & r1 &\\ 10 & & & r5 & r5 &\\ 11 & s7 & s11 & & & & 10 & 8 \end{tabular}

\def\lrzero{(0,0) ellipse (1cm and 0.5cm)} \def\lrone{(60:2cm) circle (1.5cm)} \def\thirdcircle{(0:2cm) circle (1.5cm)} \begin{tikzpicture} \begin{scope}[shift={(3cm,-5cm)}, fill opacity=0.5] \draw \lrzero node {LR(0)}; \draw \lrone node [above] {$B$}; \draw \thirdcircle node [below] {$C$}; \end{scope} \end{tikzpicture}

\def\lrzero{(0,0) ellipse (0.6cm and 0.5cm)} \def\lrone{(0,0) ellipse (2.6cm and 2.5cm)} \def\lrk{(0,0) ellipse (3.6cm and 3.5cm)} \def\slr{(0,0) ellipse (1.6cm and 1.5cm)} \begin{tikzpicture} \begin{scope}[shift={(3cm,-5cm)}] \draw \lrzero node (LR0) {LR(0)}; \draw \slr node (SLR) [above=0.6cm of LR0] {SLR}; \draw \lrone node (LR1) [above=0.6cm of SLR] {LR(1)}; \draw \lrk node (LRk) [above=0.5cm of LR1] {LR(k)}; \end{scope} \end{tikzpicture}

\def\lrzero{(0,0) ellipse (0.6cm and 0.5cm)} \def\slr{(0,0) ellipse (1.6cm and 1.5cm)} \def\lalr{(0,0) ellipse (2.6cm and 2.5cm)} \def\lrone{(0,0) ellipse (3.6cm and 3.5cm)} \def\lrk{(0,0) ellipse (4.6cm and 4.5cm)} \begin{tikzpicture} \begin{scope}[shift={(3cm,-5cm)}] \draw \lrzero node (LR0) {LR(0)}; \draw \slr node (SLR) [above=0.6cm of LR0] {SLR}; \draw \lalr node (LALR1) [above=0.4cm of SLR] {LALR(1)}; \draw \lrone node (LR1) [above=0.4cm of LALR1] {LR(1)}; \draw \lrk node (LRk) [above=0.4cm of LR1] {LR(k)}; \end{scope} \end{tikzpicture}

\def\llk{(0,0) ellipse (0.6cm and 0.5cm)} \def\lrk{(0,0) ellipse (1.6cm and 1.5cm)} \begin{tikzpicture} \begin{scope}[shift={(3cm,-5cm)}] \draw \llk node (LLk) {LL(k)}; \draw \lrk node (LRk) [above=0.6cm of LLk] {LR(k)}; \end{scope} \end{tikzpicture}