Is there a different resolution of the “dangling else” problem other than “match closest”?

Question

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for else and $c$ stands for some other kind of instruction or block): $$ \begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned} $$ For example, $aacbc$ can be parsed as $(a(acbc))$ or as $(a(ac)bc)$ (this is the simplest/shortest ambiguous word for this grammar).

The "standard" way to resolve this "dangling else" ambiguity forces the "else" ($b$) statement to pair with the closest/innermost "if-then" ($a$). This can be accomplished as follows: $$ \begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned} $$ This grammar is unambiguous. In the above example, it forces the $(a(acbc))$ parsing.

Question: Is there another natural way to resolve the ambiguity that would force the $(a(ac)bc)$ parsing of $aacbc$? In other words, I am looking for a grammar that generates the same language as the two above, that is unambiguous, and that parses $aacbc$ as $(a(ac)bc)$.

Remark: My first attempt was as follows: $$ \begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned} $$ which resolves the ambiguity of $aacbc$ as required — but this grammar is still ambiguous: $aacbacbc$ can be parsed as $(a(ac)b(acbc))$ or as $(a(acb(ac))bc)$.

Answer 1

This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before each $b$ and one at the very end.) Because it fits better with my parenthetic brain, I write as though that were the problem at hand.

The traditional "match closest" dangling-else resolution matches each close with the most recent as-yet-unmatched open. That means that there is never an unmatched open (or close, for that matter) between a matched open and its matching close.

One possible alternative would be to match each close with the earliest feasible unmatched open. "Feasible" here means that the open could be matched without violating parenthetic nesting (eg. the first $($ in $()()$ cannot feasibly match the last $)$).

This matching has to be done outside-in, so that a match for a close is not attempted until all the enclosing pairs have been matched. This fact makes it impossible to produce a parse with a bounded-lookahead algorithm, since the parse has to work inwards from both ends, after having split the string into completely matched segments (because those effectively limit the range of potential matches).

However, the fact that an online left-to-right parser doesn't exist does not imply that there is no unambiguous CFG. (Evidently: a palindromic language must be parsed from both ends towards the middle, but it's easy to write an unambiguous grammar).

To produce a grammar for the "furthest-match" parenthesis problem, I relied on the fact that an unmatched open cannot be followed by a matched open. If it were, then the furthest-match property wouldn't apply because the unmatched open could have matched the matched open's close, so the fact that it is unmatched violates the furthest-match property.

So here's the slightly clunky grammar:

$$ \begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned} $$

$S$ is the start symbol; $M$ are fully-matched statements; $U$ are definitely unmatched statements (which means they include at least one unmatched $a$, so they can't be empty) and $T$ is a "tail" consisting only of unmatched $a$s. The above fact about unmatched open's can be read directly from the grammar: all unmatched opens are derived from $T$, a $T$ can only appear at the end of a $U$, and a $U$ can only be followed by a $T$.

The clunkiness comes from preventing $U$ from matching the empty string. That prevents a bunch of what I consider spurious ambiguities: They are spurious in the sense that the matching of the opens and closes is the same in all alternative parses. If $U$ is allowed be nullable, it will also derive a completely balanced string. Since $S$ is, in effect, $M^* U$, that leads to an ambiguity in which you could consider a completely-balanced $S$ to be a series of $M$ followed by an empty $U$, or one fewer $M$ followed by a completely balanced $U$.

Probably there's a better workaround than the one I chose. But this one seems to work, and it plays well with Bison's GLR parser which I used to test it; that parser complains about ambiguous parses unless you write extra code to handle the ambiguity, and I was too lazy to do that. I tested it with strings of up to 20 open+closes, and it seems to have produced an unambiguous parse for every correctly-nested sequence, without producing parses for incorrectly-nested sequences.

Answer 2

Take a+b+c+d+e and a-b-c-d-e. There are two obvious ways how a grammar could parse these, but there is one way that we use.

In the case of the "dangling else", that's not actually how people look at it. Instead the syntax is interpreted as "if", followed by zero, one or more "else if", followed by an optional "else".