[antlr-interest] The Classic else (Non-)Ambiguity

[Ron Burk]

> There really is an ambiguity.

The grammar (a high-level, abstract specification) is ambiguous.
The parser conflict (a low-level, implementation decision) is not ambiguous.
Recall that parser generators, in the general case, know only about
conflicts in building their tables, not grammar ambiguities (as we all
know by heart, no program can detect ambiguous grammars in the general
case). In the grammar I supplied, all parser generators are warning
about conflicts in building their tables; one should not assume those
conflicts correspond to different alternatives of the grammar
ambiguity.

> really can be parsed, in general, as either

Not by an LL(1) parser with that grammar as input.
Not by an LALR(1) parser with that grammar as input.

More importantly, that is NOT what ANTLR or any other parser generator
is warning about when trying to process this grammar, and overriding
the default choice of ANTLR or any other parser generator will give
you a BROKEN PARSER, not one that selects an alternative
interpretation of the (in this case, happens to be) ambiguous grammar.

> What you are correct in pointing out is that only hard and fast rule
> that makes sense

This really sounds like you don't understand that overriding the
choice the parser generator is complaining about produces a BROKEN
parser.

> imagine a parser that did not implement a hard and fast rule and
> instead generated both parse trees and allowed the client to decide
> which it liked best (and indeed there are parser generators that
> behave that way, e.g., SGLR [1]).

Again, ANTLR is not complaining that the grammar is ambiguous. It is
complaining about a conflict between two choices. One of which utterly
fails to produce a parser that recognizes the input grammar.

> It really is best to avoid these kinds of ambiguities and to
> understand them if they exist in your grammar. Issuing a warning is
> the right thing to do.

Again, parser generators do not detect grammar ambiguities -- they
detect conflicts in constructing their tables. ANTLR is not warning
that the grammar is ambiguous. It is warning that it could not decide
between two choices -- one of which results in a BROKEN PARSER.

> It really is best to avoid these kinds of ambiguities and to
> understand them if they exist in your grammar. Issuing a warning is
> the right thing to do. The grammar author can take a look and say,
> "Yes, this is an if-then-else-like construct and I'm OK with the eager
> behavior," or, "No, this is a mistake. I'm going to rethink this
> rule."

No. This specific category of parser conflict always has the same
answer, always has an obvious meaning, and always results in
the parser claiming it was conflicted about choosing between the
obvious meaning and a BROKEN PARSER.