Categories: parsing

Parsing

Introduction

I have been interested in various aspects of parsing since 2009. My research is particularly focused on parsing general context-free grammars, using combinator parsers. I have published several papers, formalized various proofs about parsers in the HOL4 theorem prover, and produced quite a few OCaml implementations to try out various ideas:

P1, P3, E3 and P4 can all be obtained from github.

P1

P1 is a combinator parsing library for all CFGs. The implementation is based on the verified parsing work (see below).

P3

New versions of P3 are now available from github at https://github.com/tomjridge/p3. At the moment the documentation is on the github wiki for P3 at https://github.com/tomjridge/p3/wiki/P3.

The best documentation for P3 internals is the extended version of the following paper: Tom Ridge. Simple, efficient, sound and complete combinator parsing for all context-free grammars, using an oracle. In Proceedings of SLE 2014. ridge14sle.pdf extended version.

E3

E3 is available from github at https://github.com/tomjridge/e3. The examples should give some guidance on usage.

P4

P4 is available from github at https://github.com/tomjridge/p4, but there is no documentation at the moment.

P5_scala

P5 is a version of P4 for Scala, available at https://github.com/tomjridge/p5_scala. Currently not in a very polished state.

Example grammars

Some examples are at https://github.com/tomjridge/example_grammars/ ; see the blog post

Verified parsing

This work produced a verified, sound and complete approach to combinator parsing. This introduced the idea of "good parse trees". The problem with this approach is that it is too inefficient with left-recursive grammars. There is a post describing verified parsing here.



Related articles:

  • 2017-09-17 Two new OCaml libraries: P0 and tjr-csv
  • 2016-02-19 Tree-structured text
  • 2016-02-09 Simple implementation of an Earley-like parsing algorithm
  • 2015-06-26 P5 scala parsing library
  • 2014-12-19 Parsing the IMAP protocol
  • 2014-12-04 Parsing examples
  • 2014-11-21 Talk on parsing at the University of Sussex
  • 2014-09-26 P1 combinator parsing library for OCaml
  • 2014-09-26 E3 earley parser library for OCaml
  • 2014-09-18 SLE 2014 conference, and Parsing at SLE workshop, slides
  • 2014-09-07 ICFP 2014, OCaml workshop, slides and video
  • 2014-07-11 P3 paper accepted for SLE 2014
  • 2014-04-15 New release of P3 code on github
  • 2014-03-02 New release of P3 code on github
  • 2013-12-16 New release of P3 code on github
  • 2013-12-03 Implementing algorithms efficiently
  • 2013-11-08 Talk on parsing and P3 given at Cambridge
  • 2011-12-01 Verified parsing