Packrat parser with left recursion

Traditional bottom-up LALR(1) parsers like yacc are both complex to implement and limited in what they can parse. In contrast, top-down packrat parsers (good Wikipedia intro) are simple to write from scratch — you can write a parser in a few dozen lines of code without needing any tool like yacc — and they are just about as powerful.

One remaining issue with packrat parsers is that they don’t natively support left recursion, making it hard to translate yacc-style parsers. However a couple of years ago an interesting paper was published, Packrat Parsers Can Support Left Recursion (PDF) which shows how to modify the memoization to support left recursion.

This really works, but unfortunately the pseudocode used in the paper is obscure and it’s hard to find example code, so I implemented this packrat parser with support for left recursion in OCaml.

Compile with:

$ ocamlfind opt -package extlib -linkpkg \
    testparse.ml -o testparse

and run it like this:

$ cat input
( fun a -> a + 1 ) (a + b)
$ ./testparse < input