# MC97 HW 1: Parsing (Spring 1999)

## Due: March 3, 1999

- Do exercise 3.4, p. 85.
- Do exercise 3.12, p. 87.
- 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:
- A left-recursive grammar:
S -> L $
L -> a
L -> L a

- 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