Glossary
What is a Pratt parser?
A Pratt parser parses expressions by giving each kind of token up to two parsing functions (one for when it starts an expression, one for when it appears between two) and a precedence. It is named after Vaughan Pratt, who described it in 1973 as "top down operator precedence".
How it works
The core is one function, parsePrecedence(level):
- Read a token and call its prefix function (a number literal, a unary minus, a parenthesis).
- While the next token's precedence is at least
level, read it and call its infix function (a binary+, a call(, a dot), passing what was parsed so far as the left operand.
An infix function for + parses its right side with parsePrecedence one level higher, which gives left associativity. Adding an operator is one row in a table.
Pratt vs recursive descent
A recursive descent parser writes one function per precedence level (equality, comparison, term, factor, unary). That is clear but repetitive, and every expression walks through all the levels. A Pratt parser collapses those levels into a table. Crafting Interpreters uses recursive descent for jlox (chapter 6) and a Pratt parser for clox (chapter 17), so you build both and can compare.
Questions
Is a Pratt parser recursive descent?
It is a top-down recursive parser too, but it drives precedence from a table instead of from a chain of grammar rules.
What is binding power?
Another name for precedence in Pratt parsing: how strongly an operator holds on to the operands around it.