CPSC 425 Spring 2008
Top Down Parsing Exercises

Consider the grammar below: 
1. <S> := <A>$
2. <A> := b<A>c<B> 
3. <A> := <C>a
4. <B> := b<B>
5. <B> := λ
6. <C> := ca 
7. <C> := λ
  1. Compute the First set for each right hand side.
  2. Compute the Follow set for each nonterminal.
  3. Compute the Predict set for each production.
  4. 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.
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.