Chapter 4 Homework

Instructions

Given the following grammar, in which terminals are in all CAPITALS or are ‘quoted’ literals:

1. lexp          -> atom
2.                | list
3. atom          -> NUMBER
4.                | IDENTIFIER
5. list          -> '(' lexp-seq ')'
6. lexp-seq      -> lexp lexp-seq-tail
7. lexp-seq-tail -> lexp lexp-seq-tail
8.                |

1. (10 pts) Show the First and Follow sets for the nonterminals.

2. (13 pts) Show the the LL(1) parse table or Pushdown Machine Transition Table for the grammar.

3. (5 pts) Show that the grammar is LL(1).

4. (12 pts) Show the sequence of stacks and actions of a Pushdown Machine as it processes the following input string:

   (a (b (2)) (c))
   

   Write your answer following the format of the sample LL Parse given in the lecture notes.

Submission

You may turn in a neatly handwritten or word processed paper. See the syllabus for additional information about homework exercises.