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

[Eric Abrahamsen]

Ihor Radchenko <yantar92@posteo.net> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>>> Is there any progress merging peg.el to Emacs?
>>> I do not see any obvious blockers in the discussion, but the merge never
>>> happened?
>>
>> I will say that I tried to use PEG to resolve some gruesome text-parsing
>> issues in EBDB very recently, and failed to make it work in the hour or
>> two I'd allotted to the problem. The file-comment docs are pretty good,
>> but I think they would need to be expanded in a few crucial ways,
>> particularly to help those who don't necessarily know how PEGs work.
>>
>> Specifically, it is not obvious (to me) the ways in which PEGs (or maybe
>> just peg.el) are not fully declarative. It doesn't backtrack, and I
>> suspect it won't ever backtrack or isn't even supposed to, which means
>> users should be made explicitly aware of the ways in which their rules
>> can fail, and the ways in which declaration order matter. The comment
>> for the `or' construct reads:
>>
>> Prioritized Choice
>>
>> And that's about the only hint you get.
>
> As the comment in peg.el states, the definitions are adapted from the
> original PEG paper. There is even a link to paper and also to
> presentation explaining how peg works. I strongly advice you to read
> that. Prioritized Choice is explained there.

This is what I was saying in my original message, though: if peg.el is
going to go into core, it probably needs more/better docs than code
comments and "read this paper". Its likely users will be Elisp library
authors like me, who are just trying to free themselves from regexp hell
and want a relatively straightforward alternative.

I used peg.el to prototype search-string parsing in Gnus and everything
Just Worked the first time and it was pretty amazing. In my later
example below everything did not Just Work, but I think with some more
hand-holdy documentation it would have.

>> I was trying to parse a
>> multiword name like
>>
>> Eric Edwin Abrahamsen
>>
>> into the structure
>>
>> (("Eric" "Edwin") "Abrahamsen")
>>
>> using rules like
>>
>> (plain-name (substring (+ [word])) (* [space]))
>> (full-name (list (+ plain-name) plain-name)
>>     `(names -- (list (butlast names) (car (last names)))))
>>
>> Which always fails to match because (+ plain-name) is greedy and eats up
>> all the words. It doesn't ever try leaving out the last word in an
>> attempt to make the rule match.
>
> One way is
>
> (with-peg-rules
>     ((name (substring (+ [word])) (* [blank]))
>      (given-name name (not (eol)))
>      (last-name name (and (eol)))
>      (full-name (list (+ given-name) last-name) `(names -- (list (butlast 
> names) (car (last names))))))
>   (peg-run (peg full-name)))
>
> A simple-minded non-greedy version would be ambiguous. You must
> necessarily indicate end of input.
>
> A more appropriate non-ambiguous non-greedy statement would involve or
> (which you admittedly did not understand):
>
> (with-peg-rules
>     ((name (substring (+ [word])) (* [blank]))
>      (given-name name)
>      (last-name name (and (eol)))
>      (full-name (list (+ (or last-name given-name)) (and (eol))) `(names -- 
> (list (butlast names) (car (last names))))))
>      ;;;;;;;;;;;;;;;;;;;;;^^
>   (peg-run (peg full-name)))

Thanks! This is very helpful to my understanding. In this particular
case I'm putting strings in a temporary buffer, so signals like (eol) or
more likely (eob) are present and reliable.

>> I'm happy to write the docs (should it have its own info manual
>> section?), if we really think there are no other necessary
>> fixes/improvements.
>
> I find PEG to be a nice addition when regexps do not cut the necessary
> parsing, while using Bovine or tree-sitter is an overkill.

I've never tried tree-sitter, but I have tried and failed to make Bovine
do this sort of thing more than once over the years. I also agree that a
middle ground is needed.

Eric