Dangling Else Problem in Compiler
In this class, We discuss Dangling Else Problem in Compiler.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of the problem with ambiguous grammar. Click Here.
We take an example and understand the dangling else problem.
Most of the programming languages work the same way as the below example.
Example:
if(E) then
if(E) then
if(E) then
STMT
else
STMT
The above nested if the example has to match the ‘else’ with the nearest unmatched ‘if’ statement.
Example 2:
if(E) then
if(E) then
if(E) then
STMT
else
STMT
else
STMT
The first ‘else’ will match the third if statement, and the second ‘else’ will match the second if statement.
The way mentioned above, the programming languages will work.
Example Grammar to identify if-else statements:
The below example grammar is ambiguous grammar to identify the if-else statement.
STMT – if (E) then STMT | if (E) then STMT else STMT | other
Because of the ambiguity, the below example program is identified in two different ways.
The below derivation trees show the different possibilities for the program.
One derivation tree takes else to the internal if statement.
The other derivation tree takes the else statement to the outer if statement.
The above example is what we call dangling else problem.
We need to find complex context-free grammar to solve the dangling else problem.
The below grammar solves the dangling else problem.
Unambiguous grammar for dangling else:
STMT – Matchedstmt | Openstmt
Openstmt – if (E) then STMT | if (E) then matchedstmt else openstmt
Matchedstmt – if (E) then Matchedstmt else Matchedstmt
Logic:
If ‘if’ statement that obtained inside, then and else should have an else statement.
So we separate a matched statement production which always takes if and else statements.
In between then and else, we must place matched statement.
In programming languages like C, they added brackets to avoid writing complex CFG in compilers.
Example:
if(E) then
if(E) then
if(E) then
STMT
else
STMT
The above example else part is assigned to 3rd if statement.
Suppose we need to assign the else part to the first ‘if’ statement, they provided brackets.
if(E) then
{
if(E) then
if(E) then
STMT
}
else
STMT
The else statement is assigned to the first if statement.
The brackets help in avoiding writing complex CFG during compilation.