[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: |
Joel E. Denny |
Subject: |
Re: LR(1) paser generator based on Pager's algorithm |
Date: |
Tue, 3 Apr 2007 12:18:05 -0400 (EDT) |
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, 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, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm,
Joel E. Denny <=
- 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