Hey Juancarlo, PEG + left-recursion was "solved" long ago.
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). 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. **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 "widely" than PEGs). Regards, Nicolas LAURENT On 9 May 2017 at 19:04, Juancarlo Añez <apal...@gmail.com> wrote: > Hello, > > If indeed unbounded left recursion in PEG grammars is solved, it could be > possible analyze the relationship between the PEG+LEFT and CFG sets by > proving something like that there's a PEG+LEFT grammar that parses the same > language as any given CFG. > > Right? > > -- > Juancarlo *Añez* > > _______________________________________________ > 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
