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

[Joel E. Denny]

On Sun, 1 Apr 2007, Paul Hilfinger wrote:

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

Yes, but it might affect viable prefixes it did not in the LR(1) parser.

I should have included an example before:

  S: 'a' A 'a'
   | 'b' A 'b'
   ;
  A: 'a' 'a'
   | 'a'
   ;

For canonical LR(1), there is a S/R conflict at the dot in this valid 
input:

  aa.a

but not at the dot in this valid input:

  ba.ab

For LALR(1), the associated states are merged so that both inputs have the 
conflict.

If you then add this:

  %left 'a'

both the LR(1) and LALR(1) parsers perform a reduce at the dot in the 
first input.  The LR(1) parser performs a shift at the dot in the second 
input, but the LALR(1) parser still performs a reduce.  Thus, the LR(1) 
parser accepts the second input, but the LALR(1) parser eventually reports 
a syntax error.

I am studying Menhir (and OCaml) now to figure out what it does with this 
grammar.

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

Yes, I am more concerned with S/R conflicts.

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

Is that better?