[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Make peg.el a built-in library?
From: |
Helmut Eller |
Subject: |
Re: Make peg.el a built-in library? |
Date: |
Fri, 27 Aug 2021 08:41:19 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) |
On Thu, Aug 26 2021, Eric Abrahamsen wrote:
> Whoo, I've been trying to get enough of a handle on the parsing actions
> to write a documentation patch for them -- now I'm seeing what Helmut
> meant by "semantically unintuitive".
What I actually meant with "semantically unintuitive" are issues
described in Roman Redziejowski's "Trying to understand PEG" paper[*].
He writes:
The problem with limited backtracking is that by not trying hard it
may miss some inputs that it should accept. A notorious example is
the rule A = aAa | aa that defines the set of strings of a’s of even
length. Implemented with limited backtracking, this rule accepts only
strings of length 2^n.
> The sum total of docs regarding
> actions is:
>
> A "stack action" takes VARs from the "value stack" and pushes the result
> of evaluating FORMs to that stack.
Using an "open stack" for actions was my rather idiosyncratic choice and
I'm sure that many people will not like it. The syntax ( a b -- b a )
should be familiar to Forth programmers, where it's used to describe the
stack-effect of commands. The example would be the SWAP operator. If
you have never, or not recently, written some Forth or Postscript, then
mentally keeping track of the stack state can be challenging.
As for "documentation" of actions: there are also some examples. I
think that the s-exp parsing example turned out quite elegant.
Helmut
[*] http://www.romanredz.se/papers/FI2017.pdf