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@durham.ac.uk Computer Assisted Reasoning Group, Department of Computer Science, Durham http://www.dur.ac.uk/CARG