[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Helmut Eller
Subject: Re: Make peg.el a built-in library?
Date: Tue, 28 Sep 2021 11:32:58 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux)

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.


[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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]