[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 18:27:19 -0400 (EDT) |
On Sun, 1 Apr 2007, Paul Hilfinger wrote:
>
> > 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.
>
> Any S/R conflict in a LALR(1) parser will also be present in the
> corresponding LR(1) parser.
Yes, but it might affect viable prefixes it did not in the LR(1) parser.
I should have included an example before:
S: 'a' A 'a'
| 'b' A 'b'
;
A: 'a' 'a'
| 'a'
;
For canonical LR(1), there is a S/R conflict at the dot in this valid
input:
aa.a
but not at the dot in this valid input:
ba.ab
For LALR(1), the associated states are merged so that both inputs have the
conflict.
If you then add this:
%left 'a'
both the LR(1) and LALR(1) parsers perform a reduce at the dot in the
first input. The LR(1) parser performs a shift at the dot in the second
input, but the LALR(1) parser still performs a reduce. Thus, the LR(1)
parser accepts the second input, but the LALR(1) parser eventually reports
a syntax error.
I am studying Menhir (and OCaml) now to figure out what it does with this
grammar.
> Personally, I never rely on Bison's R/R conflict resolution algorithm
> (i.e, pick the textually first production). I treat any R/R conflict
> as an error to be removed. Thus the prospect of having an R/R
> conflict state merged with another doesn't particularly bother me.
Yes, I am more concerned with S/R conflicts.
> It's not clear from your note what precise problem you wish to
> address. How about an explicit restatement?
Is that better?
- 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 <=
- 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, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15