# Correct way to derive parse trees, for a given input, to show ambiguity

Is it correct to state that the below grammar can handle the expression: a - b * c, by the below two different parse trees.

Grammar:

Expression = Expression "-"
Expression | Expression "*"
Expression | Factor
Factor = "a" | "b" | "c"


Parse tree #1:

Expression -> Expression - Expression
=> Factor - Expression
=> a - Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c


Parse tree #2:

Expression -> Expression * Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c


I feel that the second derivation above is completely wrong, as not considers the left-to-right scan of the input string. The decision should have been based on the lookahead symbol only.

If possible show by a C language code snippet, how the implementation of the second derivation, is correct, as the book titled: Compliers and Compiler Generators An Introduction With C++, by Patrick D. Terry, shows the above example, in Section 6.4, page #131

For me, the ambiguous grammar can only be shown by the below second derivation:

Parse tree #2:

Expression -> Expression - Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Factor * Expression
=> a - b * Expression
=> a - b * Factor
=> a - b * c


## 1 Answer

You provided a grammar of the shape:

• $$E \rightarrow E - E$$
• $$E \rightarrow E * E$$
• $$E \rightarrow F$$
• $$F \rightarrow a | b | c$$

The second last production has $$E$$ on its LHS; it is a unit production that can be removed to produce the grammar:

• $$E \rightarrow E - E$$
• $$E \rightarrow E * E$$
• $$E \rightarrow a | b | c$$

This second grammar is ambiguous and this fact can be shown exhibiting two distinct derivation trees for the same string (they need to be both leftmost or rightmost though.) Since the removal of the production $$E\rightarrow F$$ preserves the language the initial grammar must be ambiguous as well.

Both derivations are correct since the grammar does nothing to prevent them to be generated: the fact you can show the existence of the derivation tree is sufficient to tell the string belongs to the language generated by the grammar.