1
$\begingroup$

I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last if. I still don't see how this solves the problem. Can somebody give me an explanation?

I searched before I put the question and none answered my question

enter image description here

$\endgroup$
  • 3
    $\begingroup$ Are you asking what the dangling-else problem is, how "match the last if" solves it or how the given grammar implements this? $\endgroup$ – David Richerby Feb 3 '18 at 17:20
2
$\begingroup$

The problem is that the code is ambiguous. You can interpret it either as

If C1 then
   If C2 then
     S1
   else
     S2

or as

If C1 then
   If C2 then
     S1
else
   S2

The compiler needs to choose one way and covert it into machine language. The solution of "choose the last if" means the compiler will choose solution number 1 -- will attribute the "else" to the last (open, non-matched) "if" statement.

$\endgroup$
0
$\begingroup$

The language in question uses a grammar. The grammar is ambigous. However, the language can have rules that are not represented in the grammar (which means the actual language is not the language implied by the grammar but slightly different), and the compiler may implement other rules than just those represented by the grammar.

In this case, there is an additional rule: "If an else could match two if's according to the grammar, then it matches the last if". That solves the problem.

The alternative is to modify the grammar, as you saw. The alternative is the preferred solution in simple cases.

$\endgroup$
0
$\begingroup$

I think this can be a possible answer:

[After left factoring and making it unambiguous]

Let other = a

S -> iEtT | a

T -> S | aeS

I am generating all if's first and associating the else with the recent unassociated if . If I have to get an else, I should be eliminating the possibility of getting a new if between the current unassociated if and corresponding else.
However I am allowing the possibility of getting an if after generating the corresponding else.

Point out if there are any errors.

Thank you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.