in Compiler Design edited by
5,784 views
23 votes
23 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$
in Compiler Design edited by
5.8k views

2 Comments

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

1 Answer

22 votes
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 

edited by
by

4 Comments

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)
0
0
this grammar matches each else with the nearest if and is unambiguous.

Hence this language is not inherently ambiguous
1
1

Related questions