Class 8: Parsing: top-down, bottom-up

Slides

Display version (pdf).

Downloads

Homework

Reading: PLP, 2.3 intro and 2.3.1, pp. 67-75

Exercises:
  1. Why do we sometimes restrict the set of allowable languages for compilation? Give an example of a language construct that, though valid, might not be allowed, and explain why not. (Don't use examples discussed in class; come up with your own.)
  2. Top-down and bottom-up parsers require different language restrictions in order to work. Which type of parser do you think will be more flexible, i.e., allow a larger set of languages? Briefly explain your choice.
  3. The following grammar has a few problems. For starters, it's ambiguous. Without changing the underlying language it describes, modify the grammar so that it is both unambiguous and amenable to top-down (LL) parsing.
    Sexp
    expexp + exp
    expNUM