Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 61 ยท Parsing

Pratt Parsing and Operator Precedence

Learn Pratt parsing with binding powers: prefix, infix and postfix operators, right associativity and the ternary operator, plus the shunting-yard algorithm.

Expressions are the part of a language where recursive descent feels clumsy. With ten levels of precedence you need ten nearly identical functions, and adding one new operator means inserting a function in the middle of the chain. Pratt parsing, invented by Vaughan Pratt in 1973 and sometimes called "top-down operator precedence parsing", solves this elegantly. A single short function parses every expression, and the precedence of each operator is just a number in a table.

It is a favorite of people who write hand-made parsers, and it is used in real compilers and language tools for exactly this reason: it is compact, fast, easy to extend, and produces good error messages. In this lesson you will build a Pratt parser that handles prefix, infix and postfix operators, right associativity, function calls and even the ?: ternary. Then you will compare it with the older operator-precedence method known as the shunting-yard algorithm. The lesson assumes you have read about recursive descent and about precedence and associativity in grammars.

Binding power

Think of each operator as having a "pulling strength" toward its operands. In a + b * c the * pulls b harder than the + does, so b belongs to the *. Pratt parsing makes this idea literal. Every infix operator gets two numbers:

  • the left binding power (how strongly it pulls the expression on its left), and
  • the right binding power (how strongly it pulls what comes on its right; this number becomes the minimum power for parsing the right operand).

Bigger numbers bind tighter. The two numbers also control associativity. If the left power is smaller than the right power, the operator is left-associative: after parsing a - b, a following - has left power 5 which is less than the right power 6 that was used for b, so b is not stolen. If the left power is larger, the operator is right-associative: a following ^ can steal the right operand and nest to the right.

Operator Left power Right power Result
? (ternary) 2 1 right-associative
==, <, > 3 4 left-associative
+, - 5 6 left-associative
*, / 7 8 left-associative
^ 12 11 right-associative

Prefix operators only need one number, the power with which they take their operand. Our unary minus uses 9: it is tighter than * (so -a * b means (-a) * b) but looser than ^ (so -2 ^ 2 means -(2 ^ 2), as in mathematics). Postfix operators, such as the factorial ! and the call parentheses (, also have a single left power, and they are strong enough to bind before almost everything else.

The algorithm

The heart of the parser is one function, expr(min_bp), which means "parse an expression, but stop as soon as you meet an operator whose left power is below min_bp".

  1. Read one token. It must start an expression: a number or name becomes a leaf; ( starts a nested expr(0) that must end in ); a prefix operator reads its operand with expr(prefix_power).
  2. Look at the next token in a loop. If it is a postfix operator with power at least min_bp, consume it and wrap the expression built so far.
  3. If it is an infix operator whose left power is at least min_bp, consume it, parse the right operand with expr(right_power), and wrap everything into a node.
  4. Otherwise stop and return.

That is the whole idea. Notice that the min_bp argument carries the context: it says what the caller is willing to let us take. A recursive call for the right operand of * is made with min_bp = 8, so it will refuse any operator weaker than that, such as + or -, and hand control back.

flowchart TD
    A["expr(0): reads 1"] -->|"takes +, right power 6"| B["expr(6): reads 2"]
    B -->|"takes *, right power 8"| C["expr(8): reads 3, then sees - (5 is below 8): stop"]
    C -->|"returns 3"| B
    B -->|"sees - (5 is below 6): stop, returns (* 2 3)"| A
    A -->|"sees - (5 is at least 0): take it, build (+ 1 (* 2 3)) minus 4"| R["result"]

How 1 + 2 * 3 - 4 unfolds: each call decides how much of the rest of the input it may consume.

A Pratt parser you can run

The program below is complete. The tables at the top are the only place that knows about precedence; the parser function does not mention a single operator by name except ? and (, which need special syntax. It supports - (prefix), ! and calls (postfix), the ternary ?:, comparisons and ^. After the main examples, it traces the decisions for 1 + 2 * 3 - 4 and shows how it reports errors.

Python A Pratt parser with binding powers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check some of the results against the table. 10 - 4 - 3 is (- (- 10 4) 3), because - is left-associative. 2 ^ 3 ^ 2 is (^ 2 (^ 3 2)), the right-associative reading, which equals 512, not 64. -2 ^ 2 becomes (neg (^ 2 2)), and -3! becomes (neg (fact 3)), since the postfix ! binds tighter than the prefix minus. In the ternary a ? b : c ? d : e, the second ? is part of the else branch, and the call max(1, 2 + 3) * 4 shows that a postfix ( produces a call node whose arguments are parsed with expr(0) each.

The trace below it explains the grouping. At min_bp=0 the + is taken. Inside the right operand (called with 6), * has power 7 and is taken, but inside its right operand (called with 8), the - has power 5 and is refused. Back out in the call with 6, the - is still too weak. Only the outermost loop, at min_bp=0, accepts it. Each refusal hands the operator to the level that is allowed to use it.

To add a new binary operator to a Pratt parser, you add one line to a table. To change its precedence, you change two numbers. Compare that with inserting a new function into a chain of recursive descent methods.

Why it handles the awkward cases

Many things that are tedious in a grammar are natural here:

  • Mixed prefix and infix -. The same token plays two roles, because the parser always knows whether it is at the start of an expression (a prefix position) or in the middle (an infix position).
  • Postfix and mixfix operators. The call f(x), the index a[i] and the ternary a ? b : c are all "an infix-like token that takes an expression on the left, followed by custom syntax".
  • Right associativity. Just make the left power larger than the right.
  • User-defined operators. A language that lets programs declare new operators can add them to the table at parse time.

The cost is that the grammar for such a language is no longer written down as grammar rules but as code and tables. Error messages, on the other hand, tend to be excellent, because the parser knows exactly what it was expecting at each point.

Operator-precedence parsing and the shunting-yard algorithm

Before Pratt parsing, there was the family of operator-precedence parsers. The best-known member, the shunting-yard algorithm by Edsger Dijkstra, converts an ordinary (infix) expression into postfix form (Reverse Polish Notation, RPN), where every operator comes after its operands and no parentheses or precedence rules are needed any more. RPN is trivial to evaluate with a stack, and it is basically the instruction order for a stack machine, which makes it a link to the bytecode lessons.

The algorithm keeps an output list and an operator stack. For each token:

  • A number goes straight to the output.
  • An operator pops operators of higher precedence (or equal precedence, if it is left-associative) from the stack to the output, and is then pushed itself.
  • ( is pushed, and ) pops operators to the output until the matching (.
  • At the end, everything left on the stack is popped to the output.

The program below implements it for numbers, + - * / ^, parentheses and unary minus (a - that appears at the start or right after an operator or ( is recognized as a prefix operator and renamed neg). Associativity is the only difference between ^ and the others: for equal precedence, a left-associative operator pops, a right-associative one does not. The last block compares the results with Python's own parser, where ^ is written **.

Python Shunting-yard: infix to postfix, checked against Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the trace of 2 * 3 ^ 2 ^ 2 - 1, watch the stack. The two ^ operators pile up (* ^ ^) because a right-associative operator never pops an equal one. When - arrives, it has lower precedence than everything on the stack, so all three are popped into the output, giving 2 3 2 2 ^ ^ * 1 -. Evaluating that with a stack gives 2 times (3 to the power of 4), minus 1, which is 161. The comparison table shows that all nine test expressions agree with Python's evaluator, including -2 ^ 2 = -4 and the right-associative 2 ^ 3 ^ 2 = 512.

Pratt parsing and shunting-yard are close relatives. Both use a precedence table and an explicit or implicit stack. The difference is that Pratt's recursion builds a tree directly and handles prefix, postfix and mixfix operators gracefully, while shunting-yard produces a flat postfix list. For a compiler, you almost always want the tree.

Common mistakes

  • Swapping the powers for right associativity. If 2 ^ 3 ^ 2 parses as (2 ^ 3) ^ 2, the left power of ^ is smaller than its right power. For right associativity, left must be larger.
  • Giving prefix minus the wrong power. Too high and -2 ^ 2 becomes (-2) ^ 2; too low and -a * b becomes -(a * b). Decide deliberately.
  • Forgetting to check the end of input. After expr(0) returns, the next token must be the end marker; otherwise trailing junk such as 1 2 is silently accepted.
  • Equal left and right powers. With the same number on both sides, associativity depends on your comparison (< versus <=). Keep left and right powers different.
  • Treating ( as an infix operator everywhere. The call syntax is only valid after an expression; at the start of an expression, ( means grouping.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a Pratt parser, what does the argument min_bp of expr(min_bp) mean?

    min_bp tells the call how much of the following input it is allowed to consume. Weaker operators are left for an earlier, outer call.
  2. 2. How do you make an infix operator right-associative in the binding-power table?

    With a larger left power, the operator after the right operand is still strong enough to steal it, so the expression nests to the right, as in a ^ (b ^ c).
  3. 3. In the shunting-yard algorithm, what happens to a left-associative operator when the top of the stack has equal precedence?

    Equal precedence plus left associativity means the earlier operator must be applied first, so it is moved to the output before the new one is pushed.
  4. 4. Why does -2 ^ 2 parse as -(2 ^ 2) in the lesson's parser?

    The operand of the minus is parsed with min_bp 9, and ^ has left power 12, so ^ is taken inside the operand. The minus applies to the whole power.
  5. 5. What is the output of shunting-yard for the infix expression 1 + 2 * 3?

    In postfix form each operator comes after its operands: 2 3 * is computed first, and then 1 and that result are added.

Summary

  • A Pratt parser parses all expressions with one function, expr(min_bp), driven by a table of binding powers.
  • Infix operators have a left and a right power; left smaller than right gives left associativity, left larger gives right associativity.
  • Prefix and postfix operators have a single power, and the same token (like -) can be prefix in one position and infix in another.
  • Calls, indexing and the ternary operator fit the same scheme as "an operator after an expression".
  • The shunting-yard algorithm is an older operator-precedence method that produces postfix (RPN) with an operator stack.
  • To parse correctly, always check for the end of the input after the top-level expression.

Next: Bottom-Up Parsing: Shift-Reduce