search

kschiess / parslet

A small PEG based parser library. See the Hacking page in the Wiki as well.
kschiess.github.com/parslet
MIT License
809 stars 95 forks source link

Implement direct left recursion #30

Closed stormbrew closed 13 years ago

stormbrew commented 13 years ago

These changes collectively implement direct left recursion. Note that one side effect is that not as much can be memoized. When all rules were being memoized, it made what in the grammar would have looked like a direct left-recursion into something more like an indirect left-recursion. It's possible that this is because I misunderstood something in either the implementation of parslet or the OMeta algorithm, but I've looked at other PEG parsers and they seem to be much less aggressive about memoization to begin with.

I also have some concern that the implementation I've used for reporting errors is incorrect or undercooked, but I'm not sure if there's an obvious better way that I'm missing.

kschiess commented 13 years ago

Thanks!

I'll read up on the theory and might change the code around a bit, but I will merge this as soon as I can! kaspar

kschiess commented 13 years ago

Hi stormbrew,

Maybe you've seen my post on the mailing list about this - here's a link: http://permalink.gmane.org/gmane.comp.lang.ruby.parslet/3

greetings, kaspar