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