Dark Mode

5,784 views

22 votes

Best answer

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

0

1