Packrat Parsers Can Support Left Recursion

ACM SIGPLAN 2008 Workshop on Partial Evaluation and Program Manipulation (PEPM 2008), San Francisco, CA, January 7-8, 2008.
Alessandro Warth, James R. Douglass, Todd Millstein
Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser implementations makes them difficult to use for a large class of grammars (Java's, for example). This paper presents a modification to the memoization mechanism used by packrat parser implementations that makes it possible for them to support (even indirectly or mutually) left-recursive rules. While it is possible for a packrat parser with our modification to yield super-linear parse times for some left-recursive grammars, our experiments show that this is not the case for typical uses of left recursion.