Re: Full LR(1) parser generator Hyacc 0.9 release

On Wed, 27 Feb 2008, Chris F Clark wrote:


> > on this topic. Some of my grammar examples can be found there. If there
> > is interest, I can replicate a simple example here.
>
> I presume you mean this case copied from email you sent to the Bison
> maintainers email list (I'm sorry I hadn't read the Bison related
> email archives, so I had not seen the example):


Yes. Not a problem.


> As Xin Chen points out in the discussion, the grammar is actually an
> LR(2) grammar, and that either the %left or %right declaration causes
> one of two sentences of the language to be lost. Your correction to
> flag the unreachable rule that comes from [mis-]applying the %left
> precedence with LALR table construction seems correct. If you want
> the affect of %left in that case, you are better off, simply removing
> the rule (A: a a;) that causes the conflict.


This isn't always a good solution as (A: a a;) may be useful in other
parts of the grammar. In the Bison mailing list thread you quoted, I
extend the first grammar to demonstrate how this might happen.


Of course, I've heard the argument that I'm talking about artificial toy
grammars and that any well designed grammar wouldn't suffer from these
problems. I'm not sure how to prove or disprove a statement like that
given how imprecise it is. However, in my experience, most grammars don't
start off well designed and any good design that the grammar developer
achieves may be lost (perhaps temporarily) during further development and
maintenance. Based on discussions and papers I've seen on this topic, it
seems that grammar developers can predict how a canonical LR(1) parser
behaves in such situations, but most grammar developers have difficulty
understanding the effects that various state merging algorithms have on
the parser's behavior. IELR(1) obviates the need to understand such
effects because it makes certain there are none. Thus, even if the final
grammar ends up being LALR(1), developing and debugging that grammar may
prove easier with IELR(1).


> Now, the one thing I don't understand (and it is relevant to the
> discussion) is whether the either the Pager or the IELR algorithm
> computes something different than either the LALR result or the LR
> result?


For the grammar you quoted, Pager's algorithm accepts the same language as
LALR(1) using the weak compatibility test. IELR(1) accepts the same
language as canonical LR(1) as it should for any grammar.


To be sure, I've been saying grammar when I really mean a grammar plus a
specification for resolving conflicts.


> I think one can argue that both of those results are "right"
> for this grammar.


For LR(1) algorithms (but not for implementations of them), I choose to
define "right" as the behavior of a canonical LR(1) parser simply because
it appears that canonical LR(1) exhibits the easiest behavior for a
grammar developer to understand. I'm not sure what other useful
definition of "right" exists here.

Return to the comp.compilers page.
Search the comp.compilers archives again.