retagged by
6,285 views
7 votes
7 votes
For the grammar given below

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

Which of the following statement/s is/are true

1.The grammar is ambiguous and the ambiguity can be resolved.

2.grammar is ambiguous and the ambiguity cannot be resolved.

3.The grammar is unambiguous.

If we try to remove nondeterminism , will ambiguity always be removed?
retagged by

3 Answers

7 votes
7 votes

The given grammar is an ambiguous one and specifically due to 2 S in one production and left factoring.Let us see how :

==> If we write i == "if "  ,  e  =  "expr"  t = "then"  , S = "stmt"  and  b =  "other"  then , we have :

S --> ietSeS  |   ietS | b

As clear from the given grammar it suffers from left factoring problem as ietS comes in 2 productions as we can see clearly..So to eliminate this problem which is characteristic of non determinism we have :

Let ietS   =   A , then we can rewrite the grammar as :

S --> ietSS'  | b

S' --> eS | ϵ , 

Thus the left factoring is removed..

Now the analysis becomes simpler ..

Say we have input string : ietietbeb then we have 2 derivation trees for it, one substituting epsilon for earlier S' and which is in the bottom level of derivation tree..So the grammar is an ambiguous one..

This problem is more commonly known as "dangling else problem"..There are various approaches to resolve the ambiguity associated with the problem ..

Sometimes the CFG is modified so that it is unambiguous, such as by requiring an endif statement or making else mandatory. In other cases the CFG is left ambiguous, but the ambiguity is resolved by making the overall phrase grammar context-sensitive, such as by associating an else with the nearest if. In this latter case the grammar is unambiguous, but the CF grammar is ambiguous.

Overall the language is not inherently ambiguous as ambiguity is of removable nature here..Hence option 1) is correct here..

Also let me mention :

The factors  left recursion and left factoring are possible causes of ambiguity..They will not create ambiguity always..

edited by
4 votes
4 votes

The given grammer is well known as " Dangling Else " problem  .  The given grammer 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 coditional statement for the above grammer

if $E1$ then $S1$ else if $E2$ then $S2$ else $S3$ has the following parse tree

Well this is ambiguous due to the statement
if $E1$ then if $E2$ then $S1$ else $S2$

The two parse trees are

Ambiguity can be elimated 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

Source

Good Read 

edited by
–1 votes
–1 votes
Removing undeterminism using left factoring doesn't eliminate ambiguity.

Grammar:

S-->iEtS|iEtSeS|a

E-->b

After left factoring:

S-->iEtSS'|a

S'-->epsilon|eS

E-->b
Answer:

Related questions

3 votes
3 votes
3 answers
1
24 votes
24 votes
1 answer
2
Harsh Tripathi asked Jun 30, 2016
4,632 views
DANGLING ELSE PROBLEM:S->iEtSS' / aS'->∊/ eS E->b is a Deterministic context free grammar, and is ambiguous for "iEtiEtSeS" but ALL DCFG ARE UNAMBIGUOUS . so " how c...