> > I did not find a solution that worked as users of TatSu (previously Grako) > expected.
Could you precise how that would be? Nicolas LAURENT On 14 May 2017 at 05:08, Juancarlo Añez <apal...@gmail.com> wrote: > 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
