MC97 HW 1: Parsing (Spring 1999)

Due: March 3, 1999

  1. Do exercise 3.4, p. 85.
  2. Do exercise 3.12, p. 87.
  3. We saw that left-recursive grammars can't be LL(1). By contrast, both left and right recursion are possible with LR parsing. Consider the following two grammars:
    1. A left-recursive grammar:
      S -> L $
      L -> a
      L -> L a
    2. A right-recursive grammar:
      S -> R $
      R -> a
      R -> a R
    Suppose the input consists of n repetitions of the terminal a, followed by the $ marker. What is the maximum stack depth an LR(1) parser will reach on this input, if the parser is based on the left-recursive grammar? The right-recursive one? Justify your answers.

Instructor: Max Hailperin