[Caml-list] First release of P3: a combinator parser library, and parser generator

[Caml-list] First release of P3: a combinator parser library, and parser generator

[Tom Ridge]

[-- Attachment #1: Type: text/plain, Size: 848 bytes --]

Dear caml-list,

I'm pleased to announce the first release of the P3 combinator parser
library, and parser generator. It is essentially a synthesis of Earley
parsing with combinator parsing.

The url is: http://www.tom-ridge.com/p3.html

The main features are:

  * handles all context free grammars

  * fast (when memoized)

  * correct (hopefully)

  * simple (depending on your viewpoint)

  * scannerless (probably not a good idea - a separate lexing phase
    can result in much faster overall performance - but makes
    everything much simpler)

  * parsers implemented via combinators can be integrated easily with
    the core language (OCaml in this case), allowing full use of host
    language features eg modules etc




I'm sure there is much scope for improvement, but I thought I would
release it now to get feedback.

Thanks

Tom

[-- Attachment #2: Type: text/html, Size: 1554 bytes --]

Re: [Caml-list] First release of P3: a combinator parser library, and parser generator

[Daniel Bünzli]

Hello Tom,

Combinator parsers were an obsession of mine a few years ago. I really liked the approach but eventually always ended up writing LL(k) parsers (xmlm, jsonm) by hand which so far has been the only "technology" that allows me to give the best error messages/correction, to handle asynchronous IO, and to remain reasonably efficient. 

Could you maybe comment on these points:  

* What's the error handling strategy ? Is there support for error correction ? 
* Is there support for non-blocking parsing (asynchronous IO) ? 

Best,

Daniel

Re: [Caml-list] First release of P3: a combinator parser library, and parser generator

[Tom Ridge]

[-- Attachment #1: Type: text/plain, Size: 1614 bytes --]

Dear Daniel,

It isn't a fully tooled parser by any stretch of the imagination! Sorry.

* What's the error handling strategy ? Is there support for error
correction ?

Yes, I need to do something here. At the moment, there is no real handling
of errors, and nothing to support error correction (I'm not completely sure
what error correction is).

* Is there support for non-blocking parsing (asynchronous IO) ?

No. :( It works on strings, which have to be fully loaded in memory. I
guess the use case I'm thinking of is a researcher who wants to quickly
knock up a parser, without worrying about fiddling around with the grammar,
to parse inputs of moderate size, and who doesn't care too much about
absolute performance.

For large inputs, which must be parsed quickly in absolute terms, I think
you have to start putting some restrictions on the grammar (and then you
are into using other tools).

Thanks



On 8 April 2013 12:03, Daniel Bünzli <daniel.buenzli@erratique.ch> wrote:

> Hello Tom,
>
> Combinator parsers were an obsession of mine a few years ago. I really
> liked the approach but eventually always ended up writing LL(k) parsers
> (xmlm, jsonm) by hand which so far has been the only "technology" that
> allows me to give the best error messages/correction, to handle
> asynchronous IO, and to remain reasonably efficient.
>
> Could you maybe comment on these points:
>
> * What's the error handling strategy ? Is there support for error
> correction ?
> * Is there support for non-blocking parsing (asynchronous IO) ?
>
> Best,
>
> Daniel
>
>
>

[-- Attachment #2: Type: text/html, Size: 2195 bytes --]

Re: [Caml-list] First release of P3: a combinator parser library, and parser generator

[Daniel Bünzli]

Le lundi, 8 avril 2013 à 12:33, Tom Ridge a écrit :
> Yes, I need to do something here. At the moment, there is no real handling of errors, and nothing to support error correction (I'm not completely sure what error correction is).

In hand made parsers you rewind/fast forward your parser state to get it in a state where it may parse sensible things again (e.g. a "toplevel" construct, or the next element in a list-like construct), this can be done for example by closing/ignoring mismatched parentheses etc. Essentially this means discarding part of the input or introducing tokens not present in the input.

While this may result in wrong error reports, you always end with a complete (albeit broken from the user's intent) parse tree. The advantage is that in certain cases you can report more than one syntax error during parsing (since this tends to result in cascading errors you usually set an upper error reporting bound).  

With the combinator approach, see for example [1,2] (I don't know if there were further developments in that area, these were the papers I was reading at the time).

Best,

Daniel

[1]
Swierstra, S.D. (2001).  
Combinator Parsers: From Toys to Tools.  
In G. Hutton (Ed.),  
Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers.  


[2]
Hughes, R.J.M. & Swierstra, S.D. (2003).  
Polish Parsers, Step by Step.  
In
Eighth ACM Sigplan International Conference on Functional Programming
(pp. 239-248). New York: ACM Press.