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

"Joel E. Denny" <jdenny@ces.clemson.edu>
Mon, 25 Feb 2008 12:43:43 -0500 (EST)

          From comp.compilers

Related articles
[5 earlier articles]
Re: Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Thomas Chen) (2008-02-12)
Re: Full LR(1) parser generator Hyacc 0.9 release haberg_20080207@math.su.se (Hans Aberg) (2008-02-13)
Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-14)
Re: Full LR(1) parser generator Hyacc 0.9 release cfc@shell01.TheWorld.com (Chris F Clark) (2008-02-14)
Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-23)
Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-24)
Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-25)
Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-26)
Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-27)
Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-27)
Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-27)
Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-28)
Re: Full LR(1) parser generator Hyacc 0.9 release cfc@shell01.TheWorld.com (Chris F Clark) (2008-02-28)
[2 later articles]
| List of all articles for this month |

From: "Joel E. Denny" <jdenny@ces.clemson.edu>
Newsgroups: comp.compilers
Date: Mon, 25 Feb 2008 12:43:43 -0500 (EST)
Organization: Compilers Central
References: 08-02-019 08-02-022 08-02-030 08-02-037 08-02-040 08-02-041 08-02-044 <Pine.SOC.4.61.0802230000570.9914@unixlab03.ces.clemson.edu> 08-02-076
Keywords: parse, LR(1)
Cc: compilers@iecc.com
Posted-Date: 25 Feb 2008 19:38:54 EST

On Sun, 24 Feb 2008, Chris F Clark wrote:


> Joel E. Denny wrote:


> > merging states with
> > identical cores cannot produce new S/R conflicts.


I should have mentioned that the dragon book states this in its
discussion of LALR parser table construction.


> > LALR(1), Pager's algorithm, IELR(1), and canonical LR(1) are all parser
> > table generation algorithms. When the grammar is non-LR(1) coupled with a
> > specification for resolving conflicts, I have found examples where the
> > parser tables generated by Pager's algorithm do not accept the same
> > language as do the parser tables generated by canonical LR(1). I have not
> > found such examples for IELR(1) versus canonical LR(1).
>
> The example where Pager's algorithm parses differently when conflict
> resolution is added would be interesting. I don't see how it should
> happen, since s/r conflicts should be preserved over all splitting and
> merges of the LR states (as you showed above).


Every S/R conflict is preserved for at least some but not necessarily
all of its viable prefixes. Before splitting, the conflict might
resolve as a reduce. After splitting, the action is a shift for any
viable prefix for which the conflict is not preserved. That is, for
such viable prefixes, the action might change. This is the scenario I
most commonly encounter.


> If the tables resulting from applying Pager's algorithm, and then
> applying s/r conflict resolution differ from the results of applying
> s/r conflict resolution to other LR-family tables, it suggests
> something is wrong.


Earlier in this thread, Thomas Chen posted links to some other
discussions on this topic. Some of my grammar examples can be found
there. If there is interest, I can replicate a simple example here.


Post a followup to this message

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