About packrat parsing... At my office I implemented Warth, Douglas and Millstein's left-recursion algorithm, and ran into two things. First, the algorithm desc

About packrat parsing... At my office I implemented Warth, Douglas and Millstein's left-recursion algorithm, and ran into two things. First, the algorithm described in the paper is kind of a mess, as the authors admit. Second, it doesn't actually work as advertised, as the OP discovered. What become a simple implementation taking a few days turned into many weeks of trial and error, because with each change I naively thought I was almost there. Now I know better than to go around trusting strangers with algorithmic candy. The idea is to introduce a notion of what left-recursions are allowed and which ones aren't. Say we have a rule R which matched input M. Call M the "match". Say M has a sub-match, M' which also depends on rule R. Then M is allowed if and only if the submatch M' is in a certain sense smaller than M--either it is smaller in size, or M' and M depend on the same choice rule, except M-prime's choice is ordered after M's. In implementation, we take a "growing the seed" approach described in Warth et al, but with the ability to track multiple left-recursion points, and the left-recursion seed parses that every match is dependent on. For a pathological grammar this may end up exponentially slow. I'm willing to bet this curtailment process is essentially the same as the process described in Frost, Hafiz and Callaghan's paper on left-recursive parser combinators[1], but I haven't looked too closely at it. I discovered Frost et al's paper only after I was done. I may have done a bad job of explaining this, but our unit tests have some pretty arbitrary grammars like S ::= <A>/<B> A ::= <A> ‘a’ / <B> / ‘a’ B ::= <B> ‘b’ / <A> / ‘b’ and our parser handles these admirably and with excellent greed. I've been wondering what to do with this information; I drafted an e-mail to Warth/Douglass/Millstein but haven't sent it. [1] http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBoQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.89.2132%26rep%3Drep1%26type%3Dpdf&rct=j&q=Parser%20Combinators%20for%20Ambiguous%20Left-Recursive%20Grammars&ei=H4B_TaKPB8fegQeRi42TCA&usg=AFQjCNHufySC9dCnMyMT_jwv4kyGkRPAyA&sig2=V84mqs_KHEtky4m8E6_CkA&cad=rja http://www.google.com/url?sa=t&source=web&cd=1&v...