Why Sponsor Oils? | blog | oilshell.org

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, including yesterday's update, with related links.

Original Series

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 and on) by Theodore Norvell: This article coined the term precedence climbing, citing a 1986 article by Clarke.

Review of Pratt/TDOP Parsing Tutorials (JS, Java, Python)

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

Pratt Parsing Without Prototypal Inheritance, Global Variables, Virtual Dispatch, or Java (Python)

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.

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 variable, rather than as a global variable.

Why? I tend to use classes somewhat formally, either for dependency inversion or for maintaining invariants on state. If everything's a class, then nothing is.

Pratt Parsers Can Be Statically Typed

A minor update to correct a misleading notion.

2017 Updates

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.

• From Precedence Climbing to Pratt Parsing (2016). I contacted Theodore Norvell after publishing my articles, and he agreed with my claims. Later he published this follow-up article, which treats Pratt parsing as an extension of precedence climbing.

Code for the Shunting Yard Algorithm, and More

An encyclopedic update from Jean-Marc Bourguet.

2019 - TypeScript

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.

2020 - Rust

Simple But Powerful Pratt Parsing. An introduction to the algorithm, with code in Rust. (reddit comments)

The post says that the algorithm is both recursive and iterative, which is a good point.

Here's a related observation that may also help. You can divide recursive algorithms into two categories:

1. Algorithms where the recursive function is also pure. For example, counting the nodes in a tree is a one-line function that has no variables:

function count(node) {
  return 1 + count(node.left) + count(node.right)
}

2. Algorithms where state is mutated while recursing. Recursive descent parsing and Pratt Parsing both fall in this category, and that's one thing that makes them harder to understand (and debug).

   In addition to returning or evaluating subexpressions, you advance through the token stream while recursing. This is done in the Next() call on line 222 of tdop.py. Note that ParseUntil() and the set of nud() / led() functions are mutually recursive.

2023 - Elm

Nice diagrams in this article: