Hi Alex: I am also interested in how others think about this, and I have been pleased to see the comments and references that you have got from Orlando Hill and Terrence Parr.
Many people like me want to write a grammar, and read other peoples grammar specs, with a simple interpretation, that can be easily implemented with a parser generator, or directly parsed with a grammar interpreter. Thats not the same thing at all as the intuition that some of the academic theory people can bring to bear -- I admire their work, but its beyond many of us that still find grammar specifications amazingly good value, and fun. Look at the IEFT ABNF grammar specs -- lots of great simple specifications, all of which seem to fit with a PEG implementation, and no left recursion that I have seen. Terrence makes a nice point on a good use of left recursion (I agree), and others have made the point that its sometimes harder than might be expected to manually remove left recursion. So its nice to have, but often its better to write the grammar rules so as to avoid it. I've added a few comments in reply to your response below... Cheers, Peter. On Sat, Nov 13, 2010 at 11:13 AM, Repain Alex <alex.rep...@gmail.com> wrote: > > > 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 ? > > I can't say its intuitive, but its the "prefix capture" nature of PEG first ordered choice: s=a/ab wont match ab. > > 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 ? > > Good question: my implementation does parse "bab" etc -- so the looping to build the left recursion turns out to implement a more expressive language, but its also more complex and costly that the simple PEG recursive descent.... I'm not sure it should work this way, but it does. I find I like to use a longest match choice operator rather than the PEG first choice operator -- this allow you to not care about the order of the choices and the "prefix capture" problem goes away. Its not too expensive vrs the PEG choice as long as the parser implementation fails fast with low cost on choices that are mutually exclusive, which in grammars I like is almost all the time. > > >> 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. > >> I see one of the examples in the references Orlando and Terrence gave... > >> > >> > 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
