[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Res: lpeg and left recursion
- From: Roberto Ierusalimschy <roberto@...>
- Date: Tue, 2 Mar 2010 07:07:59 -0300
> [...] As for the argument that it doesn't
> define the semantics, what would those have to be exactly? From what
> I can tell, the modifications to the matching function are internal to
> the system and do not produce any semantic differences at the PEG
> level since it's possible to transform a left recursive PEG into a non
> left recursive PEG but it takes some serious contortions to do so that
> inhibit their use. Am I wrong about this?
Yes. In CFG, left recursion has a clear meaning, but top-down parsers
cannot implement that meaning. This is a limitation of the top-down
technique, not of CFG. But a PEG is not a CFG. In PEGs, left recursion
has no meaning; this is not an implementation problem. So, you cannot
transform a left recursion into a non-left recursion keeping its
meaning, because there is no meaning to keep.
What we tend to do is to see a left-recursive PEG as if it were a
left-recursive CFG (which means something) and expect the same
semantics. But it is hard to say precisely what this "same semantics"
should be, given that everything else has different semantics.