Give the derivation tree for ((a+b)∗c+d, using the grammar in Example 5.12.
EXAMPLE 5.12
To rewrite the grammar in Example 5.11 we introduce new variables, takingV as {E, T, F, I}, and replacing the productions with
E→T,T→F,F→I,E→E+T,T→T*F,F→(E),I→a|b|c.E→T,T→F,F→I,E→E+T,T→T*F,F→(E),I→a|b|c.
A derivation tree of the sentencea +b ∗c is shown in Figure 5.6. No other derivation tree is possible for this string: The grammar is unambiguous. It is also equivalent to the grammar in Example 5.11. It is not too hard to justify these claims in this specific instance, but, in general, the questions of whether a given context-free grammar is ambiguous or whether two given context-free grammars are equivalent are very difficult to answer. In fact, we will later show that there are no general algorithms by which these questions can always be resolved.