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

[Eric Abrahamsen]

Ihor Radchenko <yantar92@posteo.net> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> Okay, here's a first stab. I read the paper, and understood about half
>> of it, which seemed like enough. It was interesting to see that the
>> paper explicitly calls out the exact greedy-matching behavior I'd
>> encountered.
>
> Thanks!

And thanks for the review! I'll add in all your simpler notes; more
responses below.

>> +  Emacs Lisp provide several tools for parsing and matching text, from
>
> provides
>
>> +regular expressions (@pxref{Regular Expressions}) to full @acronym{LL}
>> +grammar parsers (@pxref{Top,, Bovine parser development, bovine}).
>> +@dfn{Parsing Expression Grammars} (@acronym{PEG}) are another approach
>> +to text parsing that offer more structure and composibility than
>> +regular expressions, but less complexity than context-free grammars.
>> +
>> +A @acronym{PEG} parser is defined as a list of named rules, each of
>> +which match text patterns, and/or contain references to other rules.
>> +Parsing is initiated with the function @code{peg-run} or the macro
>> +@code{peg-parse}, and parses text after point in the current buffer,
>> +using a given set of rules.
>> +
>> +The definition of each rule is referred to as a @dfn{parsing
>> +expression} (@acronym{PEX}), and can consist of a literal string, a
>> +regexp-like character range or set, a peg-specific construct
>> +resembling an elisp function call, a reference to another rule, or a
>> +combination of any of these.  A grammar is expressed as a set of rules
>> +in which one rule is typically treated as a ``top-level'' or
>> +``entry-point'' rule.  For instance:
>> +
>> +@example
>> +@group
>> +((number sign digit (* digit))
>> + (sign   (or "+" "-" ""))
>> + (digit  [0-9]))
>> +@end group
>> +@end example
>> +
>> +The above grammar could be used directly in a call to
>> +@code{peg-parse}, in which the first rule is considered the
>> +``entry-point'' rule:
>> +
>> +@example
>> +(peg-parse
>> +  ((number sign digit (* digit))
>> +   (sign   (or "+" "-" ""))
>> +   (digit  [0-9])))
>> +@end example
>> +
>> +Or set as the value of a variable, and the variable used in a
>> +combination of calls to @code{with-peg-rules} and @code{peg-run},
>> +where the ``entry-point'' rule is given explicitly:
>> +
>> +@example
>> +(defvar number-grammar
>> +        '((number sign digit (* digit))
>> +          (sign (or "+" "-" ""))
>> +          (digit [0-9])))
>> +
>> +(with-peg-rules number-grammar
>> +  (peg-run (peg number)))
>> +@end example
>> +
>> +By default, calls to @code{peg-run} or @code{peg-parse} produce no
>> +output: parsing simply moves point.  In order to return or otherwise
>> +act upon parsed strings, rules can include @dfn{actions}, see
>> +@xref{Parsing Actions} for more information.
>> +
>> +Individual rules can also be defined using a more @code{defun}-like
>> +syntax, using the macro @code{define-peg-rule}:
>> +
>> +@example
>> +(define-peg-rule digit ()
>> +  [0-9])
>> +@end example
>> +
>> +This allows the rule to be referred to by name within calls to
>> +@code{peg-run} or @code{peg-parse} elsewhere, and also allows the use
>> +of function arguments in the rule body.
>> +
>> +@node PEX Definitions
>> +@section PEX Definitions
>> +
>> +Parsing expressions can be defined using the following syntax:
>> +
>> +@table @code
>> +@item (and E1 E2 ...)
>> +A sequence of PEXs that must all be matched.  The @code{and} form is
>> +optional and implicit.
>> +
>> +@item (or E1 E2 ...)
>> +Prioritized choices, meaning that, as in Elisp, the choices are tried
>> +in order, and the first successful match is used.
>
> It is worth highlighting that it is different from CFGs.
>
>> +@item (* E)
>> +Zero or more of an expression, as the regexp ``*''.
>> +
>> +@item (+ E)
>> +One or more of an expression, as the regexp ``+''.
>
> It is worth highlighting the greedy part here and referring to &A and
> !A.

I don't believe there is separate syntax for &A and !A -- those are
written (if A) and (not A).

>> +@item SYMBOL
>> +A symbol representing a previously-define PEG rule.
>
> defined
>
>> +By default the process of parsing simply moves point in the current
>> +buffer, ultimately returning @code{t} if the parsing succeeds, and
>> +@code{nil} if it doesn't.  It's also possible to define ``actions''
>> +that can run arbitrary Elisp at certain points during parsing.  These
>> +actions can affect something called the @dfn{parsing stack}: a list of
>> +values built up during the course of parsing.  If the stack is
>> +non-@code{nil} at the end of parsing, it is returned as the final
>> +value of the parsing process.
>
> Actions are only run when the expression matches; with point moved after
> the match, right? What about &A and !A?

That's right, actions only run if the parsing succeeds, and they run all
at once at the end. Maybe I can move all discussons of parsing success
vs failure into one place.

>> +There must be values on the stack before they can be popped and
>> +returned.
>
> What if there is just one value in the stack while the action required two?
>
>> +@item (list E)
>> +Match E, collect all values produced by E (and its sub-expressions)
>> +into a list, and push that list to the stack.
>> +@end table
>
> This one is not very clear. Does it imply that E is recursively wrapped
> into substring?

It's not very clear because I don't fully understand it! It does not
implicitly create any value-returning calls (such as `substring'). I
think what it means is that, by default, values returned by actions are
all spliced into a single flat list. If you need some of those values to
be returned in a sub-list, you can use this form.

It's a bit tricky to use because the E in (list E) could potentially
descend many levels and branch out into any number of sub-expressions,
so you need to have a clear mental model of what values might ultimately
be coming out of E. I guess that's also true for the whole thing,
though.

>> +It is up to the grammar author to keep track of which rules and
>> +sub-rules push values to the stack, and the state of the stack at any
>> +given point in the parsing.  If an action pops values from an empty
>> +stack, the symbols will be bound to @code{nil}.
>
> The part about popping out of empty stack looks out of scope. Maybe move
> it to earlier discussion of variable bindings in actions?

Okay, I'll remove this, and just add a shorter note up above about empty
stacks.

Thanks again,
Eric