search

nikodemus / esrap

OLD REPOSITORY: Please go to:
https://github.com/scymtym/esrap
81 stars 25 forks source link

Support left recursive rules with potential performance hit #21

Closed scymtym closed 10 years ago

scymtym commented 11 years ago

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:

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.
nikodemus commented 11 years ago

Very nice!

I have some quibbles, but they're quibbles, not real issues.

  1. The DECLAIM SPECIAL is not needed.
  2. I think I would prefer the initial default to be to signal an error on left recursion.
  3. I wonder if there could a left-recursive slot in a rule, or similar, so rules could be specified to be explicitly left-recursive -- and explicitly left recursive rules would then never signal an error.
  4. Than I think the error-on-left-recursion might turn into on-left-recursion with possible values :error, :warn, and nil.

None of these are show stoppers, though. If you want to call this done, I can merge it as is.

scymtym commented 11 years ago

As with #18, an improved version can be found in scymtym/esrap@master and I failed to update this pull request. I suggest to not immediately merge either version, though:

  1. This would allow me to integrate the improvements you suggest
  2. Since writing the pull request, I discovered limitations I would like and have started to address (not sure whether I can resolve everything since even the paper does not address some of the limitations, as far as I can tell)