Re: Res: lpeg and left recursion

[Roberto Ierusalimschy <roberto@...>]

> [...]  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.

-- Roberto