COMS W4115
Programming Languages and Translators
Lecture 8: Predictive Top-Down Parsers
February 16, 2015

Lecture Outline

  1. Top-down parsing
  2. FIRST
  3. FOLLOW
  4. How to construct a predictive parsing table
  5. LL(1) grammars
  6. Transformations on grammars

1. Top-Down Parsing

2. FIRST

3. FOLLOW

4. How to Construct a Predictive Parsing Table

5. LL(1) Grammars

6. Transformations on Grammars

7. Practice Problems

    Consider the following grammar G for Boolean expressions:
  1. What precedence and associativity does this grammar give to the operators and, or, not?
  2. Compute FIRST and FOLLOW for each nonterminal in G.
  3. Transform G into an equivalent LL(1) grammar G'.
  4. Construct a predictive parsing table for G'.
  5. Show how your predictive parser processes the input string
  6. Draw the parse tree traced out by your parser.

8. Reading



aho@cs.columbia.edu