No,
It's another way. And it can handle with rules like:
S -> (a)* a
as you can see, this rule is not recursive, but it will fails with the string
'a'
________________________________
From: Alex Repain <alex.rep...@gmail.com>
To: Yury Euceda <yuryeuc...@yahoo.com>
Cc: Sérgio Medeiros <tamp...@yahoo.com>; Bryan Ford <bryan.f...@yale.edu>; peg
lista <peg@lists.csail.mit.edu>
Sent: Monday, October 10, 2011 4:01 PM
Subject: Re: [PEG] Fun with left recursion
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
