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
Good Read
