How about this one. L = L B C | A B | L C | A should it be ((A B) C) or ((A) B C)
I write nondeterministic packrat parser(rewrite LR/RR to iteration, rest of recursion must be surrounded by nested) If I add special case rewriting A=A to A=fail it should be: 1. S=(fail )* fails. 2. S=(fail | a break)* Same as S = a 3. S=(S | &a) | a = (fail| &a break | a break)* First time it suceeds not consuming then suceeeds consuming 4. S= (aa | a break | break)* Consumes aaaa aaa aa a I rejected Warth's seed growing long ago as for indirect left recursion it gave algorithm that is both wrong and more complicated than standard rewriting of indirect LR to direct LR. Moreover for direct LR seed growing has issues like Not quite left recursion S=(a|) S b | c Does not match acbb And not considering that semantic predicates can fail S = ?(a!=1) S a | S b !(a=1) |?(a!=1) x | x a a with xaabca On Sun, Oct 09, 2011 at 04:39:09PM -0400, Bryan Ford 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 -- fractal radiation jamming the backbone _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
