On Fri, Oct 28, 2016 at 9:44 AM, Juancarlo Añez <apal...@gmail.com> wrote:
>
> On Fri, Oct 28, 2016 at 8:05 AM, Sérgio Medeiros <sqmedei...@gmail.com>
> wrote:
>>
>> 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.
>
>
> The target grammar language would be PEG.
>
> Isn't PEG > CFG an open question?
Yes, it is an open question.
Sorry, I was not clear, let me try again.
In case your approach is:
1. Given an LR(k) CFG G, first eliminate direct left recursion and
obtain an LR(k) CFG G'
2. Then adapt the approach described in https://arxiv.org/abs/1304.3177
to convert G' to an equivalent PEG P
This would be approach A, and your main work would be to adapt
the conversion from strong-LL(k) grammars into equivalent PEGs.
In case your approach is:
1. Given an LR(k) CFG G, first eliminate direct left recursion and
obtain an LR(k) CFG G'
2. Convert G' into an equivalent LL(k) CFG G''
3. Then use the approach described in https://arxiv.org/abs/1304.3177
to convert G'' to an equivalent PEG P
This would be approach B, and my point is that for some LR(k) CFGs
there are no equivalent LL(k) CFGs.
However, maybe your users write LR CFGs that you can almost
always convert to equivalent LL CFGs.
Cheers,
--
Sérgio
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
