CSE411: Introduction to Compilers

Parsing #2 (Derivation)

Jooyong Yi (UNIST)

Simplified Interface of Parser

                     |--------|           
a stream of tokens → | Parser | → ok / error
                     |--------|         

Synthesizing a Parser

          *Restricted* CFG
                   ↓
            |-------------|    
            |    Parser   |        
            | Synthesizer |
            |-------------|
                   |
              synthesizes   
                   ↓
              |--------|            
    program → | Parser | → ok / error
              |--------|                          

Today's Questions

• If CFG --> NPDA --> DPDA does not work, how to automatically synthesize a parser?
• How is the grammar restricted?

Why Not Using NPDA?

Why Not Using NPDA?

• We want a deterministic parser.

Deterministic Parsing

// Grammar G
E : T '+' E | T ;
T : int | int '*' T | '(' E ')' ;

• int '+' int ?
  • E T '+' E int '+' E int '+' T
int '+' int

Deterministic Parsing

// Grammar G
E : T '+' E | T ;
T : int | int '*' T | '(' E ')' ;

• int '+' int ?
  • E T '+' E int '+' E int '+' T
int '+' int
• int '*' '(' int '+' int ')' ?
  • E T int '*' T int '*' '(' E ')'
int '*' '(' T '+' E ')' int '*' '(' int '+' E ')'
int '*' '(' int '+' T ')' int '*' '(' int '+' int ')'

Leftmost Derivation

The leftmost nonterminal is replaced.

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

Not All Grammar Supports Leftmost Derivation

// Grammar G1
E : T '+' E | T ;
T : int | int '*' T | '(' E ')' ;

// Grammar G2
E : E '+' E | E '*' T | '(' E ')' | int;

• int '+' int ?

Not All Grammar Supports Leftmost Derivation

// Grammar G1
E : T '+' E | T ;
T : int | int '*' T | '(' E ')' ;

// Grammar G2
E : E '+' E | E '*' T | '(' E ')' | int;

• int '+' int ?
  • E E '+' E E '+' E '+' E

Not All Grammar Supports Leftmost Derivation

// Grammar G2
E : E '+' E | E '*' T | '(' E ')' | int;

• int '+' int ?
  • E E '+' E E '+' E '+' E
  • Assumption: our parser chooses a production to use deterministically without reading a whole program.
  • Lexer and parser maintain a producer-and-consumer relationship.
    • Lexer: producer
    • Parser: consumer

Left-Recursive Grammar

// Grammar G2
E : E '+' E | E '*' T | '(' E ')' | int;

• G2 is a left-recursive grammar.
• 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

// Grammar G2
E : E '+' E | E '*' T | '(' E ')' | int;

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

Indirect Left-Recursion

// Grammar G3
E : T '+' T ;
T : E | int ;

Indirect Left-Recursion

// Grammar G3
E : T '+' T ;
T : E | int ;

• G3 is indirectly left-recursive.
• E T '+' T E '+' T

Elimination of Immediate Left Recursion

Consider the following left-recursive grammar :

• is a nonterminal (i.e., ).
• • : a set of nonterminals.
  • : a set of terminals

includes the following:

Elimination of Immediate Left Recursion

includes the following:

The above strings can be expressed with the following grammar :

Elimination of Immediate Left Recursion

-- transform -->

Elimination of Indirect Left Recursion

Elimination of Indirect Left Recursion

-- transform -->

• Eliminate immediate left recursion.

Caveat

-- transform (eliminate indirect left recursion) -->

-- transform (eliminate immediate left recursion) -->

Caveat

-- transform (eliminate indirect left recursion) -->

-- transform (eliminate immediate left recursion) -->

• The left recursion elimination algorithm requires a non-cyclic grammar.
  • i.e., there should not exist for nonterminal .