[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: Akim Demaille
Subject: Re: LR(1) paser generator based on Pager's algorithm
Date: Sun, 1 Apr 2007 07:27:41 +0200

Le 1 avr. 07 à 06:40, Joel E. Denny a écrit :

I'm taking this public.

I'm including Yann, who worked on Menhir.

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
(, 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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]