[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: |
Tue, 03 Apr 2007 21:02:26 -1000 |
Joel,
That looks to be a valid counter-example. I think we indeed need to consider
about splitting states before a conflict actually happens. Or we do combine,
and when conflict occurs, use GLR or LR(2) to solve it.
Or when the programmer has such a mysterious conflict, he has to rewrite his
grammar until that conflict disappears. But that's not why we are here.
Xin
----- Original Message -----
From: "Joel E. Denny" <address@hidden>
Date: Tuesday, April 3, 2007 6:18 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, 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.
- Re: LR(1) paser generator based on Pager's algorithm, (continued)
- 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, 2007/04/15
- 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 <=
- 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