Reference no: EM131858791

Assignment

1.) Show each step of a leftmost derivation and parse tree for the following sentence. (Do not forget to include your parentheses in your derivation and parse tree).

A = A + (B + A) * C

2.) Consider the following grammar in which S, A, and B are nonterminal symbols and S is the start symbol.

S → 1A | 0B
A → A0| 1B
B → 10A| 1

Show that the grammar is ambiguous by showing two parse trees for the sentence 1110110 using leftmost derivation.

3) Consider the following grammar in which A, B, and S are nonterminal symbols, S is the starting symbol, a and b are terminal symbols.

S → A | SB
A → Aa | aa | Aab | aB | bb
B → aac | ac

a.) Show a rightmost derivation for aacab.
b.) Using the procedure explained on page 181 and transform the grammar into an equivalent non-left recursive grammar.
c.) Show a rightmost derivation for aacab, again, using the new rules created in step b.

4.) For the following grammar and the right sentential form T * (E + T * F) determine the handle. Demonstrate how you came up with your answer.

E → E + T | T
T → T * F | F
F → (E) | id