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

[Augusto Stoffel <arstoffel@gmail.com>]

On Tue, 28 Sep 2021 at 10:09, <tomas@tuxteam.de> wrote:

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

Perhaps more interesting in practice: a PEG can compute and return a
value as it parses the subject string.  So one can (easily) write a PEG
that recognizes well-formed arithmetic expressions _and_ computes the
value of the arithmetic expression along the way.  Or a PEG that
recognizes email headers and returns those headers as an alist.

Regexps usually only produce substrings of the subject string (in Emacs
regexps can also call Lisp code, but this is not as general.)

[Also note that a PEG defines a parser for a grammar, not just a
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