5,784 views
Show that grammar $G_1$ is ambiguous using parse trees:

$G_{1}: S \rightarrow$ if $S$ then $S$ else $S$

$S \rightarrow$ if $S$ then $S$

but how to minimize s? no epsilon ?
the inherently ambiguous problem for a language not grammer

The given grammar is well known as "Dangling Else" problem.  The given grammar is ambiguous and ambiguity can be resolved.

$\textbf{stmt} \to$ $\textbf{if} \$expr$\ \textbf{then}$ stmt
$\mid$ $\textbf{if}$ expr $\textbf{ then }$ stmt$\textbf{ else}$ stmt
$\mid \textbf{other}$

Consider the compound conditional statement for the above grammar

if $E_1$ then $S_1$ else if $E_2$ then $S_2$ else $S_3$ has the following parse tree

Well this is ambiguous due to the statement
if $E_1$ then if $E_2$ then $S_1$ else $S_2$

The two parse trees are

Ambiguity can be resolved by parsers  as follows

In all programming languages with conditional statements of this form, the first parse tree is preferred.
The general rule is, "Match each else with the  closest unmatched then"

In practice it is rarely built into the productions .

$\textbf{stmt} \to$ $\textbf{matched_stmt}$
$\mid$ $\textbf{open_stmt}$
$\textbf{matched_stmt} \to$ $\textbf{if }$expr$\textbf{ then }$ matched_stmt $\textbf{ else}$ matched_stmt
$\mid$ $\textbf{other}$
$\textbf{open_stmt} \to$ $\textbf{if }$expr$\textbf{ then }$ stmt
$\mid$ $\textbf{if }$ expr $\textbf{ then }$ matched_stmt$\textbf{ else}$ open_stmt

However this grammar is also ambiguous

Consider the following exercise question from Dragon book.

$\textbf{Exercise 4.3.3:}$ The following grammar is proposed to remove the “dangling-else ambiguity”:

• $stmt \to \textbf{if}\; expr\;\textbf{then}\;stmt$
$\qquad \quad \mid matchedStmt$
• $matchedStmt \to \textbf{if}\;expr\;\textbf{then}\;matchedStmt\;\textbf{else}\;stmt$
$\qquad \qquad \qquad \quad \mid \textbf{ other}$

Show that this grammar is still ambiguous.

Solution is given here. But we can make an equivalent unambiguous grammar for the dangling-else problem and that makes the language not inherently ambiguous.

Try running this code in any compilers . No doubt that all compilers will successfully parse and produce output

#include <stdio.h>

int main(void) {
if(1<3)
if(1<2)
printf("1 is the smallest");
else
printf("2 is the smallest");
return 0;
}

Thus we can say that ambiguity in Dangling Else Problem can be resolved and we can have an unambiguous grammar for it (making the language $\textbf{NOT}$ inherently ambiguous. But many of the grammars given for Dangling Else problem is ambiguous.

Source

by

Sir, can you make it more clear why the dangling else problem is not inherently ambiguous? (unless the language gets modified I am not able to generate any ambiguous grammar)
this grammar matches each else with the nearest if and is unambiguous.

Hence this language is not inherently ambiguous

1 vote