Just to state the problem, the Dangling Else Problem is an ambiguity in code syntax specification where it may be unclear, in cases of nexted ifs and elses, which else belongs to which if.
The simplest and classic example:
if(conditionA)
if(conditionB)
doFoo();
else
doBar();
It is unclear, to those who don't know the specifics of the language specification by heart, which if
gets the else
(and this particular code snippet is valid in half a dozen languages, but may perform differently in each).
The Dangling Else construct poses a potential problem for scannerless parser implementations, because the strategy is to slurp up the file stream one character at a time, until the parser sees that it has enough to tokenize (digest into the assembly or intermediate language it's compiling). This allows the parser to maintain minimal state; as soon as it thinks it has enough information to write the tokens it's parsed to the file, it will do so. That's the end goal of a scannerless parser; fast, simple, lightweight compilation.
Assuming newlines and whitespace before or after punctuation are meaningless (as they are in most C-style languages), this statement would appear to the compiler as:
if(conditionA)if(conditionB)doFoo();else doBar;
Perfectly parse-able to a computer, so let's see. I get one character at a time until I have:
if(conditionA)
Oh, I know what that means (in C#), it means "push
conditionA onto the eval stack and then call brfalse
to jump to the statement after the next semicolon if it's not true". Right now I don't see a semicolon, so for now I'll set my jump offset to the next space after this instruction, and I'll increment that offset as I insert more instructions until I see a semicolon. Continuing to parse...
if(conditionB)
OK, this parses out to a similar pair of IL operations, and it goes immediately after the instruction I just parsed. I don't see a semicolon, so I will increment the jump offset of my previous statement by the length of my two commands (one for the push and one for the break) and keep looking.
doFoo();
Ok, that's easy. That's "call
doFoo". And is that a semicolon I see? Well, that's great, that's the end of the line. I'll increment both my blocks' jump offsets by the length of these two commands and forget I ever cared. OK, moving on...
else
... Uh-oh. This isn't as simple as it looked. OK, I forgot what I was just doing, but an else
means there's a conditional break statement somewhere that I've already seen, so let me look back... yep, there it is, brfalse
, right after I push some "conditionB" on the stack, whatever that was. OK, now I need an unconditional break
as the next statement. The statement that will come after that is now definitely my conditional break's target, so I'll make sure I have it right, and I will increment the unconditional break I put in. Moving on...
doBar();
That's easy. "call
doBar". And there's a semicolon, and I never saw any braces. So, the unconditional break
should jump to the next statement, whatever it is, and I can forget I ever cared.
So, what do we have... (note: it's 10:00 PM and I don't feel like converting bit offsets to hexadecimal or filling out the full IL shell of a function with these commands, so this is just pseudo-IL using line numbers where there would normally be byte offsets):
ldarg.1 //conditionA
brfalse <line 6> //jumps to "break"
ldarg.2 //conditionB
brfalse <line 7> //jumps to "call doBar"
call doFoo
break <line 8> //jumps beyond statement in scope
call doBar
<line 8 is here>
Well, that actually executes correctly, IF the rule (as in most C-style languages) is that the else
goes with the closest if
. Indented to follow execution nesting, it would execute like this, where if conditionA is false, the entire remainder of the snippet is skipped:
if(conditionA)
if(conditionB)
doFoo();
else
doBar();
... but it does so by serendipity, because the break associated with the outer if
statement jumps to the break
statement at the end of the inner if
, which takes the execution pointer beyond the entire statement. It's an extra unneeded jump, and if this example were any more complex it might no longer function if parsed and tokenized this way.
Also, what if the language specification said that a dangling else
belongs to the first if
, and if conditionA is false then doBar is executed, while if conditionA is true but not conditionB then nothing happens, like so?
if(conditionA)
if(conditionB)
doFoo();
else
doBar();
The parser had forgotten the first if
ever existed, and so this simple parser algorithm would not produce correct code, to say nothing of efficient code.
Now, the parser could be smart enough to remember the if
s and else
s it has for a longer time, but if the language spec says a single else
after two if
s matches to the first if
, that causes a problem with two if
s with matching else
s:
if(conditionA)
if(conditionB)
doFoo();
else
doBar();
else
doBaz();
The parser will see the first else
, match to the first if
, then see the second one and go into panic "what the hell was I doing again" mode. At this point the parser's got rather a lot of code in a mutable state that it would much rather have already pushed out to the output filestream.
There are solutions to all these problems and what-ifs. But, either the code needed to be that smart increases the complexity of the parser algorithm, or the language spec allowing the parser to be this dumb increases the verbosity of the language source code, such as by requiring terminating statements like end if
, or brackets indicating nested blocks if the if
statement has an else
(both of which are commonly seen in other language styles).
This is just one, simple example of a couple of if
statements, and look at all the decisions the compiler had to make, and where it could very easily have messed up anyway. This is the detail behind that innocuous statement from Wikipedia in your question.
if a then if b then s1 else s2
, then the grammar is ambiguous.