nikodemus/esrap — pull request #21 by scymtym (2013-03-19 02:37:35+00:00)
Title: Support left recursive rules with potential performance hit

I implemented the strategy introduced in

> Alessandro Warth, James R. Douglass, Todd Millstein, 2008,
> "Packrat Parsers Can Support Left Recursion".
> http://www.vpri.org/pdf/tr2007002_packrat.pdf

Unfortunately, I'm not completely sure that my implementation is correct. I tested as thoroughly as I could but the algorithm is rather complicated. However, this is probably not as bad as it sounds because existing grammars are not affected by the added code. I did the following things to test the code:
* test cases for direct and indirect left recursion with various input sizes
* examples for left- and right-associative arithmetic expression grammars
* an example reproducing the grammar given as an example in the above paper
the new examples can be found in ``example-left-recursion.lisp``.

Commit message
```
Support left recursive rules with potential performance hit

As described in

Alessandro Warth, James R. Douglass, Todd Millstein, 2008,
"Packrat Parsers Can Support Left Recursion".
http://www.vpri.org/pdf/tr2007002_packrat.pdf

WITH-CACHED-RESULT detects left recursion and (unless signaling an
error has been requested) handles the situation by growing a "seed
parse" via repeated application of the rules involved in the left
recursion.

The new special variable *ERROR-ON-LEFT-RECURSION* switches between
this new behavior and the old behavior of signaling a LEFT-RECURSION
error.

The system version has been bumped from 0.9 to 0.10 and a feature
:ESRAP-CAN-HANDLE-LEFT-RECURSION is pushed onto *FEATURES* when the
system is loaded.

Basic unit tests for direct and indirect left recursion have been
added.

The manual has been extended.

The new file example-left-recursion.lisp contains multiple grammars
which exercise and illustrate the new capability.
```