Date: 2017-11-14
Categories: ocaml; software; parsing
New OCaml parsing algorithm: tjr_simple_earley
A while ago, I wrote a parsing algorithm loosely based on the ideas behind Earley parsing. The aim was to produce an algorithm that was:
- correct
- fast
- documented
The resulting code and documentation is on github at https://github.com/tomjridge/tjr_simple_earley
The examples in src/bin include the grammar E -> E E E | "1" |
eps, with an input of length 400. This can be parsed in under 3s. As
far as I know, most general-purpose parsers cannot handle anywhere
near this length. For example, Haskell's Happy parser takes two
minutes to handle an input of length 60 (and can't handle much longer
inputs).
Related posts:
- 2020-05-22 A simple MCQ test program, in OCaml, compiled to JavaScript
- 2019-08-30 B-tree random write performance
- 2019-08-21 ML'19 Workshop at ICFP: A key-value store for OCaml
- 2018-07-09 Backup tools
- 2018-06-14 A typed DSL for parsing
- 2018-05-22 First Python program: an Earley parser!
- 2018-02-01 New OCaml library: path resolution
- 2017-11-14 New OCaml parsing algorithm: tjr_simple_earley
- 2017-09-17 Two new OCaml libraries: P0 and tjr-csv
- 2017-03-16 tjr-btree: a CoW B-tree library in OCaml
- 2016-11-17 OCaml string functions
- 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-24 Experience of using Lem
- 2013-11-08 Talk on parsing and P3 given at Cambridge
- 2011-12-01 Verified parsing