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

[Chris verBurg]

I'm not sure my comments would be useful amongst all the parsing-theory
heavyweights on this list, but here goes.  :)


2010/5/4 Marcin Rzeźnicki <marcin.rzeznicki at gmail.com>

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


After my own bout of head-scratching, I think I finally realize what Ron's
assertion is.  A parser that binds the "else" to the outermost "if" is
unable to handle a rather simple case:

    if A then
        if B then
            ...
        else
            ...
    else
        ...

If that first "else" bound to the first "if", then the second "else" is a
syntax error -- it's just sitting out in la-la land without an "if" to
attach to.  In this case, the first "else" has to bind to the last "if".
 Ron's assertion is that if you generalize *that* as the rule, then
"if-else" isn't really ambiguous.


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

I may be misreading your example here, and if so please correct me:

Your expression ("{a: INTEGER} a+ b") could also be written as "{a: INTEGER}
a + {b: INTEGER} b", and the only valid parse for that is "(+ ({a: INTEGER}
a) ({b: INTEGER} b))".  Thus the correct parse for your original expression
is your first one, "(+ ({a: INTEGER} a) (b))".

Though the more I read this over the more I think I misunderstood you.  :)

-Chris