[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: LR(1) paser generator based on Pager's algorithm
From: |
Xin Chen |
Subject: |
Re: LR(1) paser generator based on Pager's algorithm |
Date: |
Mon, 02 Apr 2007 19:48:42 -1000 |
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.
>
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Paul Hilfinger, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm,
Xin Chen <=
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/03
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/07
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Akim Demaille, 2007/04/15