Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
The only thing I can think of is that a scanner-less parser needs a more complex grammar, making it more difficult to provide heuristics for resolving the ambiguity. –  Giorgio Jun 18 '13 at 16:59
    
That's odd. The Wikipedia cites if a then if b then s else s2 as ambiguous because it could mean either if a then (if b then s) else s2 or if a then (if b then s else s2). I thought that it was pretty much assumed and well-understood that the else always refers to the closest if in these cases (the second meaning), unless it is preempted by clarifying syntax like braces or indentation. –  Robert Harvey Jun 18 '13 at 17:44
3  
@Robert Harvey: The point is that this assumption must be reflected by the syntax tree. If a grammar allows to derive two different syntax trees for the string if a then if b then s1 else s2, then the grammar is ambiguous. –  Giorgio Jun 18 '13 at 17:47
1  
@RobertHarvey a common way to define languages is using a context-free grammar, plus a bunch of rules which disambiguate the grammar, if necessary. –  user39685 Jun 18 '13 at 17:52
1  
Not all the scannerless parsers created equal. For, say, PEG or GLR, a dangling else behaviour is always predictable. –  SK-logic Jul 11 '13 at 9:38

2 Answers 2

up vote 5 down vote accepted
+100

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.

share|improve this answer

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.

share|improve this answer
1  
Interesting but I'm far from sure that's what was intended by the Wikipedia article. It references (through the scannerless entry) a report by Eelco Visser whose content at first sight is not compatible with your explanation. –  AProgrammer Jul 10 '13 at 9:16
2  
Thanks for the response, but it doesn't really address the OP. I don't agree with the assumptions in the post about what the goal of a scannerless parser is and how it's implemented. There are many ways to implement scannerless parsers and this post seems to only deal with a limited subset. –  user39685 Jul 10 '13 at 13:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.