Compiler HWK#2 Due date: 2:20pm, April 12, 2007

1. Consider the following contest-free grammar:
      S -> S + S
      S -> * S S
      S -> a | epsilon
and the input string *a+a++a

(a) Give a leftmost derivation for the string.
(b) Give a rightmost derivation for the string
(c) Give a parse tree for the string.
(d) Is the grammar ambiguous or not?
    Explain your answers.

NOTE: epsilon is the empty string.


2. Given a grammar G,
a symbol X is useless if and only if at least one
of the following conditions is true
(1) a sequence of symbols including X cannot be derived from the starting
nonterminal
(2) X cannot derive a sequence of terminals or epsilon

(a) Show an example of a grammar with at least one useless terminal and
one useless nonterminal.
(b) Give a polynomial-time
algorithm to transform a grammar with useless symbols
into an equivalent grammar without any useless symbols.
(c) Prove the correctness of your algorithm.
(d) Show the time and space complexities of your algorithm.

3. Eliminate left recursions from the following grammar to get
an equivalent grammar.
Be sure to show all intermediate steps in deriving your answer.

   A -> A c d | A d d | e r | B B
   B -> A x y | D r t | k
   C -> B d p 
   D -> C e w