Jeffrey Kegler, creator of the Marpa parser, writes about parsing theory, its history, and occasional topics such as Gödel and the US Constitution.
Commenters call the site superb, praise the parsing timeline, and one reports great success with Marpa for its simple and accurate error messages.
I believe YAML has serious issues and I would not be using it as a configuration format.
But I think a lot of the criticism around YAML misses the mark. YAML is not excessively overused as configuration language. It is not dominant like XML was back in its heyday. TOML has a pretty strong mindshare, and many projects are still using JSON or XML. I would pick TOML over YAML any day for this usage, but I still think YAML beats XML and JSON (just think about comments and terrible merge resolution whenever you add an item to an array or an object).
But YAML does reign supreme in the world of DevOps-oriented DSLs. YAML is more suited for DSL compared to alternatives, like TOML, JSON, JSON5 or XML:
- YAML is the least verbose of all alternatives (especially XML, but even JSON5 and TOML).
- YAML requires the least of amount of "syntax noise" on top of your DSL. The "syntax noise" is mostly limited to indentation, colons, dashes (for arrays), indented text block markers and occasionally quotation marks. JSON, JSON5 and TOML require quoting all string values and explicitly marking arrays and object boundaries, which make the DSL seem less fluent. XML is even worse.
- YAML supports indenting multi-line strings, so you can easily embed other formats. This makes adding markdown descriptions (in Swagger/OpenAPI) or embedded shell scripts (in YAML-based CI/CD DSLs) a breeze.
- YAML syntax is hierarchical. The same is true for JSON and XML, but not for TOML. TOML syntax only has two…
LR parsers like yacc are obsoleted by Earley parsers, which Cox apparently didn't know about in 2010. Quoting <http://loup-vaillant.fr/tutorials/earley-parsing/what-and-why#Why>:
The biggest advantage of Earley Parsing is its accessibility.
Most other tools such as parser generators, parsing
expression grammars, or combinator libraries feature
restrictions that often make them hard to use. Use the wrong
kind of grammar, and your PEG will enter an infinite loop.
Use another wrong kind of grammar, and most parser
generators will fail. To a beginner, these restrictions feel
most arbitrary: it looks like it should work, but it doesn't.
There are workarounds of course, but they make these tools
more complex.
Earley parsing Just Works™.
On the flip side, to get this generality we must sacrifice
some speed. Earley parsing cannot compete with speed demons
such as Flex/Bison in terms of raw speed. It's not that bad,
however:
• Earley parsing is cubic in the worst cases, which is the
state of the art (and possibly the best we can do). The speed
demons often don't work at all for those worst cases. Other
parsers are prone to exponential combinatorial explosion.
• Most simple grammars can be parsed in linear time.
• Even the worst unambiguous grammars can be parsed in
quadratic time.
My advice would be to use Earley parsing by default, and only
revert to more specific methods…
Yes, yes they are. I've used them successfully for various parsing projects. And in fact Bison recently picked up GLR parsing to deal with multiple options (https://www.gnu.org/software/bison/manual/bison.html#Generalized-LR-Parsing).
But for something even more fun, I suggest you check out Marpa (https://jeffreykegler.github.io/Marpa-web-site/). It is, by far, the nicest parsing tool I have ever worked with. Being able to parse ANY BNF is huge. And the state tables for debugging! Knowing what possibilities you have makes things way easier. Especially for getting stuck in an ambiguous spot of your grammer. Finally, using ruby slippers to get out of a tight spot is hugely useful.
My one complaint is that the only implementation is in Perl. The core engine is written in C though, so someday I would like to convert the Perl into Python. I started several months ago, and haven't been able to get back to it. (https://github.com/srathbun/pyMarpa)
At the end, Kegler links to this comprehensive overview of the history of parsing:
https://jeffreykegler.github.io/personal/timeline_v3
which contains this easily overlooked but IMHO extremely significant statement:
"a recursive descent implementation can parse operator expressions as lists, and add associativity in post-processing"
Personally, it has always seemed like a no-brainer to me that this is clearly the Right Answer. It is a mystery to me that the computing world at large has spent so much effort on a problem whose solution is actually very straightforward if you just give in on one tiny little piece of theoretical purity.
See http://www.flownet.com/ron/lisp/parcil.lisp for my own implementation of such a parser. As you will see if you count LOCs, it's very, very simple by parser standards, and yet it handles all the "hard" problems: associativity, precedence, infix and prefix operators.
> PEGs are however are easier to reason about, no ambiguities, so that was good enough reason.
I frequently hear this mentioned ("PEGs don't have ambiguity"). It is literally true, but I don't think it's true in the sense that actually matters.
I've blogged about this in the past (https://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html#dealing-with-ambiguity-in-cfgs), but I'm not the only person saying this:
> PEG is not unambiguous in any helpful sense of that word. BNF allows you to specify ambiguous grammars, and that feature is tied to its power and flexibility and often useful in itself. PEG will only deliver one of those parses. But without an easy way of knowing which parse, the underlying ambiguity is not addressed -- it is just ignored.
https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2015/03/peg.html
my favorite Gödel, Einstein story is when he was prepped by Einstein for an US immigration hearing, and then told the judge he found some loopholes in the constitution. Was it his character shaping his work, or his work and surrounding shaping (making) him, and if so what shapes a man like Gödel (or Freud, Einstein, Popper, Russel, ...) many others of that time. It seems there was a huge density of brilliant people concentrated in Europe at the time. Hardly anyone who died within the past 30 years will be remembered as those from that generation I'm sure.
Now everyone is writing AI papers which all look identical. Sure academia has changed.
A Contradiction in the U.S. Constitution https://jeffreykegler.github.io/personal/morgenstern.html
Gödel’s Loophole
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2010183