CSE411: Introduction to Compilers

Parsing Algorithm 1

Jooyong Yi (UNIST)

Parsing

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

Potential yet Infeasible Approach

CFG NPDA DPDA

• Another issue
  • We are not only interested in determining whether a program is syntactically valid.
  • We also want to construct a parse tree for the program.

Our Goal

              CFG for the programming language                           
                           ↓
                       |--------|            
a sequence of tokens → | Parser | → parse tree if the sequence is syntactically valid
                       |--------|                          

Context-Free Grammar (CFG)

• CFG
  • : a finite set of non-terminals
  • : a finite set of terminal symbols
  • : a start non-terminal
  • : a finite set of productions
    • Each production has the form
      • where and

E : E '+' E | INT

Example of Our Goal

• CFG: E : E '+' E | INT
• Input: INT '+' INT
• Output:

      E
     /|\                       
    E + E
    |   |
  INT   INT

Straightforward Approach

• CFG: E : E '+' E | INT
• Input: INT '+' INT
• Output:

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

Straightforward Approach

• CFG: E : E '+' E | INT
• Input: INT '+' INT
• Output:

E →     E   →      E    →      E
       /|\        /|\         /|\
      E + E      E + E       E + E
                 |           |   |
               INT         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

Turning Leftmost Derivation into a Parse Algorithm

• CFG: E : E '+' E | INT
• Input: INT '+' INT
• Output:

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

• CFG

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

• Recursive Descent Parsing Algorithm

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

fun S() = case !tok (* read the current token *)
          of BEGIN => (eat(BEGIN); S(); L())
           | IF => (eat(IF); E(); eat(THEN); S(); eat(ELSE); S())
           | PRINT => (eat(PRINT); E())
           | _ => error() (* _: matches any remaining token *)
and L() = case !tok
          of END => eat(END)
           | SEMI => (eat(SEMI); S(); L())
           | _ => error()
and E() = (eat(NUM); eat(EQ); eat(NUM))                     

• CFG: E : E '+' E | INT
• Input: INT '+' INT

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

• Does it work?

• CFG: E : E '+' E | INT
• Input: INT '+' INT

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

• Does it work?
  • '+' INT is left unparsed

• CFG: E : E '+' E | INT
• Input: INT '+' INT

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

Left-Recursive Grammar

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 .

Elimination of Immediate Left Recursion

• Consider the above 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 by Grammar Transformation

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

• Which new grammar can accept the same language as but is not left-recursive?

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

• Which new grammar can accept the same language as but is not left-recursive?

Elimination of Immediate Left Recursion by Grammar Transformation

E : E '+' E | INT

E : E '+' E | INT

E : INT E'
E' : '+' E E' | ε

E : INT E'
E' : '+' E E' | ε

fun E() = case !tok
          of INT => (eat(INT); E'())
and E'() = case !tok
          of '+' => (eat('+'); E(); E'())
           | EOF => () (* apply the rule E' -> ε *)
           | _ => error()

Indirect Left-Recursion

E : T '+' T
T : E | INT

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

Elimination of Indirect Left Recursion

• Consider the above left-recursive grammar :
  • and are nonterminals (i.e., ).
  • and do not start with .
  • and do not start with .

• Elimination of immediate left recursion

• at hand

• Target

• Elimination of immediate left recursion

• at hand

• Target

Elimination of Indirect Left Recursion

E : T '+' T
T : E | INT

A1 ⟼ E
A2 ⟼ T
ɑ ⟼ '+' T
β is absent
ɣ ⟼ ε
δ ⟼ INT

E : T '+' T
T : E | INT

E : T '+' T
T : INT T'
T' : '+' T T' | ε

Takeaway: A grammar that is difficult to parse (e.g. left recursive grammar) can be transformed into an equivalent grammar that is easier to parse.

Ambiguous Grammar

E: E + E | E * E | INT

• The parse tree of INT + INT * INT?

Ambiguous Grammar

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 | INT
==> ...

Disambiguating Ambiguous Grammar

        (Undesired)                 (Desired)

              E                        E
            / | \                    / | \
           E  *  E                  E  +  E
          /|\   |                   |    /|\
         E + E  INT                INT  E * E
         |   |                          |   |
        INT  INT                       INT  INT

• How can we derive the desired parse tree without allowing the undesired one?

Disambiguating Ambiguous Grammar

        (Undesired)                 (Desired)          (Refactored)

              E                        E                    E
            / | \                    / | \                / | \
           E  *  E                  E  +  E              E  +  E
          /|\   |                   |    /|\             |     |
         E + E  INT                INT  E * E            T     T     
         |   |                          |   |            |    /|\
        INT  INT                       INT  INT        INT   T * T
                                                             |   |
                                                            INT INT

Disambiguating Ambiguous Grammar

E: E + E | E * E | INT
==>
E: E + E | T
T: T * T | INT

        (Undesired)                 (Desired)          (Refactored)

              E                        E                    E
            / | \                    / | \                / | \
           E  *  E                  E  +  E              E  +  E
          /|\   |                   |    /|\             |     |
         E + E  INT                INT  E * E            T     T     
         |   |                          |   |            |    /|\
        INT  INT                       INT  INT        INT   T * T
                                                             |   |
                                                            INT INT

Ambiguous Grammar

E: E + E | T 
T: T * T | INT | ( E )

• The parse tree of INT + INT + INT?

Ambiguous Grammar

E: E + E | T 
T: T * T | INT | ( E )

• The parse tree of INT + INT + INT?

   (Left-associative)            (Right-associative)

           E                             E
       /   |  \                       /  |  \
      E    +   E        OR           E   +   E 
   /  |  \     |                     |     / | \
  E   +   E    T                     T    E  +  E
  |       |    |                     |    |     |
  T       T   INT                  INT    T     T
  |       |                               |     |
 INT     INT                             INT   INT

Ambiguous Grammar

E: E + E | T             ==> ...
T: T * T | INT | ( E )

• Refactor the tree to allow only left-associativity.

   (Left-associative)            (Right-associative)        (Refactored)

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

Ambiguous Grammar

E: E + E | T             ==> ...
T: T * T | INT | ( E )

• Refactor the tree to allow only left-associativity.

   (Left-associative)            (Right-associative)        (Refactored)

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

Ambiguous Grammar

E: E + E | T             ==> E: E + T | T
T: T * T | INT | ( E )       T: T * T | INT | ( E )

• Refactor the tree to allow only left-associativity.

   (Left-associative)            (Right-associative)        (Refactored)

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

Ambiguous Grammar

E: E + T | T 
T: T * T | INT | ( E )

• The parse tree of INT * INT * INT?

   (Left-associative)            (Right-associative)

           E                             E
           |                             |
           T                             T
        /  |  \                       /  |  \
      T    *   T                     T   *   T 
   /  |  \     |                     |     / | \
  T   *   T   INT                   INT   T  *  T
  |       |                               |     |
 INT     INT                             INT   INT                                         

Ambiguous Grammar

E: E + T | T             ==>  E: E + T | T
T: T * T | INT | ( E )        T: T * F | F
                              F: INT | ( E )

• The parse tree of INT * INT * INT?

   (Left-associative)            (Right-associative)            (Refactored)

           E                             E                             E
           |                             |                             |
           T                             T                             T
        /  |  \                       /  |  \                       /  |  \
      T    *   T                     T   *   T                     T   *   F
   /  |  \     |                     |     / | \                /  |  \    |
  T   *   T   INT                   INT   T  *  T              T   *   F  INT
  |       |                               |     |              |       |
 INT     INT                             INT   INT             F      INT
                                                               |
                                                              INT

Unambiguous and Non-Left-Recursive Grammar

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

E: T E'
E': + T E' | ε
T: F T'
T': * F T' | ε
F: INT | ( E )                                                                                

fun E() =
    (T(); Eprime())

and Eprime() =
    case !tok
      of PLUS => (eat(PLUS); T(); Eprime())
       | _ => ()       (* epsilon *)

and T() =
    (F(); Tprime())

and Tprime() =
    case !tok
      of TIMES => (eat(TIMES); F(); Tprime())
       | _ => ()       (* epsilon *)

and F() =
    case !tok
      of INT => eat(INT)
       | LPAREN => (eat(LPAREN); E(); eat(RPAREN))                                                  
       | _ => error()

Another Example

S: if E then S else S
 | if E then S

Another Example

S: if E then S else S
 | if E then S

fun S() =
    case !tok
      of IF => ...

Another Example

S: if E then S else S  ==> ...
 | if E then S

Another Example

S: if E then S else S  ==> S:  if E then S S'
 | if E then S             S': else S | ε

fun S() =
    case !tok
      of IF => (eat(IF); E(); S(); Sprime())
      | _ => error()    
and Sprime() =
    case !tok
      of ELSE => (eat(ELSE); S())
       | _ => ()       (* epsilon *)

• This transformation is called left factoring.

Left Factoring

• and are nonterminals (i.e., ).

Another Example

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

Another Example

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

fun E() = (T(); X())
and X() = case !tok
    of PLUS => (eat(PLUS); eat(INT); Eprime())
     | _ => (Eprime())
and Eprime() =
    case !tok
      of PLUS => (eat(PLUS); T(); Eprime())
       | _ => ()       (* epsilon *)
and T() =
    case !tok
      of INT => (eat(INT); Tprime())
       | LPAREN => (eat(LPAREN); E(); eat(RPAREN); Tprime())
       | _ => error()
and Tprime() =
    case !tok
      of TIMES => (eat(TIMES); T(); Tprime())
       | _ => ()       (* epsilon *)                                                                                    

• Consider input INT + ( INT )

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

fun E() = (T(); X())
and X() = case !tok
    of PLUS => (eat(PLUS); eat(INT); Eprime())
     | _ => (Eprime())
and Eprime() =
    case !tok
      of PLUS => (eat(PLUS); T(); Eprime())
       | _ => ()       (* epsilon *)
and T() =
    case !tok
      of INT => (eat(INT); Tprime())
       | LPAREN => (eat(LPAREN); E(); eat(RPAREN); Tprime())
       | _ => error()
and Tprime() =
    case !tok
      of TIMES => (eat(TIMES); T(); Tprime())
       | _ => ()       (* epsilon *)                                                                                    

• Consider input INT + ( INT )

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

E => T X => T E' => INT T' E' => INT E' => INT + T E' 
  => INT + ( E ) T' E' => INT + ( T X ) T' E' 
  => INT + ( INT T' ) T' E' => INT + ( INT ) T' E' 
  => INT + ( INT ) E' => INT + ( INT )                                                              

• Consider input INT + ( INT )

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

E => T X => T E' => INT T' E' => INT E' => INT + T E' => INT + ( E ) T' E' 
  => INT + ( T X ) T' E' => INT + ( INT T' ) T' E' => INT + ( INT ) T' E' => INT + ( INT ) E' => INT + ( INT ) 

fun E() = (T(); X())
and X() = case !tok
    of PLUS => (eat(PLUS); eat(INT); Eprime())
     | _ => (Eprime())
and Eprime() =
    case !tok
      of PLUS => (eat(PLUS); T(); Eprime())
       | _ => ()       (* epsilon *)
and T() =
    case !tok
      of INT => (eat(INT); Tprime())
       | LPAREN => (eat(LPAREN); E(); eat(RPAREN); Tprime())
       | _ => error()
and Tprime() =
    case !tok
      of TIMES => (eat(TIMES); T(); Tprime())
       | _ => ()       (* epsilon *)