From: <tomas@tuxteam.de>
To: emacs-devel@gnu.org
Subject: Re: Make peg.el a built-in library?
Date: Tue, 28 Sep 2021 10:09:02 +0200 [thread overview]
Message-ID: <20210928080902.GC14380@tuxteam.de> (raw)
In-Reply-To: <87sfxp4ard.fsf@ericabrahamsen.net>
[-- Attachment #1: Type: text/plain, Size: 1269 bytes --]
On Mon, Sep 27, 2021 at 08:52:38PM -0700, Eric Abrahamsen wrote:
>
> On 09/27/21 18:34 PM, Richard Stallman wrote:
> > [[[ To any NSA and FBI agents reading my email: please consider ]]]
> > [[[ whether defending the US Constitution against all enemies, ]]]
> > [[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> >
> > What is a PEG?
>
> A Parsing Expression Grammar:
> https://en.wikipedia.org/wiki/Parsing_expression_grammar
>
> Basically a way of composing a parser out of smaller regexp-like
> expressions. They can be very useful in a wide variety of situations.
In the Chomsky hierarchy, they live in some funny place between
regular (Type-3) and context free (Type-2). They are strictly
more powerful than regular grammars (but can eat memory for
breakfast [1], but (quoting the Wikipedia ref above:
"It is an open problem to give a concrete example of a
context-free language which cannot be recognized by a
parsing expression grammar."
I don't know at the moment whether there is a (non-constructive)
proof that CFGs be strictly more expressive than PEGs?
Cheers
[1] Memory has become significantly cheaper since Thompson, this
might have a practical significance or not ;-)
- t
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]
next prev parent reply other threads:[~2021-09-28 8:09 UTC|newest]
Thread overview: 100+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-25 18:52 Make peg.el a built-in library? Eric Abrahamsen
2021-08-26 6:17 ` Eli Zaretskii
2021-08-26 15:34 ` Eric Abrahamsen
2021-09-09 4:36 ` Eric Abrahamsen
2021-09-19 15:25 ` Eric Abrahamsen
2021-09-30 19:44 ` Stefan Monnier
2021-09-30 20:34 ` Adam Porter
2021-10-01 8:14 ` Augusto Stoffel
2021-10-01 18:05 ` Stefan Monnier
2021-10-01 18:40 ` Eric Abrahamsen
2021-10-02 3:57 ` Stefan Monnier
2021-10-02 7:32 ` Adam Porter
2021-10-02 14:45 ` Stefan Monnier
2021-10-02 15:13 ` Adam Porter
2021-08-26 17:02 ` Adam Porter
2021-08-26 17:25 ` Eric Abrahamsen
2021-08-27 3:17 ` Eric Abrahamsen
2021-08-27 6:41 ` Helmut Eller
2021-08-27 16:57 ` Eric Abrahamsen
2021-09-26 10:59 ` Augusto Stoffel
2021-09-26 15:06 ` Eric Abrahamsen
2021-09-26 18:36 ` Augusto Stoffel
2021-09-27 16:18 ` Eric Abrahamsen
2021-09-27 22:34 ` Richard Stallman
2021-09-28 3:52 ` Eric Abrahamsen
2021-09-28 8:09 ` tomas [this message]
2021-09-28 9:32 ` Helmut Eller
2021-09-28 10:45 ` tomas
2021-09-28 15:24 ` Augusto Stoffel
2021-09-30 6:04 ` Richard Stallman
2021-10-01 3:27 ` Eric Abrahamsen
2021-10-09 1:31 ` Michael Heerdegen
2021-10-09 5:28 ` Michael Heerdegen
2021-10-09 8:12 ` Helmut Eller
2021-10-09 12:52 ` Stefan Monnier
2021-10-10 5:49 ` Helmut Eller
2021-10-14 10:25 ` Michael Heerdegen
2021-10-09 12:54 ` Stefan Monnier
2021-10-09 16:47 ` Eric Abrahamsen
2021-10-10 4:20 ` Michael Heerdegen
2021-10-10 21:40 ` Eric Abrahamsen
2021-10-13 2:58 ` Michael Heerdegen
2021-10-09 16:49 ` Eric Abrahamsen
2021-10-10 3:43 ` Stefan Monnier
2021-10-10 4:46 ` Michael Heerdegen
2021-10-10 5:58 ` Helmut Eller
2021-10-10 13:56 ` Stefan Monnier
2021-10-22 16:33 ` Michael Heerdegen
2021-10-31 23:43 ` Michael Heerdegen
2021-11-15 23:16 ` Michael Heerdegen
2022-11-07 3:33 ` Ihor Radchenko
2022-11-07 19:46 ` Eric Abrahamsen
2022-11-08 6:57 ` Helmut Eller
2022-11-08 8:51 ` Ihor Radchenko
2022-11-10 4:04 ` Richard Stallman
2022-11-10 5:25 ` tomas
2022-11-10 8:15 ` Eli Zaretskii
2022-11-10 8:29 ` tomas
2022-11-11 4:36 ` Richard Stallman
2022-11-08 8:47 ` Ihor Radchenko
2022-11-08 16:18 ` Eric Abrahamsen
2022-11-08 19:08 ` tomas
2022-11-08 19:42 ` Eric Abrahamsen
2022-11-16 4:27 ` [PATCH] " Eric Abrahamsen
2022-11-16 5:07 ` tomas
2022-11-16 5:39 ` Eric Abrahamsen
2022-11-16 15:53 ` tomas
2022-11-16 6:24 ` Ihor Radchenko
2022-11-16 18:15 ` Eric Abrahamsen
2022-11-17 12:21 ` Ihor Radchenko
2022-11-27 1:46 ` Eric Abrahamsen
2022-11-27 8:57 ` Eli Zaretskii
2022-11-28 1:09 ` Eric Abrahamsen
2022-11-28 12:16 ` Eli Zaretskii
2023-09-25 1:30 ` Eric Abrahamsen
2023-09-25 2:27 ` Adam Porter
2023-09-25 13:00 ` Alexander Adolf
2024-03-24 14:19 ` Ihor Radchenko
2024-03-24 15:32 ` Eli Zaretskii
2024-03-25 1:45 ` Eric Abrahamsen
2023-01-11 7:39 ` Michael Heerdegen
2023-01-11 8:04 ` Ihor Radchenko
2023-01-11 11:01 ` Michael Heerdegen
2023-01-11 11:32 ` tomas
2023-02-05 12:10 ` Ihor Radchenko
2023-02-05 15:41 ` Eduardo Ochs
2023-02-05 15:45 ` Ihor Radchenko
2023-02-05 16:19 ` Eduardo Ochs
2023-02-05 16:50 ` Ihor Radchenko
2023-02-09 5:44 ` Jean Louis
2023-02-06 0:33 ` Michael Heerdegen
2022-11-08 14:01 ` Stefan Monnier
2022-11-08 14:42 ` tomas
2022-11-08 15:08 ` Visuwesh
2022-11-08 16:29 ` Juanma Barranquero
2022-12-02 20:20 ` Augusto Stoffel
2022-11-08 16:10 ` Eric Abrahamsen
2022-11-08 18:59 ` tomas
2022-11-08 19:42 ` Eric Abrahamsen
2022-11-08 22:03 ` Tim Cross
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210928080902.GC14380@tuxteam.de \
--to=tomas@tuxteam.de \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.