blog | oilshell.org
I've noticed that my November posts on expression parsing with Pratt's algorithm are popular and still drawing readers.
So here's an index of them, including yesterday's update, with related links.
(1) Pratt Parsing and Precedence Climbing Are the Same Algorithm
After parsing arithmetic in OSH, I noticed that the precedence climbing algorithm is a special case of the earlier Pratt parsing algorithm. But see the update below.
(2) Review of Pratt/TDOP Parsing Tutorials
I reviewed four articles, in order to motivate a different code structure.
(3) Pratt Parsing Without Prototypal Inheritance, Global Variables, Virtual Dispatch, or Java
Crockford deserves credit for reviving Pratt's algorithm, but I think his idiosyncratic style leaked into almost every future exposition of it.
In this article, I explain the code in my pratt-parsing-demo repo.
Why? I tend to use classes somewhat formally, either for dependency injection or for maintaining invariants on state. If everything's a class, then nothing is.
(4) Pratt Parsers Can Be Statically Typed
A minor update to correct a misleading notion.
(5) Precedence Climbing is Widely Used
In November, I recommended dropping the "precedence climbing" name to avoid confusion. After looking at real code, I've changed my view.
(6) Code for the Shunting Yard Algorithm, and More
An encyclopedic update from Jean-Marc Bourguet.
The post How Desmos Uses Pratt Parsers may be useful if you prefer to read code in TypeScript. See desmosinc/pratt-parser-blog-code.
They also compare Pratt Parsing to using Jison, a LR(1) parser generator like Yacc or GNU Bison.