Re: LR(1) paser generator based on Pager's algorithm

[Paul Hilfinger]

 > Bison can generate parsers for some non-LR(1) grammars by using its 
 > conflict-resolution mechanisms.  I don't believe Pager's algorithm was 
 > intended to handle this situation.  The algorithm seems to allow two 
 > states to be merged even if one state has a conflict (S/R or R/R) that the 
 > other does not.  Thus, the parser would encounter this conflict for viable 
 > prefixes that this conflict would not affect in a canonical LR(1) table.  
 > If Bison's resolution of the conflict changes the action for these viable 
 > prefixes, the parser would report mysterious syntax errors.

Any S/R conflict in a LALR(1) parser will also be present in the
corresponding LR(1) parser.  Hence, Bison's precedence-based conflict
resolution (which applies only to S/R errors) is orthogonal to the
extra R/R conflict avoidance afforded by LR(1).  

Personally, I never rely on Bison's R/R conflict resolution algorithm
(i.e, pick the textually first production).  I treat any R/R conflict
as an error to be removed.  Thus the prospect of having an R/R
conflict state merged with another doesn't particularly bother me.

 > I am trying to figure out how to solve this problem.  Is there prior work 
 > on this issue?  I haven't hit Google hard enough yet and I need to check 
 > what Menhir does, but I'd appreciate pointers if you have them.

It's not clear from your note what precise problem you wish to
address.  How about an explicit restatement?

Paul Hilfinger