Hello Nicolas, PEG + left-recursion was "solved" long ago. >
I did not find a solution that worked as users of TatSu (previously Grako) expected. They expected left recursive rules to behave like they do in LR parsers, with the rule order and backtracking semantics of PEG. > I suppose that by "solved" you mean that an implementation for it exists > (to be > clear, this too has been the case for a while). > As above. > I seem to recall that it is proven that there are PEG grammars that have > no CFG > equivalent (to be verified), so the proposition would be PEG+LEFT > CFG. > I haven't seen that mentioned in the papers I've read. > **If** the proposition PEG+LEFT > CFG is true, then of course a proof is > possible. But my point is that there isn't any new element on how to > conduct > this proof. > > I thought about it for awhile, my "naive" line of thought was providing an > algorithm that converts every CFG into a PEG. I'm not optimistic about the > prospects of this approach, but if you you want to try it, the difficulty > is to > encode the backtracking pattern of CFG in PEG (CFGs may backtrack much more > I thought about looking for a CFG that generates a language that cannot be recognized by a PEG+LEFT. Intuitively, I don't think there's one, because a Grako grammar was able to parse SAG Natural without tricks, and Natural is not CF. That instance would work the other way around: there's a PEG language that is not CF. -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
