[Haskell-cafe] [Off-topic]Functional parsing theory

[Dominique Devriese]

Mauricio,

2010/10/6 Maurí­cio CA <mauricio.antunes at gmail.com>:
> I've been working in a tool that reads a grammar with associated
> actions and act on input based on that grammar. I would like to
> rewrite it in a functional style, but I've not been able to find a
> theory that would handle any possible grammar with cyclicity and
> empty productions, and flexibility is more important for this tool
> than performance.
>
> Do you have a suggestion on that? What I'm using now is this
> (non-functional) article on Earley method:

I'm not sure what you're looking for exactly, but my
grammar-combinators library [1] might be interesting for you. It is
not yet industry-proof at the moment, but might benefit from some more
real-world use and comments. It is a novel functional parsing library
using an explicit representation of recursion which allows it to
support many different parsing algorithms and grammar transformations.

Anyway, in the functional world, parsing algorithms used are often LL
parsing algorithms, often used with parser combinators. Other
algorithms can sometimes be emulated in a functional style using a
top-down parsing algorithm on a transformed grammar (e.g. left-corner
transform, but I also suspect you can emulate LR parsing using what I
call the uniform Paull transformation). My library automates two such
important transformations (supporting for example left-recursion).

Dominique

Footnotes:
[1] http://projects.haskell.org/grammar-combinators/