Elimination of ambiguity.

Example 8 Let us consider $\Sigma$ = {a, b, c} and

L = {w $\displaystyle \in$ $\displaystyle \Sigma^{{{\ast}}}_{{}}$ | ( | w $\displaystyle \mid_{{a}}^{{}}$ = | w $\displaystyle \mid_{{b}}^{{}}$ ) or ( | w $\displaystyle \mid_{{b}}^{{}}$ = | w $\displaystyle \mid_{{c}}^{{}}$ )}.

(17)

One can show that L is an inherently ambiguous language.

Example 9 Consider V_N = {S, E}, V_T = { $\bf if$ , $\bf then$ , $\bf else$ } and a grammar G = (V_T, V_N, S, P) such that the following

$\displaystyle \longmapsto$

$\displaystyle \bf if$ E $\displaystyle \bf then$ S | $\displaystyle \bf if$ E $\displaystyle \bf then$ S $\displaystyle \bf else$ S

(18)

are productions of G. Then the string

w = $\displaystyle \bf if$ E $\displaystyle \bf then$ $\displaystyle \bf if$ E $\displaystyle \bf then$ S $\displaystyle \bf else$ S

(19)

has two parse trees as shown on Figure 5.

**Figure 5:** Two parse trees for the same if-then-else statement.
$\begin{figure}\htmlimage \centering\includegraphics[scale=.4]{ifThenElseParseTrees.eps} \end{figure}$

In all programming languages with if-then-else statements of this form, the second parse tree is preferred. Hence the general rule is: match each else with the previous closest then. This disambiguating rule can be incorporated directly into a grammar by using the following observations.

A statement appearing between a then and a else must be matched. (Otherwise there will be an ambiguity.)
Thus statements must split into kinds: matched and unmatched.
A matched statement is
- either an if-then-else statement containing no unmatched statements
- or any statement which is not an if-then-else statement and not an if-then statement.
Then an unmatched statement is
- an if-then statement (with no else-part)
- an if-then-else statement where unmatched statements are allowed in the else-part (but not in the then-part).

stmt	$\longmapsto$	matched-stmt \| unmatched-stmt
matched-stmt	$\longmapsto$	if expr then* matched-stmt else matched-stmt*
matched-stmt	$\longmapsto$	non-alternative-stmt
unmatched-stmt	$\longmapsto$	if expr then* stmt*
unmatched-stmt	$\longmapsto$	if expr then* matched-stmt else unmatched-stmt*