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, and
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]