2010/11/12 Peter Cashin <cashin.pe...@gmail.com> > 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. > > That seems rather unintuitive to me ... For the grammar I provided, if you consider the input "aba", you wouldn't match the 'b' in it, since the first match of an 'a' restricts the ordered choice ? Then what about "bab" ? Should it be parsed completely ? 'B' being the second choice for rule S, What should the parser do when he entered a B evaluation ? restricts the choice to S <- B only, or still allow for S <- A / B ?
> 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). > I would be interested in seeing this example of tricky grammar. My main goal here is to understand what vision you guys have about left-recursion and the ordered choice thing. > > > 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
