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

[Xin Chen]

Hi Joel,

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.

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.

Thanks,
Xin

----- Original Message -----
From: "Joel E. Denny" <address@hidden>
Date: Monday, April 2, 2007 8:21 am
Subject: Re: LR(1) paser generator based on Pager's algorithm
To: Xin Chen <address@hidden>
Cc: Paul Hilfinger <address@hidden>, Akim Demaille <address@hidden>, 
address@hidden

> On Mon, 2 Apr 2007, Joel E. Denny wrote:
> 
> > > In my impression, this can intuitively 
> > > cover all such cases, and this problem is already solved. A 
> strict proof 
> > > may be needed. Then as Knuth said, be alerted, since "I have 
> proved it, 
> > > but did not try it"..
> > 
> > Here's a counter-example:
> > 
> >   S: 'a' A 'a'
> >    | 'b' A 'b'
> >    ;
> >   A: 'a' 'a' 'a'
> >    | 'a' 'a'
> >    ;
> > 
> > Here's the additional itemset that must be split:
> > 
> >   A: 'a' . 'a' 'a' ['a' 'b']
> >    | 'a' . 'a'     ['a' 'b']
> 
> But hmm... I easily foresee the upcoming S/R conflict by 
> inspection.  
> This looks promising, but I need to think more about whether that 
> works in 
> general.  I have to run now.
>