Tuesday, 17 January 2012

Packrat Parser combinators for haXe.


Last time I presented you Monax (http://lambdabrella.blogspot.com/2012/01/monax-crossplatform-monads-via-haxe.html), a compiler macro that brings monadic syntactic sugar (ala haskell) to haXe and enables defining your own monads (and hooks to optimize their compositions).

I said I had several other projects waiting to be released.

So I'm proud to release now Parsex, a parser combinator which started as a side project effort to ease working with external DSLs and to which I've decided to bring some additional love by making it a packrat parser (this is largely motivated by the awesome packrat parsers which are part of the awesome Scala language libraries).

You may found some information about packrat parsers here:

The important aspect of it is that a packrat parsers memoize their results in a context (based on parsing position), lowering backtracking cost *a lot*.

Thanks to this memoization, there's no more real need to separate the lexer and the parser (it's usually the case only for performance reasons).

We're also able to detect left recursive grammars and handle them properly.

This is at the time of writting, the first general purpose Parser API in haXeland.

Here's an exmaple from the test to parse a Json array:

Combinatorial style:

static var jsonArrayP =   leftBracketP._and(jsonValueP.repsep(commaP).and_(rightBracketP)).then(JsArray);

Monadic style (using monax and which perform slighty faster):

static var jsonArrayP =
    leftBracketP; // Parses '['
    jsons <= jsonValueP.repsep(commaP); // Parses json values separated by some commas
    rightBracketP; // Parses ']'
    ret(JsArray(jsons)); // returns the result wrapped in a JSArray enum (case classes in Scala)

I'll not enter into the details as it speaks for itself.

Speed wise, it's not as fast as hand written parser; the additional cost may be aleviated with future versions of haXe with better expression generation (JS) and more inlining control.

But I think it's the fastest path for developpement speed.

Available on my github: https://github.com/sledorze/Parsex

and released on haxelib (the haXe libraries repository): http://lib.haxe.org/p/Parsex



  1. Sent it over to a haskell friend :P

    I did actually develop last year a lexer/parser generator for haXe/C++ for LALR(1) parsers. Granted that's not as nice as a parsec parser :P

    example: https://github.com/deltaluca/flappy/blob/master/UserClient/daide/lexer.hlx and https://github.com/deltaluca/flappy/blob/master/UserClient/daide/parser.hlr

  2. Oh! didn't know about this one..
    So we're more than a bunch of Haskellers out there! ;)

  3. Hello, I've just started using Haxe, and recently found your parsing library. I have an existing codebase (from Scala no less) that I'd like to port to Haxe, but I'm having an issue compiling the Parsex library. Testing with a single file: Main.hx
    import com.mindrocks.text.Parser;

    class Main {
    static public function main() {
    trace ('Hello world');

    When I compile with: "haxe -lib Parsex -main Main.hx -cpp bin", I get the following:
    include\Parsers.h(84) : error C2535: 'Dynamic Parsers_obj::_and(Dynamic,Dynamic)' : member function already defined or declared
    include\Parsers.h(78) : see declaration of 'Parsers_obj::_and'
    include\Parsers.h(85) : error C2535: 'Dynamic Parsers_obj::_and_dyn(void)' : member function already defined or declared
    include\Parsers.h(79) : see declaration of 'Parsers_obj::_and_dyn'
    ./src/Parsers.cpp(1032) : error C2084: function 'Dynamic Parsers_obj::_and(Dynamic,Dynamic)' already has a body

    include\Parsers.h(78) : see previous definition of '_and'
    ./src/Parsers.cpp(1041) : error C2084: function 'Dynamic __Parsers_obj_and(const Dynamic &,const Dynamic &)' already has a body
    ./src/Parsers.cpp(1019) : see previous definition of '__Parsers_obj_and'
    ./src/Parsers.cpp(1041) : error C2084: function 'Dynamic Parsers_obj::_and_dyn(void)' already has a body
    include\Parsers.h(79) : see previous definition of '_and_dyn'

    1. Can you open an issue here?