Hi Alex: I think a PEG grammar should not match this as (a|b)+ since the first choice excludes the second so a prefix a+ will be matched, and stop when seeing a b. I just tried in out on my implementation of left recursion and it acted as I expected.
But when I changed to a first longest choice A|B instead of the PEG A/B first ordered choice, then it matches (a|b)+ as expected for a CFG. I am a little surprised, I expected it would require a full fledged CFG choice to chase down every match, but I need to think about it a bit more.... I don't find left recursion intuitive despite playing with it for years (but some others seem to have better intuition). I don't think its a very good idea for grammar language specifications. I would be keen to talk to you about examples of strange behaviour. I have some too, including a tricky grammar example that was contributed to an earlier discussion by another PEG member (sorry I forget who, but I will dig it out). Cheers, Peter. On Fri, Nov 12, 2010 at 12:33 PM, Repain Alex <alex.rep...@gmail.com> wrote: > 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 > >
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
