9
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ And in your last example, which of the two possible parses do you regard as "natural", or correct, and why? $\endgroup$ – rici Jan 17 '17 at 3:10
  • $\begingroup$ @rici Yes, this is a tricky question!, and I don't know. I'll be happy with an unambiguous grammar which produces either parsing of $aacbacbc$. What I mostly care about is that $aaa\ldots aaacbcbc\ldots bc$ (with more $a$'s than $b$'s) matches the $k$-th last $b$ with the $k$-th $a$ (and leaves the innermost $a$'s unmatched). $\endgroup$ – Gro-Tsen Jan 17 '17 at 10:17
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Congratulations on achieving what I had concluded was probably impossible! I checked experimentally that for words of length ≤16 this grammar is indeed unambiguous and generates the same words as the ones in my question. Now I have to understand in detail how it works! $\endgroup$ – Gro-Tsen Jan 17 '17 at 23:47
  • $\begingroup$ @Gro-Tsen: I hope the second paragraph helps explain it. The grammar is a lot simpler with the spurious ambiguities left in: $S \to aSbT \;|\; aMbS$ ($M$ as in my solution, $T\to aT\;|\;c$) and that's what I came up with when I was thinking about the problem. It took me a while to convince myself that it was necessary to make $U$ be non-nullable in order to avoid ambiguous parses (although, as I said, the ambiguity is relative), and a while longer to work around my distaste for the way I chose to enforce that. I'll bet there is a more elegant presentation. $\endgroup$ – rici Jan 17 '17 at 23:54
0
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Note that "if … then … else if … then … else if … then … else …" corresponds to $acbacbacbc$ in my notation: this is parsed unambiguously by my initial grammar (and the variants I give agree), so I'm not asking for an alternative parse of this. $\endgroup$ – Gro-Tsen Jan 17 '17 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.