Parsing Tools

Since around 2004, when I worked on extensible syntax and extensible parsers as part of a customer project, I’ve been interested in different approaches to parsing and pattern matching. My experimental programming language work has often been the testbed for the parsing libraries I’ve built as a result.

(Extensible) Packrat Parsing

I’ve built a couple of implementations of Bryan Ford’s packrat parsing algorithm: initially a closed implementation in SML, for a customer, and subsequently an open-source implementation in Scheme, for my own projects.


After a couple of years of working with packrat-style systems, I discovered Alessandro Warth’s fascinating work on OMeta, and realised that many of the techniques I’d used to build my packrat-parsing library—particularly the error-handling techniques—could let me build an interesting OMeta implementation as well.

You can find the results here. Currently it runs in MzScheme, but it should be fairly portable, with dependencies only on a handful of commonly-implemented SRFIs. For more information, see the blog post. It’s not as well-documented as my packrat library, but I’m using it successfully in a number of the little-languages I’m experimenting with.