[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.
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
- Re: Make peg.el a built-in library?, (continued)
- Re: Make peg.el a built-in library?, Eric Abrahamsen, 2021/09/19
- Re: Make peg.el a built-in library?, Stefan Monnier, 2021/09/30
- Re: Make peg.el a built-in library?, Augusto Stoffel, 2021/09/26
- Re: Make peg.el a built-in library?, Richard Stallman, 2021/09/27
- Re: Make peg.el a built-in library?, Augusto Stoffel, 2021/09/28
- Re: Make peg.el a built-in library?, Richard Stallman, 2021/09/30
- Re: Make peg.el a built-in library?, Eric Abrahamsen, 2021/09/30