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, taking V 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 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.
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, taking V 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 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
Trending now
This is a popular solution!
Step by step
Solved in 8 steps with 6 images
