Home

Pratt Parsing Index and Updates

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, 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.

• Parsing Expressions by Recursive Descent (1999 an on) by Theodore Norvell: This article coined the term precedence climbing, citing an article by Clarke.

(2) Review of Pratt/TDOP Parsing Tutorials

I reviewed four articles, in order to motivate a different code structure.

• Top Down Operator Precedence (2007) by Douglas Crockford
• Simple Top-Down Parsing in Python (2008) by Fredrik Lundh
• Top-Down operator precedence parsing (2010) by Eli Bendersky
• Pratt Parsers: Expression Parsing Made Easy (2011) by Bob Nystrom

(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 structure I used, with tested and runnable code in my pratt-parsing-demo repo. Summary:

1. I prefer to use a pair of lookup tables for precedence, rather than token objects with dynamic dispatch.
2. I prefer to enclose the entire parser in an class, with the current token as a member, rather than as a global variable.

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.

March 2017 Updates

• From Precedence Climbing to Pratt Parsing (2016). I contacted Theodore Norvell after publishing my article, and he agreed that they are the same. Later he published this nice follow-up article.

To avoid confusion, I recommended dropping the precedence climbing name in favor of the earlier Pratt parsing name.

After looking at real code, I've changed my view. I would now classify the two top-down algorithms like this:

• Does the code have a single table of precedences? Is there a single recursive function? If so, call it precedence climbing. You will likely see ad hoc techniques to handle the difference between the unary -5 and binary x - 2, as well as the tenary operator.
• Pratt parsing: Are there two tables of precedences, or two dynamically dispatched methods? (for left and right "binding power") Is there a set of mutually recursive functions?