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