CSE411: Introduction to Compilers

Parsing Algorithms

Jooyong Yi (UNIST)

Parsing

        <id, 1> <=> <id, 2> <+> <id, 3> <*> <int, 60>
                           ↓
        |------------------------------------|
        |      Syntax Analyzer (Parser)      |
        |------------------------------------|
                           ↓
                       =
                      / \
                <id,1>   +
                        / \
                   <id,2>  *
                          / \
                    <id,3>   <int,60>                   

Synthesizing a Parser

        Specification for the parser written in CFG
                           ↓
                    |-------------|    
                    |    Parser   |        
                    | Synthesizer |
                    |-------------|
                           |
                      synthesizes   
                           ↓
                       |--------|            
a sequence of tokens → | Parser | → parse tree
                       |--------|                          

Potential Approach

CFG NPDA DPDA

Potential Approach

CFG NPDA DPDA

• NPDA DPDA

Potential Approach

CFG NPDA DPDA

• NPDA DPDA
• Why not use NPDA?

Our Focus

        Specification for the parser written in CFG
                           ↓
                    |-------------|    
            Focus:  |    Parser   |        
                    | Synthesizer |
                    |-------------|
                           |
                      synthesizes   
                           ↓
                       |--------|            
a sequence of tokens → | Parser | → parse tree
                       |--------|                          

Q: How can we turn a CFG into a parse tree?

Context-Free Grammar (CFG)

• CFG
  • : a finite set of non-terminals (e.g., exp).
  • : a finite set of terminals (e.g., '(', ')', PLUS)
  • : a start non-terminal (e.g., start)
  • : a finite set of productions.
    • Each production has the form
      • where and

start : exp EOF
exp: INT | ID | exp PLUS exp | '(' exp ')'

Parse Tree

• Root: a start non-terminal
• Leaf: a terminal or
• Internal node: a non-terminal
• Edge: defined by a production rule

A -> X Y Z
 
        A
       /|\                       
      X Y Z

Example

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

• What is the parse tree for int '+' int?

Deterministic Parsing Algorithm?

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

input: int '+' int

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

Derivation

• Assume CFG where
• Suppose you have a string where
• Then, derives and we write

Leftmost Derivation

• Assume CFG where
• Suppose you have a string where
• Then, derives and we write

Rightmost Derivation

The rightmost nonterminal is replaced.

• Assume CFG where
• Suppose you have a string where
• Then, derives and we write

Applying Leftmost Derivation

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

input: int '+' int

Applying Leftmost Derivation

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

input: int '+' int

E  -lm->  E '+' E  -lm->  int '+' E  -lm->  int '+' int

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

Applying Rightmost Derivation

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

input: int '+' int

E  -rm->  E '+' E  -rm->  E '+' int  -rm->  int '+' int

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

Frontend Architecture Options

          |--------|                          |--------|
input  →  | Lexer  |  → sequence of tokens →  | Parser | → parse tree
          |--------|                          |--------|

Frontend Architecture Options

          |--------|                     |--------|
input  →  | Lexer  |  → current token →  | Parser |
          |--------|                     |--------|
            ↑                                 ↓
            |                           intermediate
            ← request the next token  ←  incomplete
                                         parse tree

Which One to Use?

          |--------|                          |--------|
input  →  | Lexer  |  → sequence of tokens →  | Parser | → parse tree
          |--------|                          |--------|

          |--------|                     |--------|
input  →  | Lexer  |  → current token →  | Parser |
          |--------|                     |--------|
            ↑                                 ↓
            |                           intermediate
            ← request the next token  ←  incomplete
                                         parse tree

Applying Leftmost Derivation (Revisited)

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

input: int '+' int
        ↑

E →     E  
       /|\ 
      E + E

Applying Leftmost Derivation (Revisited)

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

input: int '+' int
                ↑

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

Applying Leftmost Derivation (Revisited)

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

input: int '+' int
                   ↑

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

Applying Rightmost Derivation (Revisited)

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

input: int '+' int
        ↑

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

• We have not read the second int yet!

Applying Rightmost Derivation (Revisited)

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

input: int '+' int

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

Applying Rightmost Derivation (Revisited)

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

input: int '+' int

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

E  -rm->  E '+' E  -rm->  E '+' int  -rm->  int '+' int

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