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.