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.
[PDF]