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