[Haskell] pre-ANNOUNCE: Generalized LR parsing added to Happy

[P.C.Callaghan]

Hello,

The CVS version of Happy now includes an extension for GLR parsing. GLR
parsing extends LR parsing to ambiguous grammars, producing a directed,
acyclic and-or graph ("a packed forest") to compactly represent the
multiple possible parses. There are many possible applications, not least
natural language, bioinformatics, sequence alignment, code generation...

It comprises an additional back-end and drivers for Happy.  The code
generated is 100% Haskell-98 or can be optimised for GHC.  The latter is
sufficiently efficient to parse a gene sequence of length 600 to a graph
of some 11000 nodes in about 10 seconds. It has two modes of recording
semantic information, either calculating the list of all possible results
or allowing detailed labelling of the forest's nodes. It is based on
undergraduate work by Ben Medlock (Durham), with some use of ideas from
Peter Ljungloef (Chalmers), and subsequently extended / improved by myself.
Its unique feature is the production of an explicit graph, which is
essential for applications involving heavy ambiguity - where simply
processing lists of alternatives leads to explosion of possibilities.


A new release of Happy containing this code is planned soon, but if anyone
is curious and would like to try the code out in advance, I'd be grateful
for comments / bugs reports. You can build from CVS, or download a linux
distribution from http://www.dur.ac.uk/p.c.callaghan/glr-dist.tgz
This package contains brief instructions and some examples. Executing
"make in-place" in the distribution's root directory should fix up paths
to allow the examples to be compiled.

The brief instructions, with an example of a forest, can be viewed at
	http://www.dur.ac.uk/p.c.callaghan/glr-simple-docs
The forest can also be viewed graphically, see
	http://www.dur.ac.uk/p.c.callaghan/glr-four.eps

Enjoy!

Paul Callaghan


--------------------------------------------------------------------------------
Dr Paul Callaghan       (Lecturer)      Email: P.C.Callaghan at durham.ac.uk
Computer Assisted Reasoning Group, Department of Computer Science, Durham
                   http://www.dur.ac.uk/CARG