CSE411: Introduction to Compilers

Recursive Decent Parsing

Jooyong Yi (UNIST)

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

Recursive Descent Parsing

// Grammar G
S : begin S L | if E then S else S | print E
L : end | ; S L
E : num = num

val tok = ref (getToken())
fun advance() = tok := getToken()
fun eat(t) = if t = !tok then tok := advance() else error()

fun S() = case !tok
          of BEGIN => (eat(BEGIN); S(); L())
           | IF => (eat(IF); E(); eat(THEN); S(); eat(ELSE); S())
           | PRINT => (eat(PRINT); E())
and L() = case !tok
          of END => eat(END)
           | SEMI => (eat(SEMI); S(); L())
and E() = (eat(NUM); eat(EQ); eat(NUM))                     

Recursive Descent Parsing

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

fun E() = case !tok
          of int => eat(INT)
           |   ? => (E(); eat(PLUS); E())           

• Does it work? Consider 1 + 2.

Recursive Descent Parsing

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

fun E() = case !tok
          of ? => (E(); eat(PLUS); E())           
           | int => eat(INT)  

• How about this? Again, you can consider 1 + 2.

Left-Recursive Grammar

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

• A grammar is left-recursive if it has a nonterminal such that there is a derivation for some string .
  • represents applying one or more times.

Immediately Left-Recursive Grammar

E : E '+' E | int

• A grammar is immediately left-recursive if it has a nonterminal such that there is a derivation for some string .

Indirect Left-Recursion

E : T '+' T ;
T : E | int ;

• E T '+' T E '+' T

Elimination of Immediate Left Recursion

Consider the following left-recursive grammar :

• is a nonterminal (i.e., ).
• and do not start with .

(i.e., the language of ) includes the following:

Elimination of Immediate Left Recursion

includes the following:

A non-left-recursive grammar that can express the above?

Elimination of Immediate Left Recursion

The above strings can be expressed with the following grammar :

Elimination of Immediate Left Recursion

Elimination of Immediate Left Recursion

• is a nonterminal (i.e., ).
• and do not start with .

Elimination of Immediate Left Recursion

• is a nonterminal (i.e., ).
• and do not start with .

Elimination of Indirect Left Recursion

Elimination of Indirect Left Recursion

• Eliminate immediate left recursion.

Ambiguous Grammar (Precedence)

E: E + E | E * E | (E) | int

• The parse tree of int + int * int?

              E                        E
            / | \                    / | \
           E  *  E       OR         E  +  E
          /|\   |                   |    /|\
         E + E  int                int  E * E
         |   |                          |   |
        int  int                       int  int

Disambiguating Ambiguous Grammar

E: E + E | E * E | (E) | int

==> ... 

              E                         
            / | \                     
           E  +  E       ==>         
           |    /|\                  
          int  E * E                 
               |   |                 
              int  int                                                    

Disambiguating Ambiguous Grammar

E: E + E | E * E | (E) | int

==> ... 

              E                         E
            / | \                     / | \
           E  +  E       ==>         E  +  E
           |    /|\                        |
          int  E * E                       T
               |   |                      /|\    
              int  int                   T * T
                                         |   |
                                         F   F
                                         |   |
                                        int int   

Disambiguating Ambiguous Grammar

E: E + E | E * E | (E) | int

==>

E: E + E | T
T: T * T | F
F: (E) | int

              E                         E
            / | \                     / | \
           E  +  E       ==>         E  +  E
           |    /|\                        |
          int  E * E                       T
               |   |                      /|\    
              int  int                   T * T
                                         |   |
                                         F   F
                                         |   |
                                        int int

Ambiguous Grammar (Associativity)

E: E + E | T
T: T * T | F
F: (E) | int

Consider: int + int + int

         E                             E
     /   |  \                       /  |  \
    E    +   E        OR           E   +   E 
 /  |  \     |                     |     / | \
E   +   E   int                   int   E  +  E
|       |                               |     |
int    int                             int    int

Disambiguating Ambiguous Grammar

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

           E                             
       /   |  \         
      E    +   E     ==> ...   
   /  |  \     |        
  E   +   E   int       
  |       |
 int     int

Disambiguating Ambiguous Grammar

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

           E                         E               
       /   |  \                  /   |  \
      E    +   E     ==>        E    +   T
   /  |  \     |             /  |  \     |
  E   +   E   int           E   +  T     F
  |       |                 |      |     |
 int     int                T      F     int
                            |      |
                            F     int
                            |
                           int

Disambiguating Ambiguous Grammar

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

           E                         E               
       /   |  \                  /   |  \
      E    +   E     ==>        E    +   T
   /  |  \     |             /  |  \     |
  E   +   E   int           E   +  T     F
  |       |                 |      |     |
 int     int                T      F     int
                            |      |
                            F     int
                            |
                           int

// Grammar
S: c A d
A: a b | a

• Consider cad