CSE411: Introduction to Compilers

Bottom-Up Parsing

Jooyong Yi (UNIST)

Parsing Technique and Grammar

E: E + E | T           E: E + T | T         E : T E'
T: T * T | F   ==>     T: T * F | F   ==>   E': + T E' | ε
F: (E) | int           F: (E) | int         T : F T'
                                            T': * F T' | ε
                                            F: (E) | int         

• The grammar is restricted by the parsing technique.

Parsing Technique and Grammar

E : E + T  { $$ = $1 + $3; }
  | T      { $$ = $1; }
T : T * F  { $$ = $1 * $3; }
F : (E)    { $$ = $2; }
  | int    { $$ = $1; }

Parsing Technique and Grammar

E: E + E | T           E: E + T | T         E : T E'
T: T * T | F   ==>     T: T * F | F   ==>   E': + T E' | ε
F: (E) | int           F: (E) | int         T : F T'
                                            T': * F T' | ε
                                            F: (E) | int         

// Difficult to work with the converted grammar
E : T E'      { ??? }
E' : + T E'   { ??? }
...

Top-Down Parsing vs. Bottom-Up Parsing

// Grammar G
E : E '+' E | int

Top-Down parsing uses the leftmost derivation.

E →     E   →      E    →      E
       /|\        /|\         /|\
      E + E      E + E       E + E
                 |           |   |
                int         int  int

Bottom-Up parsing uses the rightmost derivation.

                                       E
                                    /  |  \
 E               E       E         E   |   E
 |               |       |         |   |   |
int '+' int  →  int '+' int   →   int '+' int

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

id * id + id $                                                                                                           
 ↑

Stack: 0

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

id * id + id $                                                                                                           
   ↑

Stack: 0 5

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 F
 |
id * id + id $                                                                                                           
   ↑

Stack: 0

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 F
 |
id * id + id $                                                                                                           
   ↑

Stack: 0 3

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 T
 |
 F
 |
id  * id + id $                                                                                                           
    ↑

Stack: 0

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 T
 |
 F
 |
id * id + id $                                                                                                           
   ↑

Stack: 0 2

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 T
 |
 F
 |
id * id + id $                                                                                                           
      ↑

Stack: 0 2 7

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 T
 |
 F
 |
id  * id  + id $                                                                                                           
          ↑

Stack: 0 2 7 5

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                 

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

 T
 |
 F     F
 |     |
id  * id  + id $                                                                                                           
          ↑

Stack: 0 2 7 

Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

 T
 |
 F     F
 |     |
id  * id  + id $                                                                                                           
          ↑

Stack: 0 2 7 10 

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id $                                                                                                           
          ↑

Stack: 0

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id $                                                                                                           
          ↑

Stack: 0 2

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id $                                                                                                           
          ↑

Stack: 0

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id $                                                                                                           
          ↑

Stack: 0 1

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id $                                                                                                           
             ↑

Stack: 0 1 6

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                  

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1 6 5

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F     F
 |  |  |     |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1 6

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

    E
    |
    T
  / | \
 T  |  |
 |  |  |
 F  |  F     F
 |  |  |     |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1 6 3

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

    E
    |
    T
  / | \
 T  |  |     T
 |  |  |     |
 F  |  F     F
 |  |  |     |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1 6

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

    E
    |
    T
  / | \
 T  |  |     T
 |  |  |     |
 F  |  F     F
 |  |  |     |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1 6 9

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

          E
     /    |  \
    E     |  |
    |     |  |
    T     |  |
  / | \   |  |
 T  |  |  |  T
 |  |  |  |  |
 F  |  F  |  F
 |  |  |  |  |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id                                                                                                   

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

          E
     /    |  \
    E     |  |
    |     |  |
    T     |  |
  / | \   |  |
 T  |  |  |  T
 |  |  |  |  |
 F  |  F  |  F
 |  |  |  |  |
id  * id  + id  $                                                                                                           
                ↑

Stack: 0 1

How to Construct a Bottom-Up Parsing Table

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   |                               | 
   1   |                               |
   2   |                               |
   3   |                               |
   4   |                               | 
   5   |                               |
   6   |                               | 
   7   |                               | 
   8   |                               |  
   9   |                               |
  10   |                               |
  11   |                               |
-------------------------------------------------- 

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

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   | s5              s4            |  1  2  3
   1   |                               |
   2   |                               |
   3   |                               |
   4   |                               | 
   5   |                               |
   6   |                               | 
   7   |                               | 
   8   |                               |  
   9   |                               |
  10   |                               |
  11   |                               |
-------------------------------------------------- 

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

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   | s5              s4            |  1  2  3
   1   |       s6                 acc  |
   2   |                               |
   3   |                               |
   4   |                               | 
   5   |                               |
   6   |                               | 
   7   |                               | 
   8   |                               |  
   9   |                               |
  10   |                               |
  11   |                               |
-------------------------------------------------- 

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

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

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

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

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

FOLLOW(E) = {$, +, )}

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

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

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

FOLLOW(T) = {$, *, +, )}

---------------------------------------------------
       |  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   |                               | 
   5   |                               |
   6   |                               | 
   7   |                               | 
   8   |                               |  
   9   |                               |
  10   |                               |
  11   |                               |
-------------------------------------------------- 

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

Reflection

id * id + id $                                 
↑

Stack: 0

⇩

id * id + id $                                 
   ↑

Stack: 0 5(id)

E' =rm*=> id * id + id $                              
             ↑

id * id + id $                                 
   ↑

Stack: 0 5(id)

⇩

 F
 |
id * id + id $                                 
   ↑

Stack: 0 3(F)

E' =rm*=> F * id + id $ =rm*=> id * id + id $
            ↑                     ↑

 F
 |
id * id + id $                                 
   ↑

Stack: 0 3(F)

⇩

 T
 |
 F
 |
id * id + id $                                 
   ↑

Stack: 0 2(T)

E' =rm*=> T * id + id $ =rm=> F * id + id $ =rm*=> id * id + id $
            ↑                   ↑                     ↑

 T
 |
 F
 |
id * id + id $                                 
   ↑

Stack: 0 2(T)

⇩

 T
 |
 F
 |
id * id + id $                                 
        ↑

Stack: 0 2(T) 7(*) 5(id)

E' =rm*=> T * id + id $ =rm=> F * id + id $ =rm*=> id * id + id $
                 ↑                   ↑                     ↑

 T
 |
 F
 |
id * id + id $                                 
        ↑

Stack: 0 2(T) 7(*) 5(id)

⇩

 T
 |
 F    F
 |    |
id * id + id $                                 
        ↑

Stack: 0 2(T) 7(*) 10(F)

E' =rm*=> T * F + id $ =rm=> T * id + id $ 
   =rm=> F * id + id $ =rm*=> id * id + id $

 T
 |
 F    F
 |    |
id * id + id $                                 
        ↑

Stack: 0 2(T) 7(*) 10(F)

⇩

    T
  / | \
 T  |  |
 |  |  |
 F  |  F
 |  |  |
id * id + id $                                 
        ↑

Stack: 0

E' =rm*=> T + id $ =rm=> T * F + id $
   =rm=> T * id + id $ 
   =rm=> F * id + id $ =rm*=> id * id + id $