[InAnEmergency]

This article does not cite any references (and is from 2010) so I can't tell if the author was aware that packrat parsing can support left recursion (PDF, 2008): http://web.cs.ucla.edu/~todd/research/pepm08.pdf

[hardmath123]

Also worth noting that Earley parsers also support left-recursion without any fancy additions.

http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan...

[wtetzner]

The algorithm in that paper produces incorrect parses for some PEGs: http://tratt.net/laurie/research/publications/papers/tratt__...

[stormbrew]

Also worth noting from this paper is this, which is an underappreciated facet of packrat parsing:

> It should be noted that while Packrat parsing obviously adds an extra layer of complexity over ‘pure’ PEGs, contrary to expectations it often slows parsing down when used blindly for every rule.

Especially these days, and really definitely in a lot of dynamic languages (cfe Ruby), the kind of allocation rate that packrat parsing produces has a significantly negative effect on performance. Applied blindly you're just trading n^2 performance for n^2 memory use, and that may not work out the way you think it should.

[jules]

Actually performance is exponential without memoization, so usually some amount of memoization is essential, but memoizing more rules usually does not help.