Comment by remywang
10 hours ago
One cool factoid about PEGs is that it is an open problem if they can parse all context free languages.
10 hours ago
One cool factoid about PEGs is that it is an open problem if they can parse all context free languages.
If I understand correctly, one of the recent cool generative AI-assisted results is actually supposed to have closed this problem, complete with a Lean proof!
https://arxiv.org/abs/2608.29592
I think language designers in general have realized that there's nothing particularly virtuous about a programming language with a syntax that's hard to parse.
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.