# 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*

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