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

[Joel E. Denny]

On Mon, 2 Apr 2007, Xin Chen wrote:

> Yeah, please think more about it to see if any counter example can be 
> found. BTW, I'm thinking about whether I can find a constructive proof 
> on this.

So this one takes a bit more work:

  S: 'a' A 'a'
   | 'b' A 'b'
   ;
  A: 'a' 'a' B
   ;
  B: 'a'
   | %prec 'a'
   ;

You'll have to avoid the merge creating this item set:

  A: 'a' . 'a' B ['a' 'b']

It's harder to foresee the S/R conflict that the merge here creates in its 
successor.  Moreover, imagine if the productions for B were much more 
complex.  Imagine if A had other RHSs ending in other nonterminals.

By the way, here's an extended grammar that makes all productions useful 
so that Menhir (at least) reports no warnings:

  S: 'a' A 'a'
   | 'b' A 'b'
   | 'c' c
   ;
  A: 'a' 'a' B
   ;
  B: 'a'
   | %prec 'a'
   ;
  c: 'a' 'a' 'b'
   | A
   ;

> For the short report comparison.pdf, I sent it to the Bison 
> maintainers' email list. If you lost it, I think Akim can send you one 
> copy.

There's no message from you in the bison-maintainers archive.  Maybe it 
was never approved.  Anyway, if it's important to our discussion and you 
don't want to post it publicly, you could always send it to me privately.