CSE411

CSE411: Introduction to Compilers

Parsing #5 (Bottom-Up Parsing)

Jooyong Yi (UNIST)

2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
int * int + int
   ↑
scanner
position
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
 T
 |
int * int + int
   ↑
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
 E
 |
 T
 |
int * int + int
   ↑
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
 E
 |
 T
 |
int * int + int
     ↑
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
 E
 |
 T
 |
int * int + int
     ↑
  • We are stuck!
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
int * int + int
     ↑
  • Backtrack
2023 Spring
CSE411

Bottom-Up Parsing

  • Parse int * int + int
       T
       |
int * int + int
         ↑
2023 Spring
CSE411

Bottom-Up Parsing

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

Bottom-Up Parsing

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

Bottom-Up Parsing

  • Parse int * int + int
                                                                  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
⠀

Top-Down Parsing vs Bottom-Up Parsing

    E                    E                    E                    E
   /|\         ->       /|\    ->         /    | \     ->     /     | \
  T + E                T + E             T     +  E          T      +  E
                      /|\               /|\                 /|\        |
                   int * T           int * T              int * T      T
                                           |                    |      |
                                           int                  int   int

 int * int + int   int * int + int   int * int + int      int * int + int
↑                       ↑                       ↑                        ↑
lookahead

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

Top-Down Parsing vs Bottom-Up Parsing

  • Top-down parsing
    • The leftmost non-terminal derives a production.
2023 Spring
CSE411

Top-Down Parsing vs 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
         ↑                   ↑                        ↑                  ↑
  • We reduce int to T
  • We reduce int * T to T
  • We reduce T to E
  • We reduce T + E to E
2023 Spring
CSE411

Top-Down Parsing vs Bottom-Up Parsing

  • We reduce int to T
  • We reduce int * T to T
  • We reduce T to E
  • We reduce T + E to E
2023 Spring
CSE411

Why Bottom-Up Parsing?

  • The above grammar is not LL(1).
    • The grammar should be converted to perform LL(1) parsing (e.g., left factoring).
  • There exists a bottom-up parser that can handle the above grammar.
2023 Spring
CSE411

Why Bottom-Up Parsing?

2023 Spring
CSE411

Why Bottom-Up Parsing?

  • But, left factoring can be done automatically.
  • Parsing is just part of compilation.
// Specify how to handle addition 
E : T '+' E  { $$ = $1 + $3; }
2023 Spring
CSE411

Why Bottom-Up Parsing?

  • But, left factoring can be done automatically.
  • Parsing is just part of compilation.
// Specify how to handle addition 
E : T '+' E  { $$ = $1 + $3; }

// Difficult to work with the converted grammar
E : T X     { ??? }
X : '+' E   { ??? }
2023 Spring
CSE411

Key Operations of Bottom-Up Parsing

2023 Spring
CSE411

Shift operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
  • By performing the shift operation, we shift ↑ one token to the right.
2023 Spring
CSE411

Shift operation

Input
□□□□□□□□
  ↓
|---------|    Stack
| Control | ⇔  |__|
|  Unit   |    |__|
|---------|    |__|
                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
  • Which part of the PDA will be affected by the shift operation?
2023 Spring
CSE411

Shift operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
        top of the stack
  • By performing the shift operation,
    • we shift ↑ one token to the right.
    • we push the token to the stack.
  • It can be viewed that ↑ points to the top of the stack.
2023 Spring
CSE411

Reduce Operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
  • We reduce int to T
  • We reduce int * T to T
  • We reduce T to E
  • We reduce T + E to E
2023 Spring
⠀

Reduce Operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
  • To perform the reduce operation
    1. Look up the stack to find a string that
      1. ends with the symbol at the top of the stack, and
      2. there exists a production whose right-hand side is .
    • E.g.,
⠀
CSE411

Reduce Operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
  • To perform the reduce operation
    1. Look up the stack to find a string that
      1. ends with the symbol at the top of the stack, and
      2. there exists a production whose right-hand side is .
    • is called a handle.
2023 Spring
CSE411

Reduce Operation

                                                                  E
                                                               /    | \
                        T                  T        E         T     |  E
                     /  |  \            /  |  \     |      /  |  \  |  |
       T             |  |  T            |  |  T     T      |  |  T  |  T
       |         ->  |  |  |        ->  |  |  |     |  ->  |  |  |  |  |
int * int + int     int * int + int    int * int + int    int * int + int
         ↑                   ↑                        ↑                  ↑
Stack Input Operation (Action)
int * int + int$ Shift
int * int + int$ Shift
int * int + int$ Shift
int * int + int$ Reduce
int * T + int$ Reduce
T + int$ Shift
T + int$ Shift
T + int $ Reduce
T + T $ Reduce
T + E $ Reduce
E $ Accept
2023 Spring
CSE411

Conflict

  • When to perform the shift/reduce operation?
  • How do we know that we should perform shift for the first int and reduce for the second int?
                                                                  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

Conflict

  • When both shift and reduce operations can be applied, we say that conflict occurs.
  • There can be two kinds of conflicts:
    1. Shift-reduce conflict
    • Both shift and reduce are applicable.
    1. Reduce-reduce conflict
    • Multiple productions can be used for reduce
2023 Spring
CSE411

Conflict

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