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

Christopher L Conway cconway at cs.nyu.edu
Tue May 4 08:57:56 PDT 2010


Dude. Chill out.

Best regards,
Chris

On Tue, May 4, 2010 at 10:03 AM, Ron Burk <ronburk at gmail.com> wrote:
>> 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.
>


More information about the antlr-interest mailing list