edited by
7,222 views
24 votes
24 votes
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$
edited by

1 Answer

Best answer
23 votes
23 votes

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 

edited by

Related questions

17 votes
17 votes
2 answers
4
makhdoom ghaya asked Nov 23, 2016
4,294 views
State whether the following statements are TRUE or FALSE with reason:The Link-load-and-go loading scheme required less storage space than the link-and-go loading scheme.