CSE411: Introduction to Compilers

Bottom-Up Parsing

Jooyong Yi (UNIST)

LL(1) Example

                              left
E: E + T | T                recursion        E:  T E'
T: T * T | INT | ( E )  == elimination =>    E': + T E' | ε
                                             T:  F T'
                                             T': * F T' | ε
                                             F: INT | (E)

-------------------------------------------------    
   |  int  |  +     |   *   |  (    |  )  |  $  |    
-------------------------------------------------    
E  |  T E' |        |       | T E'  |     |     |    
E' |       | + T E' |       |       |  ε  |  ε  |    
T  |  F T' |        |       | F T'  |     |     |    
T' |       |  ε     | * F T'|       |  ε  |  ε  |    
F  |  int  |        |       |  (E)  |     |     |    
-------------------------------------------------    

Grammar that cannot be handled by LL(1)

E: E + T | T | T + INT  == elimination => E:  T E' | T + INT E'  == left factoring => E:  T X
T: T * T | INT | ( E )                    E': + T E' | ε                              X:  E' | + INT E'
                                          T:  INT T' | ( E ) T'                       E': + T E' | ε
                                          T': * T T' | ε                              T: INT T' | ( E ) T'
                                                                                      T': * T T' | ε

--------------------------------------------------------------------------
   |   INT   |        +         |       *        |    (     |  )  |  $  |
--------------------------------------------------------------------------
E  |  T X    |                  |                |  T X    |     |     |
X  |         | { E', + INT E' } |                |         |  ε  |  ε  |
E' |         |  + T E'          |                |         |  ε  |  ε  |
T  | INT T'  |                  |                | (E) T'  |     |     |
T' |         |  ε               | { * T T', ε }  |         |  ε  |  ε  |
--------------------------------------------------------------------------

How can we go beyond LL(1)?

Is it LL(1)?

S: INT +
S: INT *

Is it LL(2)?

S: INT INT +
S: INT INT *

Top-Down Parsing

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

E →     E   →      E    →      E     →     E
       /|\        /|\         /|\         /|\
      E + T      E + T       E + T       E + T
                 |           |           |   |
                 T           T           T  INT
                             |           |
                            INT         INT

Bottom-Up Approach

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

           
           
 T         
 |         
INT + INT  
 ↑

Bottom-Up Approach

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

 E           
 |          
 T         
 |         
INT + INT  
 ↑

Bottom-Up Approach

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

 E          
 |          
 T         
 |         
INT + INT  
    ↑

Bottom-Up Approach

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

 E          
 |           
 T     T    
 |     |    
INT + INT  
       ↑

Bottom-Up Approach

// Grammar G
E : E + T | T
T : INT

// Input
INT + INT

    E
 /  |  \
 E  |  |     
 |  |  |      
 T  |  T    
 |  |  |    
INT + INT  
       ↑

Bottom-Up Approach

// Left-Recursive Grammar G
E : E + T | T
T : INT

// Input
INT + INT

    E
 /  |  \
 E  |  |     
 |  |  |      
 T  |  T    
 |  |  |    
INT + INT  
       ↑

Bottom-Up Approach

1. Repeat to read the next token until the end of the input is reached
   1. Check whether the current sequence of tokens matches the right-hand side of any production rule. If it does, reduce the sequence to the corresponding non-terminal symbol and return to step 1.
   2. Otherwise, accumulate the current token and return to step 1.

LR(1) Parsing

• L: scanning from left to right.
• R:
• 1: using one lookahead token.

LR(1) Parsing

• L: scanning from left to right.
• R: using the right-most derivation.
• 1: using one lookahead token.

Top-Down Parsing

E : E + T | T
T : INT

Top-down parsing uses the leftmost derivation.

E →     E   →      E    →      E     →     E
       /|\        /|\         /|\         /|\
      E + T      E + T       E + T       E + T
                 |           |           |   |
                 T           T           T  INT
                             |           |
                            INT         INT

Bottom-Up Parsing

E : E + T | T
T : INT

                                                                 E
                                                             /   |  \
                            E               E                E   |   |
                            |               |                |   |   |
              T             T               T       T        T   |   T
              |             |               |       |        |   |   |
INT + INT  → INT + INT  →  INT + INT   →   INT  +  INT  →   INT  +  INT

Bottom-Up Parsing

E : E + T | T
T : INT

Bottom-up parsing uses the rightmost derivation in reverse.
                                                                 E
                                                             /   |  \
                            E               E                E   |   |
                            |               |                |   |   |
              T             T               T       T        T   |   T
              |             |               |       |        |   |   |
INT + INT  → INT + INT  →  INT + INT   →   INT  +  INT  →   INT  +  INT

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                             

INT + INT $
 ↑
                                                                                                  
Stack: 0

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                             

INT + INT $  ==>  INT + INT $
 ↑                    ↑
                                                                                                  
Stack: 0     ==>  Stack: 0 3

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                             

                  T
                  |
INT + INT $  ==> INT + INT $
    ↑                ↑
                                                                                                  
Stack: 0 3   ==> Stack: 0 2

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

                   E
                   |
 T                 T 
 |                 |
INT + INT $   ==> INT + INT $
    ↑                 ↑                
                                                                                                                      
Stack: 0 2  ==> Stack: 0 1

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

 E                 E
 |                 |
 T                 T 
 |                 |
INT + INT $   ==> INT + INT $
    ↑                    ↑                
                                                                                                              
Stack: 0 1  ==> Stack: 0 1 4

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

 E                 E
 |                 |
 T                 T 
 |                 |
INT + INT $   ==> INT + INT $
       ↑                    ↑                
                                                                                                                     
Stack: 0 1 4  ==> Stack: 0 1 4 3

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

 E                  E 
 |                  | 
 T                  T     T
 |                  |     |
INT + INT $    ==> INT + INT $
          ↑                  ↑                
                                                                                                                     
Stack: 0 1 4 3 ==> Stack: 0 1 4 5

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

                       E
                    /  | \
 E                  E  |  | 
 |                  |  |  | 
 T     T            T  |  T
 |     |            |  |  |
INT + INT $    ==> INT + INT $
          ↑                  ↑                
                                                                                                                     
Stack: 0 1 4 5 ==> Stack: 0 1

Bottom-Up Parsing Table

(1) E : E + T 
(2) E : T
(3) T : INT                                                                                     

------------------------------------
      |    Action       |   Goto
State |-----------------|-----------
      | INT |  +  |  $  |  E  |  T
------------------------------------
  0   | s3  |     |     |  1  |  2
  1   |     | s4  | acc |     |
  2   |     | r2  | r2  |     |
  3   |     | r3  | r3  |     |
  4   | s3  |     |     |     |  5
  5   |     | r1  | r1  |     |
------------------------------------                                                                              

    E
 /  | \
 E  |  | 
 |  |  | 
 T  |  T
 |  |  |
INT + INT $
          ↑                  
                                                                                                                     
Stack: 0 1    ==> Accept and $ are reached.