Re: Make peg.el a built-in library?

[Helmut Eller]

On Tue, Sep 28 2021, tomas@tuxteam.de wrote:

> I don't know at the moment whether there is a (non-constructive)
> proof that CFGs be strictly more expressive than PEGs?

You could ask this question on the PEG mailing list [1].

Apparently it has been proven[2] that for every CFG in LL(1) there is a
corresponding PEG.  This is very nice, because in practice we are mostly
interested in grammars that can be parsed efficiently.  Unfortunately,
it seems[3] difficult/impossible to tell (statically) if a given PEG
corresponds to LL(1) or how much backtracking it needs.

Helmut


[1] https://lists.csail.mit.edu/mailman/listinfo/peg
[2] https://arxiv.org/abs/1304.3177
[3] Trying to understand PEG
    Fundamenta Informaticae 157, 4 (2018) 463-475.
    http://www.romanredz.se/papers/FI2017.pdf