# 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

## 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
| ε
``````