What exactly is Pratt parsing used for and how does it work?

Question

I've come across the term “Pratt parsing”. The only thing I know is that it's an algorithm (or a pattern, a technique) used to parse expressions.

How does it work? I'd like to see the intuition behind the algorithm, not just a series of steps to perform. What problems does this technique actually solve, and at what cost? How is it different from other well-known traditional/basic parsing strategies? Has it been “superseded” (at least in some aspects) by better techniques?

Answer 1

Motivation

What problems does this technique actually solve, and at what cost?

In a BNF grammar, you need a nonterminal for each level of operator precedence.

 ⟨additive⟩ =
  ⟨multiplicative⟩ ( (+ | -) ⟨multiplicative⟩ )*

 ⟨multiplicative⟩ =
  ⟨unary⟩ ( (* | /) ⟨unary⟩ )*

 ⟨unary⟩ =
  (+ | -) ⟨term⟩

 ⟨term⟩ =
  ⟨number⟩ | ⟨variable⟩

If you translate this to a recursive-descent parser, each nonterminal becomes a function. In pseudo-Python:

def accept_additive():
    lhs = accept_multiplicative()
    if lhs is None:
        return None

    while True:
        op = accept_additive_operator()
        if op is None:
            break
        rhs = expect_multiplicative()
        lhs = Binary(op, lhs, rhs)

    return lhs

def accept_additive_operator():
    return accept_token('+') or accept_token('-')

def expect_multiplicative():
    e = accept_multiplicative()
    if e is None:
        raise ParseError()
    return e

def accept_multiplicative():
    ...

def accept_multiplicative_operator():
    ...

def expect_unary():
    ...

def accept_unary():
    ...

def accept_unary_operator():
    ...

def expect_term():
    ...

def accept_term():
    return accept_number() or accept_variable()

So it takes many nested calls to reach the parsers for the leaves of the AST: before the parser even consumes a character, it must go down the chain of accept_additive() → accept_multiplicative() → accept_unary() → accept_term(), most of which is unproductive.

Solution

How does it work?

How is it different from other well-known traditional/basic parsing strategies?

In Top-Down Operator Precedence Parsing, Vaughan Pratt devised a method of simplifying this pattern, in a way that integrates well with recursive descent parsing.

The technique is to add a precedence table, which associates each operator token with a few properties:

• “Left binding power” (LBP), an integer precedence level

• “Null denotation” (NUD), a function to parse it in prefix position (nothing to its left)

• “Left denotation” (LED), a function to parse it in infix position (something to its left)

The chain of calls is replaced by a single loop that uses the token to dispatch to the appropriate parser immediately, skipping over the irrelevant precedence levels. In this case, the precedence levels are these.

0. Literal / Minimum
1. Additive
2. Multiplicative / Maximum

So the table looks like this. Notice that there’s an extra “end” marker token with minimum precedence.

Token	Precedence (LBP)	Prefix (NUD)	Infix (LED)
*	Multiplicative (2)	None	mul_led
/	Multiplicative (2)	None	div_led
+	Additive (1)	add_nud	add_led
-	Additive (1)	sub_nud	sub_led
Number	Literal (0)	num_nud	None
Variable	Literal (0)	var_nud	None
End	Minimum (0)	None	None

None indicates cases where a parse error could occur, so this also allows context-sensitive error reporting.

The top-level expression parser can now work iteratively. It’s parameterised by a “right binding power” (RBP), which starts at the minimum precedence level when parsing a top-level expression. It grabs a token and tries to parse it as a prefix operator, then repeatedly tries to parse infix expressions above the current precedence level.

def accept_expression(rbp):
    current = next_token()
    lhs = table[current].nud()
    while table[current].lbp > rbp:
        operator = current
        current = next_token()
        lhs = table[operator].led(lhs)
    return lhs

This is the sense in which it’s “top-down”: like the recursive descent parser, it considers the lowest-precedence operators first, and makes recursive calls at higher precedence levels. The definitions of the individual operator parsers, where this recursion actually happens, are quite mechanical:

def add_nud():
    return expect_expression(PREC_MAX)

def add_led(lhs):
    return Binary('+', lhs, expect_expression(PREC_ADD))

A right-associative operator would use a lower precedence than the current level; for example, take exponentiation:

def exp_led(lhs):
    return Binary('^', lhs, expect_expression(PREC_EXP - 1))

Conclusion

Has it been “superseded” (at least in some aspects) by better techniques?

Mostly it hasn’t. Parser generators like Happy and parser combinator libraries like Megaparsec do have some facilities for handling operator precedence automatically. However, you may still need to write a recursive descent parser by hand in order to gracefully recover from errors and produce helpful feedback. In that case, Pratt parsing is a nice technique for simplifying the parser and improving its performance compared to naïve RD. It readily admits user-defined operators, by just allowing the precedence table to be extended, and it works equally well in imperative and functional style.

Finally, operator-precedence grammars can describe a fairly large class of languages, too, so it’s also quite possible to parse a language entirely with this technique, or only modest extensions. For example, I once wrote a language where if was considered a prefix binary operator and else an infix binary operator, with precedence and associativity defined so that if A B else if C D else E would parse as (if A B) else ((if C D) else E).