Pika parsing: reformulating packrat parsing as a dynamic programming algorithm
arxiv.org
arxiv.org
bottom-to-top is fairly common for parsing (e.g. pretty much any LR based parser will do so), but right-to-left is not something I've encountered before. The very right-most terminal is the first thing matched with this technique.
The other thing I wasn't a fan of is he doesn't give an recursive descent (RD) algorithm, even though it's trivial to describe RD using a pair of functions (parse-alt; parse-rule) over a grammer. When RD is expressed as a grammar, almost every parsing algorithm falls out as a "memoization" hack for one part of the algorithm, or another.
Which always puzzled me, because I was like "so what, is it supposed to be somehow surprising that circular dependencies can create the liar paradox (or some other infinite inference loop?)"
Your circular dependencies are metacircular rather than circular. That corresponds to circular if you can prove that truths in the system and its metasystem are equivalent, but that's often not so easy to show rigourously. (In other words, so you can be really really sure you haven't missed a subtle loophole). It's tempting to assume they are equivalent by intuition, but that assumption isn't correct for all logic systems.
Like many good theorems, the core idea is simple once explained.
Gõdel's incompleteness theorem required the axioms and logical deduction rules of the arithmetical logic used at the time to be encoded using that very same arithmetic, and to prove that's possible, that it works, and it's consistent. That takes some rigour. Until it was done, it wasn't obvious you could definitely prove that it works, because system-metasystem relationships often have some subtle twist.
My favourite example of a subtle twist like that is Skolem's Paradox. Which relates back to diagonalization, and shows that maybe countability and uncountability aren't so simple after all.