Indirect Left Recursion #8

Open
yfeldblum opened this Issue Nov 16, 2010 · 1 comment

Projects

None yet

2 participants

@yfeldblum

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
Owner
mjackson commented Jan 1, 2011

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment