Re: Bison's GLR mode

[Hans Aberg]

At 17:17 +0100 2004/10/11, A Johnstone wrote:
>I'm writing rather tentatively as a designer of parsing algorithms rather
>than as a user of Bison.

Such issues are generally best addressed at the Bug-Bison list.

>Now to the difficult bit. We're pretty clear that Bison's GLR mode isn't
>what the world means by GLR, that is a derivative of Tomita's 1985
>algorithm which uses a graph to represent multiple stacks, compressing
>both common prefixes and common suffixes. I think the generalised Bison
>parser is just replicating stack tops, which can generate exponential
>memory consumption. This means it can be very quickly choked: we have a
>grammar that causes Bison to run out of memory after just a few tokens.

The Bison GLR parser was written by Paul Hilfinger
<address@hidden>. You might check with him about it.

>In addition, the extraction of derivations (or parser trees), and the
>execution of semantic actions, from generalised parsers is not at all
>straightforward and I don't think the existing tools within Bison will do
>the job. The Amsterdam team responsible for the ASF+SDF toolkit have the
>scars to show what is involved in disambiguating actions. Users will, I
>think find that the behaviour of general parsers built using Bison as it
>presently is will often generate nasty surprises.

There seems to be two ways to excite rule actions in a GDP (generalized
deterministic parser): Immediately, or delayed until branches have been
resolved. Bison chooses the latter. But the former ones would ensure that
typical DP tweaks can always be translated into GDP. Or do you have
something else in your mind?

>So, after all that, the help query is: can we help out with the
>development effort?

Bison has been modularized by Akim Demaille <address@hidden>, in order to
admit multiple Bison algorithms existing in parallel. So there are two
possibilities, it seems: Either you enhance Bison's current GLR parser, or
write your own, entirely new module.

>I don't really understand how decisions are made about
>what goes into a GNU release, and I neither want to reinvent the wheel nor
>step on anybody else's territory, but we have a lot invested in GLR
>technology and we'd like to help spread the word.

I suggest you contact Paul Hilfinger and/or Akim Demaille.