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

[Joel E. Denny]

I'm taking this public.

On Mon, 19 Mar 2007, Akim Demaille wrote:

> Your timing is incredible: Joel, who is also a Bison maintainer,
> recently reported that he was about to implement LR(1) into Bison.  He
> didn't say exactly what technique he had in mind, but since we had
> been talking about proposing Pager's algorithm for Google Summer of
> Code like last year
> (http://www.gnu.org/software/soc-projects/ideas-2006.html#bison), I
> figured that's the one he was thinking about.

I've most recently been reading Pager's "A Practical General Method for 
Constructing LR(k) Parsers".  Is this the algorithm either of you have in 
mind?  I believe this is what Menhir uses.  Unfortunately, I'm not sure 
it's exactly what Bison needs.

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.

I realize this problem is already present for LALR(1), and I believe it is 
more subtle than LALR(1)'s creation of completely new mystery conflicts.  
I'm not sure how frequently it appears for real grammars.  Even so, I'd 
prefer to fully eliminate all the mysteries of LALR(1) from Bison.

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.