search

mjackson / citrus

Parsing Expressions for Ruby
http://mjackson.github.io/citrus
405 stars 28 forks source link

Indirect Left Recursion #8

Open yfeldblum opened 13 years ago

yfeldblum commented 13 years ago

Very cool.

Does this implementation support indirect left recursion? There is a paper on implementing indirect left recursion in a packrat parser at:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.7466&rep=rep1&type=pdf

mjackson commented 13 years ago

Citrus doesn't currently support left recursion, but there's no reason it couldn't given the research that you linked to. In fact, I recently refactored both of Citrus' scanner classes (Citrus::Input and Citrus::MemoizedInput) to use an apply_rule method that looks very similar to the Apply-Rule procedure mentioned in the paper. Should just be a matter of detecting when rules are left recurring and reacting appropriately. This could be added into MemoizedInput to prevent those who don't need support for left recursion from experiencing a decrease in performance.