13
$\begingroup$

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?

$\endgroup$
4

1 Answer 1

8
$\begingroup$

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.

  1. Literal / Minimum
  2. Additive
  3. 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).

$\endgroup$
1
  • $\begingroup$ There is currently an effort in the Ruby community to replace the aging "Flex/Bison-with-lots-of-hand-written-code" parser of YARV, which due to Ruby's complex syntax also ended up being used by every other Ruby implementation (despite the fact it is not designed for re-use and intimately tied to YARV), with a new parser that is designed for re-use, has no dependencies on YARV, and can be used by all other Ruby implementations as well as refactoring tools, IDEs, linters, syntax highlighters, etc. It is called Prism and is a hand-written Pratt-style TDOP parser: github.com/ruby/prism $\endgroup$ Dec 17, 2023 at 15:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .