CPSC 425 Spring 2008
Consider the grammar below:
Top Down Parsing Exercises
1. <S> := <A>$
2. <A> := b<A>c<B>
3. <A> := <C>a
4. <B> := b<B>
5. <B> := λ
6. <C> := ca
7. <C> := λ
Remember that a top down parse produces a left-most derivation, and that at
each step the parser has to decide what production to use to expand
the next non-terminal in the current sentential form in the derivation.
If the next symbol is a terminal, it must be matched by the next token
in the input string.
- Compute the First set for each right hand side.
- Compute the Follow set for each nonterminal.
- Compute the Predict set for each production.
- Use the grammar and the Predict sets to do a top-down parse for each
string below. If you encounter an error during the parse, indicate where,
what input symbol(s) you were expecting, and what symbol you got instead.