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.
- Extensible Parsing Systems
- From Stateful Parsing to Transactional Parsing
- The announcement of the code and documentation for the library
- The library itself: http://eighty-twenty.org/~tonyg/Darcs/json-scheme/ (browseable, and a darcs repository)
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.
- The announcement of the library on the OMeta mailing list
- OMeta for Scheme
- The library itself: http://www.eighty-twenty.org/hgwebdir.cgi/ometa-scheme/ (browseable, and a mercurial repository)