2011/10/9 Peter Goodman <peter.good...@gmail.com> > Well, using code that I haven't touched in ages and a completely > experimental approach, what I get for http://codepad.org/EvnKQm98 is: > > case 1: doesn't do anything, doesn't loop > case 2: behaves like S -> a > case 3: segfault.. hrmmmm. >
For case 3, I would say "S -> T / a" can be replaced by "S -> S / &a / a" , succeeds on &a. First try will succeed on &a, the result is stored for S in a second try, in which, depending on the behaviour of your parser will give : 1. success on "a" if your left-recursion growing scheme seeks the longest match (which is somehow opposed to the first match operator... although the latter is not specified for left-recursion) 2. infinite loop if your left-recursion growing scheme seeks first match in the rules. "&a" consuming no input, the "grow-a-seed" principe developed in Warth et al. will probably run into an infinite loop (not saying it is the only left-recursion scheme out there, but that's the one I know). 3. success on "a" if you adopt a "first longer match" scheme, where growing the seed can only be obtained through input consumption. That is, if a left-recursion growth iteration consumes no input, it is illegal. I tried to study that stuff in an unpublished technical report one year ago, which was based on A. Warth et al.'s work, and came up with that 3rd behaviour as a (not perfect) compromise between PEGs specifications and full left-recursion support. case 4: reads in aaa. > > This is using http://projects.ioreader.com/cp/ > > Best Regards, > > Peter Goodman, > http://www.petergoodman.me > 65 High Park Ave. APT 413, > Toronto, Ontario > M6P 2R7 > > > > On Sun, Oct 9, 2011 at 4:39 PM, Bryan Ford <bryan.f...@yale.edu> wrote: > > Left recursion in PEGs indeed seems like an interesting can of worms. > For those interested, I'm wondering how a few example grammars behave under > your preferred left-recursive parsing technique, and how you think they > should behave. > > > > First, a trivially evil left-recursive grammar: > > > > S <- S > > > > For example, does your parser detect and reject this somehow, or does it > behave the same as 'S <- f'? (I hope it doesn't result in an infinite loop > at runtime anyway. :) ) > > > > Now a grammar that's weird, not necessarily evil, in a slightly more > subtle way: > > > > S <- S / a > > > > Does this behave the same as 'S <- a', or do something else? How should > it behave? > > > > Cranking up the evilness factor one notch with a mutually left-recursive > grammar… > > > > S <- T / a > > T <- S / &a > > > > Given the input string "a", does this behave the same as 'S <- a' > (succeeding and consuming) or the same as 'S <- &a' (succeeding but > consuming no input)? Do S and T behave the same way or differently? Should > they? > > > > Now, another grammar that's not necessarily evil but strange in a > slightly different way: > > > > S <- Saa / a / > > > > Given the input string 'aaaa', for example, does/should this grammar > consume just 3 or all 4 a's, or does it do something else? What should it > do? > > > > Cheers, > > Bryan > > _______________________________________________ > > 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 > -- *Alex REPAIN* ENSEIRB-MATMECA - student TECHNICOLOR R&D - intern BORDEAUX I - master's student SCALA - enthusiast
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
