1. (25 points) 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):

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

Derive

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

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

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

In plain English what does the grammar generate? 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. 01010100
2. 01010101
3. 10101010
4. 10010011

3. (25 Points) For the following grammar and the right sentential form F * (id + id) draw a parse tree and show all phrases, simple phrases, and the handle (E, T, and F are nonterminal symbols; id is a terminal symbol). Explain. E E + T | T T T * F | F F (E) | id
4. (25 Points) 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 AaA | bAA | AAa | bAb

CAUTION: Make sure ALL left recursion is eliminated.