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

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.

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