Hello, Paul Sargent implemented Warth et al's left-recursion in Grako[2]. It has been a problem because the algorithm cannot handle any sort of left recursion, and that's what users of Grako expected.
I implemented a version Medeiro et al's[3] algorithm in Grako. I don't know what I did that for, because it should be easy to prove that an algorithm that sets a bound to recursion will fail for certain grammars and inputs. What disappoints me about the papers is that they don't characterize the grammars for which the algorithms do work. Not all left-recursive grammars are LR, and only LR grammars will parse with LR algorithms. Which set of grammars are PEG+Left_Recursion_Alg_X? The need for left-associativity in expressions can be handled in several different ways in a PEG parser, without trying to make a PEG parser parse with left-recursive grammars. Cheers, [1]: http://www.vpri.org/pdf/tr2007002_packrat.pdf [2]: https://bitbucket.org/apalala/grako [3]: http://www.inf.puc-rio.br/~roberto/docs/sblp2012.pdf -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
