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

[P.C.Callaghan]

Dear all,

An update on the GLR extension for Happy:

Several improvements in speed and functionality have been made since the
August version. The full release as part of Happy will occur soon, but a
sneak preview plus useful information can be found on page:
	http://www.dur.ac.uk/p.c.callaghan/happy-glr

This will be a permanent page for distributing information, tips,
interesting examples, experimental releases etc.

The currently contains a current linux build (as .tgz, compiled on
Fedora), and a current windows build (as a zip file)

These packages contain full documentation on the GLR extension and some
relevant examples.  Executing "make in-place" in the distribution's root
directory will fix up paths to allow the examples to be compiled. (This
works on the linux version or Windows with Cygwin etc - there's no support
for other combinations yet.)


>From the earlier message:

> 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 1200 to a graph
> of some 23400 nodes in about 4 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.

Since August, the following change have been made:
 * much faster
 * better representation (ideal for local ambiguity packing)
 * supports monadic semantic values in tree-decode mode (ie, Happy's
   %monad directive and {%...} facility.)
 * can parse grammars with hidden left recursion.
 * full documentation added
 * wider set of examples

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