to rewrite the grammar so that only one parsing is possible.
Example 5.12
To rewrite the grammar in Example 5.11 we introduce new variables, taking V as
{E, T, F, I}, and replacing the productions with
A derivation tree of the sentence a + 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.
Figure 5.6
Example 5.12
To rewrite the grammar in Example 5.11 we introduce new variables, taking V as
{E, T, F, I}, and replacing the productions with
A derivation tree of the sentence a + 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.
Figure 5.6