Date: 2016-02-09
Categories: news; parsing; p3; software
Simple implementation of an Earley-like parsing algorithm
I have written a simple implementation of an Earley-like parsing algorithm in OCaml. This is intended to be the simplest possible Earley-like code for which one can prove correctness. I think it also makes the structure of Earley's algorithm clear, and the complexity argument also clear.
The code is on github here, and the documentation (with a link to an html version of the code) is here.
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-07-02 Funded PhD places
- 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-09-06 ICFP most influential paper from 10 years ago
- 2017-03-16 tjr-btree: a CoW B-tree library in OCaml
- 2016-11-17 OCaml string functions
- 2016-06-05 Do not buy TP-Link products
- 2016-05-27 Visit to Cambridge, for REMS workshop
- 2016-04-22 Visit to Denmark, to see Joergen Villadsen
- 2016-02-19 Tree-structured text
- 2016-02-09 Simple implementation of an Earley-like parsing algorithm
- 2016-01-27 Talk at York University
- 2016-01-06 Stephanie Heintz PhD viva
- 2015-10-05 SibylFS presentation at SOSP'15
- 2015-09-28 SibylFS SOSP poster
- 2015-09-21 SibylFS presentation to Industrial Advisory Board
- 2015-06-28 SOSP 2015 paper acceptance for SibylFS
- 2015-06-26 P5 scala parsing library
- 2015-04-21 REMS Cambridge talk on SibylFS
- 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-09-07 ICFP 2014, Lem talk
- 2014-07-11 P3 paper accepted for SLE 2014
- 2014-07-11 Lem paper accepted to ICFP 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-13 PhD student course on logic, proof and mechanized theorem proving
- 2013-11-13 New website design
- 2013-11-13 Engineer position
- 2013-11-12 Netsem TCP/IP specification on github
- 2013-11-08 Talk on parsing and P3 given at Cambridge
- 2013-11-01 Funded PhD positions
- 2013-04-01 PhD position funded by Microsoft Research
- 2013-02-01 EPSRC grant funded
- 2011-12-01 Verified parsing