[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: |
Sun, 1 Apr 2007 00:40:32 -0400 (EDT) |
I'm taking this public.
On Mon, 19 Mar 2007, Akim Demaille wrote:
> Your timing is incredible: Joel, who is also a Bison maintainer,
> recently reported that he was about to implement LR(1) into Bison. He
> didn't say exactly what technique he had in mind, but since we had
> been talking about proposing Pager's algorithm for Google Summer of
> Code like last year
> (http://www.gnu.org/software/soc-projects/ideas-2006.html#bison), I
> figured that's the one he was thinking about.
I've most recently been reading Pager's "A Practical General Method for
Constructing LR(k) Parsers". Is this the algorithm either of you have in
mind? I believe this is what Menhir uses. Unfortunately, I'm not sure
it's exactly what Bison needs.
Bison can generate parsers for some non-LR(1) grammars by using its
conflict-resolution mechanisms. I don't believe Pager's algorithm was
intended to handle this situation. The algorithm seems to allow two
states to be merged even if one state has a conflict (S/R or R/R) that the
other does not. Thus, the parser would encounter this conflict for viable
prefixes that this conflict would not affect in a canonical LR(1) table.
If Bison's resolution of the conflict changes the action for these viable
prefixes, the parser would report mysterious syntax errors.
I realize this problem is already present for LALR(1), and I believe it is
more subtle than LALR(1)'s creation of completely new mystery conflicts.
I'm not sure how frequently it appears for real grammars. Even so, I'd
prefer to fully eliminate all the mysteries of LALR(1) from Bison.
I am trying to figure out how to solve this problem. Is there prior work
on this issue? I haven't hit Google hard enough yet and I need to check
what Menhir does, but I'd appreciate pointers if you have them.
- Re: LR(1) paser generator based on Pager's algorithm,
Joel E. Denny <=
- 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