Ambiguity in Grammar

A Grammar is said to be ambiguous if its language contains some string with more than one -

• parse tree, or
• leftmost derivation or
• rightmost derivation or
• syntax tree or
• derivation tree.

If the grammar is not ambiguous, then it is called unambiguous. If the grammar has ambiguity, then it isn't useful for compiler construction. No method can automatically detect and eliminate the ambiguity, but we can remove ambiguity by re-composing the entire grammar without ambiguity.

Definition of Ambiguous Grammar

A Context Free Grammar G = (V,T,P,S) is said to be ambiguous if and only if there exists a string in T* that has more than on the parse tree, where
V is a finite set of variables,
T is a finite set of terminals,
P is a finite set of productions of the form, A -> α, where A is a variable and α ∈ (V ∪ T)*.
S is a start variable.

Example of Ambiguous Grammar

Suppose there is a string S that has the following grammar.

S = Z + Z X Z

These are the possible parse trees for this string S -

Since two parse trees exist for the string S, hence the grammar is ambiguous.

Here, we have evaluated the derivations for the same string S.

S = Z + Z X Z

Z -> Z+Z

Since, two derivations exist for the string S, hence the grammar is ambiguous.

Here, we have drawn the syntax trees of the same string S -

Since two syntax trees exist for the string S, hence the grammar is ambiguous.

In some cases, it is possible to modify the grammar to make it unambiguous. A grammar G is said to be unambiguous if every string has a unique leftmost deviation (or rightmost deviation), unique syntax tree and unique parse tree.