On Thu, Oct 27, 2016 at 8:02 PM, Juancarlo Añez <apal...@gmail.com> wrote: > > On Thu, Oct 27, 2016 at 11:48 AM, Sérgio Medeiros <sqmedei...@gmail.com> > wrote: >> >> >> This approach may be easier than try to get a PEG without left-recursive >> rules directly from a left-recursive CFG. >> >> Either way, I think you have a tough task :-) > > > Actually, I see a light at the end of the tunnel... > > This is the algorithm for elimination in direct left recursion in a CFG: > > A = A alfa | beta > _____________ > > A = beta A' > > A' = alfa A' | eps > > > When the target grammar is PEG, the above translates to: > > A = beta (alfa)* > > > Somehow adding the above to your algorithm would require some sort of rule > rewriting, but it would remove the left recursion being bound by the number > of choices, and would probably result in implementations much simpler than > those of Warth's.
Just to confirm, your approach would be: 1. Given a CFG G, first you would eliminate direct left recursion and obtain G' 2. Then you would use the approach described in https://arxiv.org/abs/1304.3177 to convert G' to an equivalent PEG P This works for some grammars, but not for all, because LL(k) is a proper subset of LR(k): https://en.wikipedia.org/wiki/LR_parser Anyway, this approach may fit your users' needs. >> In case the semantics gives a result, but the user was expecting >> a different parsing tree, then I think it would be preferable to say >> that the semantics does not give the expected result. >> >> Nonetheless, the semantics allows the user to change the precedence >> of the operators, and then get the desired associativity. > > > I understand (there's no misunderstanding). Do you understand my case with > my tool's users? Sure, your users can use "fail" to express that the parser did not produce the expected tree. However, in this forum I think it is better not to use "fail" to mean this. Sorry in case I am being too meticulous. Cheers, -- Sérgio
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
