3. Consider the following context-free grammar in BNF, where and are non-terminals and +, -, and id are terminals. ::= + (r1)

::= - (r2)

::= (r3)

::= id (r4)

a. (5 points) Construct parsing steps for the string id + id - id in the grammar and state whether or not the string is a sentence in the language. Solution:

b. (5 points) Draw a parse tree from (a) Solution:

c. (5 points) Prove that the grammar is ambiguous Solution

d. (5 points) Disambiguating the grammar. Solution: