COMS W4115
Programming Languages and Translators
Lecture 9: Top-Down Parsing
February 20, 2008

Lecture Outline

1. Review
2. Context-free grammars
3. Top-down parsing
4. Transformations on grammars
5. Reading and other

1. Review

• Role of the parser
• Context-free grammars
• Derivations and parse trees
• Ambiguity
• Yacc: a language for specifying translators

2. Context-Free Grammars

• Examples
• All strings of the form n a's followed by n b's:
CFG: S → aSb | ε
• All strings of balanced parentheses:
CFG: S → (S)S | ε
• All strings of a's and b's with the same number of a's as b's:
CFG: S → aSbS | bSaS | ε
Note that this grammar is ambiguous.
• If- and if-else statements:

      stmt → if ( expr ) stmt else stmt
           | if (expr) stmt
           | other
   

Note that this grammar is ambiguous.
• Arithmetic expressions:

      expr →   expr + term
           |   term
      term →   term * factor
           |   factor
      factor → ( expr )
           |   number
   

3. Top-down Parsing

• Top-down parsing consists of constructing a parse tree for an input string starting from the root and creating the nodes of the parse tree in preorder.
• Equivalently, top-down parsing consists of finding a leftmost derivation for the input string.
• Consider grammar G:

      S → ( S ) S | ε
    

• Leftmost derivation for (()()):

      S ⇒ ( S ) S

        ⇒ ( ( S ) S ) S

        ⇒ ( ( ) S ) S

        ⇒ ( ( ) ( S ) S ) S

        ⇒ ( ( ) (  ) S ) S

        ⇒ ( ( ) (  ) ) S

        ⇒ ( ( ) (  ) )
  

• Recursive-descent parsing
• Recursive-descent parsing is a top-down method of syntax analysis in which a set of recursive procedures is used to process the input string.
• One procedure is associated with each nonterminal of the grammar. See Fig. 4.13, p. 219.
• The sequence of successful procedure calls defines the parse tree.
• Nonrecursive predictive parsing
• A nonrecursive predictive parser uses an explicit stack.
• See Fig. 4.19, p. 227, for a model of table-driven predictive parser.
• Parsing table for G:

                        Input Symbol
   Nonterminal      (         )        $

       S        S → (S)S    S → ε    S → ε
   

• Moves made by predictive parser on input (()()).

       Stack       Input      Output
        $S         (()())$
        $S)S(      (()())$   S → (S)S
        $S)S        ()())$
        $S)S)S(     ()())$   S → (S)S
        $S)S)S       )())$
        $S)S)        )())$   S → ε
        $S)S          ())$
        $S)S)S(       ())$   S → (S)S
        $S)S)S         ))$
        $S)S)          ))$   S → ε
        $S)S            )$
        $S)             )$   S → ε
        $S               $
        $                $   S → ε        
   

4. Transformations on Grammars

• Two common language-preserving transformations are often applied to grammars to try to make them parsable by top-down methods. These are elimination of left recursion and left factoring.
• Eliminating left recursion:
• Replace

      expr →  expr + term
           |  term
   

by

      expr  →  term expr'

      expr' →  + term expr'
            |  ε
   

• Left factoring:
• Replace

      stmt → if ( expr ) stmt else stmt
           | if (expr) stmt
           | other
   

by

      stmt  → if ( expr ) stmt stmt'
            | other

      stmt' → else stmt
            | ε
   

5. Reading and Other

• Language whitepapers are due in class February 27, 2008.
• Try doing exercises 4.2.1, 4.2.2, 4.2.3, 4.3.1.
• Read ALSU, Sections 4.3, 4.4.