the approach I am taking is to combine the PEG with a step of AST processing in order to then produce a correct and descriptive tree structure (for later rendering).
I do agree the Guile library has some spots to improve but honestly, I am already enjoying it so much, and it's far better for the Lisper in me than other things I've tried. I also find S-expressions much more comprehensible and self-documenting.
Looking forward to seeing what you do with it :)
I am indeed hoping that this library is useful for more people and that perhaps things like Haunt blog generator can use it (and other interesting uses)
As for nested markup, and nested lists it has been tricky, but so far I've really promising results:
(assert-equal #:got (inline-org->html (inline-org->ast "*bold with /italic/*")) #:expect "<strong>bold with <em>italic</em></strong>")
LLMs have changed the equation. It used to take me 2-3 hours to write a parser for a moderately complex grammar. Now, if I hand an LLM a loosely written, BNF-ish grammar and ask for a recursive-descent parser, it finishes the job in five minutes. At this point, writing them by hand is hard to justify. The model does it substantially faster, and lately, often better than I do.
Which makes me wonder: what’s the appeal of PEGs or parser generators now? They used to make sense when hand-writing wasn't practical, but what compelling reasons are left to use them today?
The reason why it became second nature for you is this hand-rolling, manual work. I observed that with math - unless you manually practice problem solving (integrals, differential equations), you might know the mechanics but you'll have hard time solving them. And that knowledge of mechanics will also fade away at some point.
> LLMs have changed the equation. It used to take me 2-3 hours to write a parser for a moderately complex grammar. Now, if I hand an LLM a loosely written, BNF-ish grammar and ask for a recursive-descent parser, it finishes the job in five minutes. At this point, writing them by hand is hard to justify
So, what is the difference between LLMs generated "manual" parsers vs those with parser generators, beside that with LLM that will be done in five minutes + plus some $$ and with parser generators you'll get that for free and under a second?
> Which makes me wonder: what’s the appeal of PEGs or parser generators now? They used to make sense when hand-writing wasn't practical, but what compelling reasons are left to use them today?
The appeal is predictability - use i.e. Bison, feed it with grammar and you'll get always the same output. Not so much with LLMs.
How small of a model can complete the operation you described above? If writing a parser still requires a software forge with 2T of vram and a petabyte of training data, then I still see value in PEGs.
Maybe the smaller local models, given a structured grammar can use a PEG to generate a parser.
No LLMs needed, and you can jump straight to coding, and you don't have to go through precedence shenanigans.
I just had the robots write a PEG parser generator...
Which can do analysis on the grammars which, I suspect, a hand (or LLM) written one can't do so you don't end up chasing infinite recursion, dead rules and whatnot. It also got shoehorned into the regex engine (https://arxiv.org/abs/1210.4992) for my toy Java 1.0 compiler to loop back to TFA.
For my APL interpreter they had to do the 'handwritten' parser (a Pratt parser a sibling comment brings up) as you need to combine parsing and evaluation since there's no way for the parser to tell what it's looking at because APL syntax is just weird.
Horses for courses, as they say.
Go and Rust (and Pascal) have cleaned up C's awful legacy enough that they're parseable with LL(X) parsers that don't have scary corner cases or polynomial behavior.
The two are useful for different layers of abstraction: regex is for lexing and PEG is for parsing.
Speaking of the Chomsky hierarchy, last I checked, it is still unproven whether or not PEGs can parse all context free languages. Intuitively, they're _probably_ weaker than CFGs, but no one has yet provided a counter example.
I have no easy way to express this other than to plug my recently-released OSS, namely a library I wrote to implement "RegexStores" in Python[1] to compile complex, composed regexes upfront from a custom DSL. I'll link a representative usecase below[2], which I think drives home two things:
1. Regex deserves to be composed using named groups, at the very least! Most people aren't even aware that you can define named groups upfront and then reference them by name throughout, even 'capturing' them multiple times in one match.[3] Even when you do write patterns that use subroutines, the ergonomics of actually accessing, say, the three matched substrings for the `username` group in your single match is finnicky at best (without some magic[4]...).
2. Regex needs high quality syntax highlighting. The linked page is hopefully skimmable in a python sense, but trying to decipher the individual patterns in GitLab would be tough even for me, and I wrote the darn things. It's kinda awkwardly sized, but this screenshot drives home the basics of the point -- note the bright yellow named groups, which are basically subroutine invocations as discussed above: https://i.imgur.com/NllqM6S.png
Sorry to quasihijack the thread. Hopefully the fact that all this stuff has never been announced or published anywhere is proof enough of my good intentions -- that is, to defend my one n' only :)
Most of this functionality was conceived and implemented in a rage after I found out that Rust's main (only?) regex library avoids the possibility of infinite loops by just dropping half the features of the language, so excuse the jank. Even the halting problem seems solvable when you're willing to make moves like that!
[1]: https://gitlab.com/doering-ai/libs/basis/#regular-expression...
[2]: https://gitlab.com/doering-ai/apps/wiki-parse/-/blob/main/wi...
[3]: I wrote up an overview of advanced regexes in Python a while back, but was hit by the agential engineering bus before I had the time to polish and release it. Some may find it interesting, if overly long -- the aforementioned subroutines are covered under `3.1`, and repeated captures under `6.2`: https://gitlab.com/doering-ai/libs/basis/-/blob/main/docs/re...
[4]: https://gitlab.com/doering-ai/libs/basis/-/blob/main/my/rege...
They're a proper superset of regular languages and a proper subset of deterministic context-free languages, but they retain many of the nice properties of regular languages that DCFLs don't - they're closed under intersection, union, concatenation, Kleene Star and reversal.
They can parse more languages that Regular Expressions (non PCRE), but fewer than deterministic CFG subsets like LL/LR. They're expressive enough to parse languages which have a regular tree structure like S-expressions, JSON, XHTML.
I started exactly such a project, for org syntax, a while ago. Didn't get very far though because it seems to me that things in org cannot be parsed and understood in one go. For example the TODO keywords can be specified at the top of an org file and then would influence how headings in the document are understood. This cannot be done with merely a PEG.
Another tricky point is nested inline markup. Bold inside italic? Verbatim inside bold, inside italic? And so on. Would be great to support all meaningful combinations via recursive rules. Org has many inline markup things. Even programming language specific inline markup elements.
Another issue is, that Guile's PEG library, when using the non-string form of grammar rules, does not allow mutually recursive grammar rules, due to being buggy (in that way it is not excellent, but in other ways it is!). One has to use the string form or rules, which makes it a lot less nice to use, unfortunately. I hope that will be fixed at some point, because I like the library except for that. And it is in the standard lib, no need to install any dependencies. Like to use it for AoC puzzle inputs for example.
Will be interesting to read how far they got.
EDIT: Also it's going to be great to have an actual grammar based parser for org. This will ease creating one for other tools, like for example parsers of readmes in repos on git hosters.