I do not understand this sentence from the Wikipedia article on the Dangling Else problem:
[The Dangling Else problem] is a problem that often comes up in compiler construction, especially scannerless parsing.
Can someone explain to me how scannerless parsing techniques might exacerbate this problem? It seems to me that the problem is with the grammar -- since it's ambiguous -- not with the choice of parsing technique. What am I missing?
My best guess is that the sentence in the Wikipedia article result from a misunderstanding of E. Visser work.
Grammars for scannerless parsers (i.e. grammars describing a language as set of sequences of characters instead as a set of sequences of tokens with the tokens described separately as strings of characters) tend to have lot of ambiguities. E. Visser paper Disambiguation Filters for Scannerless Generalized LR Parsers (*) proposes several mechanisms to solve ambiguities, one of which is useful for solving the dangling else problem. But the paper do not state that the precise ambiguity named "dangling else problem" is related to scannerless parsers (nor even that the mechanism is especially useful for scannerless parsers).
The fact that it proposes a mechanism for solving it isn't an implicit statement as another ambiguity resolution mechanism (operator priority and precedence) seems also totally unrelated to the scannerless nature of the considered parsers (consider for instance that those ambiguities can't be present in regular grammars as they result from nesting, while those handled by a longest match rule can).
(*) Which is probably the paper serving as base of the Wikipedia article on scannerless parsers even if they reference another one, also by E. Visser, Scannerless Generalized-LR Parsing.
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 ifs and elses it has for a longer time, but if the language spec says a single else after two ifs matches to the first if, that causes a problem with two ifs with matching elses:
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.