2011/10/10 Yury Euceda <yuryeuc...@yahoo.com> > Hello! > > I developed a PEG that supports left (direct indirect hidden) recursion, > right recursion, both (left and right) recursion, generating a linear > algorithm for these tasks. > Capable of assist in FRONT END compiler development (syntactical, lexical, > semantical analysis) > And you're going to be able to generate morphing computer algorithms like > katadhin. > > There are many powerful characteristics and those issues below are covered > and many more for example, rules like: > > S -> S a | S S | S S S | b > > with linear parsing time!!!!! > > Out of curiosity, is it using packrat parsing-style memoization to guarantee such linear time ?
Somebody knows someone who's interested in this matter? > Regarding the left recursion support, I think the main problem is that it is unspecified up to now, how PEGs should behave when supporting left-recursion. If your parser is good for practical use, and that the way left-recursion behaves is widely accepted, I'd say a lot of us will be interested. ------------------------------ *From:* Sérgio Medeiros <tamp...@yahoo.com> *To:* Bryan Ford <bryan.f...@yale.edu>; peg lista <peg@lists.csail.mit.edu> *Sent:* Monday, October 10, 2011 11:24 AM *Subject:* Re: [PEG] Fun with left recursion > 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. :) ) The same as 'S <- f'. > 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? The same as 'S <- a'. > 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? The same as 'S <- &a'. > 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? It consumes just 3 a's. The general behavior is like this: * If the input has 2n a's, then 2n-1 a's are matched. * If the input has 2n+1 a's, then 2n+1 a's are matched. Sérgio _______________________________________________ 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
