BISON's GLR mode

[A Johnstone]

Dear all,

I'm writing rather tentatively as a designer of parsing algorithms rather
than as a user of Bison. Just to establish some credentials: my research
group (Liz Scott, myself and some grad students especially Giorgios
Economopoulos) have been working with generalised parsers for a few years:
amongst other things we've produced a significant simplification of
Tomita's GLR algorithm which is correct and more efficient than variants
described in the literature. You can read some of our papers in the
Compilers Conference for 2003 and 2004, and a I'm expecting a big paper on
our algorithm to appear in ACM TOPLAS sometime soon. There's some other
relevant stuff in Acta Informatica and (provisionally, to appear) in the
Computer Journal. Our algorithm (called Binary Right Nulled GLR parsing or
just BRNGLR) achieves worst case cubic runtime and quadratic space whilst
preserving the linear time-and-space behaviour of traditional LALR
parsing for those parts of the grammar that are LALR. In practice this
means that it is not far off the performance of straight LALR parsing
for deterministic grammars, and degrades gracefully therafter to a
managable worst case. Oh, and it is easy to implement.

As you can imagine, we were really pleased to hear a couple of years ago
that Bison now incorporated a GLR mode because we spend quite a lot of
time convincing people that general parsing is (a) good software
engineering and (b) now acceptably efficient. (As an aside, I also really
like Scott McPeak's Elkhound tool which also shows the way, and we also
have a reasonably close working relationship with the Amsterdam team who
are responsible for ASF+SDF which is probably the most mature GLR parser
generator available today.)

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.

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.

So, after all that, the help query is: can we help out with the
development effort? 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.

                          Adrian

Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London,  Egham, Surrey, TW20 0EX, England.
Email address@hidden Tel:+44(0)1784 443425 Fax:+44(0)1784 439786