Programming Language Principles

Homework for Week 02.

1. Consider the following context-free grammar:

               S -> S B
                 -> k
               B -> B x
                 -> A x
               A -> v
                 -> v S k

   a) Show that the grammar is not LL(1).

   b) Modify the grammar so that it becomes LL(1).

   c) Construct the corresponding LL(1) parse table.

   d) Hand-simulate the execution of the classical top-down parsing
      algorithm, using your parse table, for the input string
      "kvxvkkxx<eof>".  For each step, show the stack, the input,
      and the result of OPF.  Then take the sequence of productions
      produced by OPF and use them to derive the input string.

   e) Write the skeleton of the corresponding recursive descent parser.

   f) Add output statements to the code of part e) so that the parser
      generates (in reverse order) the sequence of productions from the
      original grammar (not the modified grammar) that can be used to
      derive the input parsed.