Hi PEG list, As an intern, I worked this summer in a japanese laboratory, on left-recursion support for packrat parsers. One of the questions we had a hard time dealing with was the following :
Since the original definition of PEG grammars doesn't take in account the grammars with left-recursive rules (directly or indirectly), what is the behaviour we expect from a PEG parser, when dealing with those grammars ? The first and intuitive solution is to avoid these rules, but a lot of work has been produced on the subject, including Wrath *et al.*'s paper* [1]*(which might be the most acknowledged), and today it seems we want to be able to handle left-recursive grammars. But this can reveal itself quite tricky. Take for instance the following grammar : S <- A | B A <- S a | a B <- S b | b which is an indirectly left-recursive grammar. In a CFG context, this grammar would represent the langage (a|b)+ . What about this in the PEG context ? My guess is that, despites the fact that PEGs impose the concept of ordered choice, the expected behaviour of this grammar is to recognize the very same (a|b)+ langage, through a PEG parser - say for instance a packrat parser. Still, I would like to be sure of it, and if anybody has a CLEAR idea of what SHOULD happen with a correct support for left-recursion, I'm eager to hear about it. Is there only a real convention for a correct behaviour ? My actual situation is the following : during my internship this summer, I started to doubt about the capacity for Wrath et al.'s algorithm to handle every type of left-recursive grammars. For instance, the above grammar, when passed to a Packrat parser with Wrath et al.'s enhancement, doesn't recognize (a|b)+, but only a subset of this langage. That is not the behaviour I expected, and thus I started working on a new algorithm able to take into account complex left-recursion cases. Yet, if my vision of how a parser behaves "correctly" is altered in some way, my work here could be just good for the trash bin. Thanks for your help. Alex P.S. : if someone is interested in my work, or in examples of strange behaviour with Wrath et al.'s, I can provide them, one-to-one (to avoid attached files on the mailing lists). *[1]* *Packrat Parsers Can Support Left Recursion*, Alessandro Warth, James R. Douglass, and Todd Millstein (2008)
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
