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

[Eli Zaretskii <eliz@gnu.org>]

> Date: Thu, 10 Nov 2022 06:25:55 +0100
> From: <tomas@tuxteam.de>
> 
> > Would someone like to tell me in 10 lines what job peg.el does?
> 
> PEG (Parsing Expression Grammars [1]) is a grammar notation which can
> be automatically translated into a parser (think regular expressions).

The reference [1] was probably meant to be

  https://en.wikipedia.org/wiki/Parsing_expression_grammar

or somesuch

> The notation is actually similar to that of regexps.

I believe you meant "similar to regular expressions in rx form"?

> The main difference
> is that the "alternative" operator is an "ordered" choice instead of an
> ambiguous choice. To compensate for this, the notation provides for a
> (potential) lookahead mechanism, which, in the naive implementation would
> lead to exponential running time in the worst case. The canonical
> implementation (nicknamed "packrat") addresses that by memoizing.
> 
> Basically they can do what a recursive descent parser can, are thus
> slightly more powerful than regexps. They lead to nice little grammars,
> but they do take some practice to be useful.

I think an example from peg.el will clarify the issue:

  ;; This file implements the macros `define-peg-rule', `with-peg-rules', and
  ;; `peg-parse' which parses the current buffer according to a PEG.
  ;; E.g. we can match integers with:
  ;;
  ;;     (with-peg-rules
  ;;         ((number sign digit (* digit))
  ;;          (sign   (or "+" "-" ""))
  ;;          (digit  [0-9]))
  ;;       (peg-run (peg number)))
  ;; or
  ;;     (define-peg-rule digit ()
  ;;       [0-9])
  ;;     (peg-parse (number sign digit (* digit))
  ;;                (sign   (or "+" "-" "")))

HTH