Ambiguity

We say that a grammar $G$ is ambiguous if there is a word $w\in L(G)$ for which there is more than one parse tree. This is usually a bad thing because it entails that there is more than one way to interpret a word (i.e. it leads to semantical ambiguity).

As an example consider the following alternative grammar for arithmetical expressions: We define $G'=(\{E\},\{(,),a,+,*\},E,P')$ where $P'$ is given by:

$$P' = \{ E \to E + E \mid E * E \mid a \mid ( E ) \}$$

This grammar is shorter and requires only one variable instead of 4. Moreover it generates the same language, i.e. we have $L(G)=L(G')$. But it is ambigous: Consider $a+a*a$ we have the following parse trees:

        

Each parse tree correspond to a different way to read the expression, i.e. the first one corresponds to $(a+a)*a$ and the second one to $a+(a*a)$. Depending on which one is chosen an expression like $2+2*3$ may evaluate to $12$ or to $8$. Informally, we agree that $*$ binds more than $+$ and hence the 2nd reading is the intended one.

This is actually achieved by the first grammar which only allows the 2nd reading: