1.Using the following grammar, show a parse tree and a leftmost derivation for the following sentence (make sure you do not omit parentheses in your derivation. Parentheses, because they are terminal symbols, should have edges in your parse tree as well.):

Grammar = A | B | C + | * | () |

Derive

C = (A * (B + C) * C)

2. Consider the following grammar (S is the start symbol; 0 and 1 are terminal symbols; A and B are non-terminals)

S 0A | 1B A 1B | 1 B 0A | 0

Explain, in your own words, what the grammar generates? Which of the following sentences are in the language generated by the grammar? Show derivations. If a sentence cannot be generated by the grammar, explain why.

1. 0001110
2. 1010101
3. 1100011
4. 0101010

3.For the following grammar and the right sentential form E + (T * F + id * id) draw a parse tree and show all phrases, simple phrases, and the handle (E, T, and F are nonterminal symbols; E is the start symbol). E E + T | T T T * F | F F (E) | id

4. Transform the following left recursive BNF grammar into an equivalent non-left recursive grammar (S and A are nonterminal symbols; S is the start symbol; a and b are terminal symbols): S aSb | bAS A AbA | bAA | Aa | aAb