1. Problem 4: Using the grammar in Example 3.4, show a parse tree and a leftmost derivation for each of the following statements.
(a) A := (A+B)*C
|
|
(b) A := B+C+A
 |
 |
(c) A := A* (B+C)
 |
 |
(d) A := B * (C * (A + B))
 |
 |
2 . Problem 5 : Prove that the following grammar is ambiguous.
A grammar is ambiguous if it generates two or more parse trees (or more
than one leftmost/rightmost derivation) for the same sentence. We can prove
the ambiguity of the grammar by deriving two parse trees for the sentence
a+b+c.
 |
 |
3 . Problem 8: Consider the following grammar:
<S> -> <A> a <B> b
<A> -> <A> b | b
<B> -> a <B> | a
The sentences in (a) and (d) are elements of the language generated by this grammar. The leftmost derivations for these sentences are as follows:
(a)
<S> => <A> a <B> b
<S> => b a <B> b
<S> => b a a b
(d)
<S> => <A> a <B> b
<S> => <A> b a <B> b
<S> => b b a <B> b
<S> => b b a a b
Last modified: Mon Sep 13 17:30:44 1999