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

[Marcin Rzeźnicki]

On Tue, May 4, 2010 at 4:03 PM, Ron Burk <ronburk at gmail.com> wrote:

Hi, I've been following this thread and I must say that I've been
scratching my head thinking about what you have been attempting to
prove. Let me offer my two cents worth on all this.

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

Why shouldn't 'one assume those conflicts correspond to different alternatives'?
There is theorem that states that if a language generated by the cfg
grammar is accepted by some deterministic push-down automata then that
language has unambiguous cfg grammar. Negating this theorem gives you
that: if language is ambiguous then no deterministic push-down
automata for it exists. So it suffices to say that cfg parser is a
push-down automata to see that conflict in the parser table are effect
of language ambiguity and if you show that parser without conflicts
can be  built for a given language then that language has unambiguous
grammar

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

Why BROKEN? This is more generic conflict than you are trying to show
it is. This is NOT only if-else specific conflict so to be
sufficiently generic parser needs to issue a warning.

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

This really sounds like you like the word BROKEN :-)

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

Nope. Conflict between two choices and ambiguity are one and the same
thing, only in different models.


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

No. this is not specific category. This is very broad category of
conflicts. Let me show you an example of exactly the same conflict:
Expression can have form : {ID : type } expression
and expressions can be chained together without any delimiter
Then parser must issue a warning that  {a : INTEGER } a + b can be
seen as ( + ({a : INTEGER} a) b) or ({a: INTEGER} (+a b)).
This is exactly the same conflict yet even you, without knowing what
language I am talking about, cannot give the resolution. How can you
expect parser to give you any?