How to write a Pratt parser for operator precedence in filters#

Your filter language gains arithmetic and not, and the recursive descent parser grows a function for every precedence level. Then -2^2 evaluates to 4 where your spec says -4, 2--1 fails as a syntax error, and not a = 1 negates the field before comparing it. Each fix means reordering functions that call each other.

What you get

You will end up with a filter parser whose precedence lives in one table of binding powers, with tests that pin -2^2, 2--1, and not a = 1. This is for you if your query language has more than three precedence levels.

Short answer

A Pratt parser gets operator precedence right with a table of binding powers and one loop. Read a prefix expression, then keep taking operators that bind more tightly than the current minimum, and parse each right side at that operator’s own power. Give prefix minus a row of its own, between * and ^, so -2^2 is -(2^2) and 2--1 parses.

You will need

Node 22.18 or later, which runs a .ts file directly by stripping its types, and Python 3.8 or later for the Lark comparison. Verified 2026-10-21 against Node 22.22.0, Python 3.13.16, peggy 5.1.0, and lark 1.3.1. The parser has no dependencies. npm ci installs peggy, and its postinstall step puts lark in vendor/ for the comparison. The sample builds trees and stops there, so evaluating a tree against a record is a walk you write separately. Start with write a recursive descent parser by hand in TypeScript if tokens and parse trees are unfamiliar.

Approaches compared

peggy and Lark make the grammar the source of truth, so a reviewer reads precedence as rule order rather than as numbers. Each pays with a rule per level, and a level added later means a new rule plus an edit to the rule that calls it. Lark adds a transformer method per operator and a Python runtime. The Pratt parser costs a lexer and error messages of its own, and a table that only someone who knows the loop can check.

Put every operator in one table

The table holds all of the precedence logic. Each infix operator gets a left binding power, which says how tightly it holds the expression to its left, and an associativity. Each prefix operator gets the power its operand is parsed at.¹

// A higher number binds tighter. The gaps of ten leave room for a level added later.
export const TABLE: Table = {
  infix: {
    or: { lbp: 10, assoc: 'left' },
    and: { lbp: 20, assoc: 'left' },
    '=': { lbp: 40, assoc: 'none' },
    '!=': { lbp: 40, assoc: 'none' },
    '<': { lbp: 40, assoc: 'none' },
    '<=': { lbp: 40, assoc: 'none' },
    '>': { lbp: 40, assoc: 'none' },
    '>=': { lbp: 40, assoc: 'none' },
    '+': { lbp: 50, assoc: 'left' },
    '-': { lbp: 50, assoc: 'left' },
    '*': { lbp: 60, assoc: 'left' },
    '/': { lbp: 60, assoc: 'left' },
    '%': { lbp: 60, assoc: 'left' },
    '^': { lbp: 80, assoc: 'right' },
  },
  prefix: {
    // Below the comparisons, so `not a = 1` is `not (a = 1)`.
    not: { op: 'not', rbp: 30 },
    // Between * and ^, so `-2^2` is `-(2^2)` and `-2*3` is `(-2)*3`.
    '-': { op: 'neg', rbp: 70 },
  },
}

Only the order of the numbers matters, so the gaps of ten are free room: a ?? operator between the comparisons and + can take 45 without renumbering a row. The words and, or, and not are keys like +, and the lexer reads its symbols from the same table, longest first.

Two rows carry the decisions filter languages most often get wrong. not sits at 30, below the comparisons, because whoever writes not a = 1 means not (a = 1). The same low power is why prefix refuses a = not b = c, where not would swallow the second =. Prefix - sits at 70, between * and ^, which is where Python’s precedence table puts unary minus.

Parse with one loop

The loop is the whole of Pratt’s algorithm. It reads one prefix expression, then takes each following operator whose left binding power beats the current minimum, and parses that operator’s right side with a minimum of its own.

  // The whole algorithm: read a prefix, then take every operator that binds
  // more tightly than `minBp`, parsing its right side with its own power.
  function expr(minBp: number): Tree {
    if (++depth > MAX_DEPTH) throw new ParseError(src, peek().offset, `filter nests deeper than ${MAX_DEPTH} levels`)
    let left = prefix(minBp)
    for (;;) {
      const t = peek()
      const info = infixOf(t)
      if (!info || info.lbp <= minBp) break
      pos++
      // Left-associative: the right side stops at an operator of the same power,
      // so this loop folds `a - b - c` to the left. Right-associative: the right
      // side starts one point lower, so the next `^` joins it instead.
      const right = expr(info.assoc === 'right' ? info.lbp - 1 : info.lbp)
      left = { op: t.text, args: [left, right] }
      if (info.assoc === 'none' && infixOf(peek())?.lbp === info.lbp) {
        throw new ParseError(src, peek().offset, `'${peek().text}' cannot follow '${t.text}' without parentheses`)
      }
    }
    depth--
    return left
  }

Associativity is the argument to the recursive call. A left-associative - parses its right side at its own power, so the second - in 10 - 4 - 3 cannot join that side and goes back to the loop, which folds to the left. A right-associative ^ parses its right side one point lower, so the next ^ joins it. A comparison is non-associative: after one, the loop refuses another at the same power.

Run the parser over eight filters, two of them broken:

node demo.ts

price * qty > 100 and not archived   (and (> (* price qty) 100) (not archived))
10 - 4 - 3                           (- (- 10 4) 3)
2 ^ 3 ^ 2                            (^ 2 (^ 3 2))
-2^2                                 (neg (^ 2 2))
2--1                                 (- 2 (neg 1))
not a = 1 and b = 2                  (and (not (= a 1)) (= b 2))
a < b < c                            ParseError: 1:7: '<' cannot follow '<' without parentheses
2 +                                  ParseError: 1:4: expected a value, found the end of the filter

(neg (^ 2 2)) is -(2^2), and (- 2 (neg 1)) is 2 - (-1). The same - token became a prefix operator where a value was due, and an infix operator where an operator was due. The chained comparison stops at its second <, and the error names its column.

Write the same language as layered rules

A grammar tool states the same precedence as one rule per level, from the loosest operator to the tightest, where each rule’s operands are the rule after it. The tight end of the peggy grammar handles prefix minus and ^:

unary
  = "-" _ arg:unary { return { op: 'neg', args: [arg] } }
  / power

// Right-associative through recursion: the exponent is a whole unary.
power
  = base:atom exp:(_ "^" _ @unary)? { return exp === null ? base : { op: '^', args: [base, exp] } }

Lark writes the same ladder for its parser. A ? before a rule’s name inlines the rule when it matched a single child, so the tree records only the levels where an operator appeared:

// One comparison and no recursion: a second comparison is a syntax error.
?comparison: sum
           | sum COMPARE sum -> compare

?sum: product
    | sum "+" product -> add
    | sum "-" product -> sub

?product: unary
        | product "*" unary -> mul
        | product "/" unary -> div
        | product "%" unary -> mod

// Prefix minus sits below power, so -2^2 is -(2^2).
?unary: power
      | "-" unary -> neg

?power: atom
      | atom "^" unary -> pow

lark_filter.py asks for Lark’s basic lexer. The default contextual lexer matches only terminals the parser can take next, turning x = 1 andy into x = 1 and y.

Run all three parsers over the same filters, then count what each needed to gain a ?? level:

node compare.ts

lines of code, comments and blank lines excluded
  hand-written Pratt  143  pratt.ts
  peggy                57  filter.peggy + peggy-filter.ts
  Lark                 66  filter.lark + lark_filter.py

same tree from all three on 14 of 14 filters
all three reject 6 of 6 broken filters

adding a `??` level between the comparisons and +, from the copies in with-fallback/
  hand-written Pratt  +1 -0  in pratt.ts
  peggy               +3 -1  in filter.peggy
  Lark                +5 -2  in filter.lark, lark_filter.py
  same tree from all three on 3 of 3 filters, such as (> (?? discount 0) 5)

peggy rules entered to parse `x = 1`: 34
  orExpr 1, andExpr 1, notExpr 1, comparison 1, sum 2, product 2, unary 2, power 2, atom 2

The Pratt file is the longest because it carries its own lexer and error messages, which the grammar tools generate. The three agree on every tree and reject the same broken filters. The ?? rows are the trade-off in numbers. The Pratt table gains one row, while each grammar gains a rule and edits the rule that calls it, and Lark also gains a transformer method. The last line shows where peggy’s time goes, because reading x = 1 enters sum, product, unary, power, and atom once for each operand.

Time the parsers on a long filter

bench.test.ts parses one 1,615-character filter 2,000 times with each Node parser, after a warm-up, then checks that both built the same tree.

node --test bench.test.ts

ok 1 - hand-written Pratt: 2000 parses of a 1615-character filter
  ---
  duration_ms: 204.808348
  type: 'test'
  ...
# Subtest: peggy: the same 2000 parses
ok 2 - peggy: the same 2000 parses
  ---
  duration_ms: 402.309947

The Pratt parser took about half of peggy’s time. That fits the rule counts from compare.ts: the loop runs once per operator, while the layered grammar descends through every level for every operand. The ratio moves with the shape of the filter and the machine. Lark runs in Python, so its time beside these would measure the runtime rather than the algorithm. Its parser documentation claims an implementation that outperforms every other parsing library for Python.

Check it worked

Ten tests pin the table’s decisions, run with the Node test runner. The test for prefix minus covers the shared token from both sides:

test('prefix minus has its own binding power, between * and ^', () => {
  assert.equal(tree('-2^2'), '(neg (^ 2 2))')
  assert.equal(tree('2--1'), '(- 2 (neg 1))')
  assert.equal(tree('2-1'), '(- 2 1)')
  assert.equal(tree('-2 * 3'), '(* (neg 2) 3)')
  assert.equal(tree('2^-1'), '(^ 2 (neg 1))')
  assert.equal(tree('- -2'), '(neg (neg 2))')
})

node --test pratt.test.ts

1..10
# tests 10
# suites 0
# pass 10
# fail 0
# cancelled 0
# skipped 0
# todo 0
# duration_ms 490.406873

The suite also parses every prefix of a valid filter, each of which must parse or fail with a ParseError rather than a TypeError. It then feeds 100,000 nested prefix operators, parentheses, and ^ chains, which must stop at the depth cap of 64 instead of overflowing the stack. The last expects peggy and Lark to agree on filters like x = 1 andy and a = not b = c.

When it goes wrong

Prefix minus is the usual failure, because - is one token with two jobs. Pratt’s paper gives such a token two pieces of code, a null denotation for prefix use and a left denotation for infix use, and here each needs its own row. pitfall.ts runs tables that each get one row wrong:

node pitfall.ts

no prefix row for -
  -2^2       ParseError: 1:1: expected a value, found '-'
  2--1       ParseError: 1:3: expected a value, found '-'
prefix - tighter than ^ (rbp 90)
  -2^2       (^ (neg 2) 2) = 4
  2--1       (- 2 (neg 1)) = 3
prefix - between * and ^ (rbp 70)
  -2^2       (neg (^ 2 2)) = -4
  2--1       (- 2 (neg 1)) = 3
not tighter than the comparisons (rbp 45)
  not a = 1  (= (not a) 1)
not looser than the comparisons (rbp 30)
  not a = 1  (not (= a 1))
comparisons left-associative
  a < b < c  (< (< a b) c)
comparisons non-associative
  a < b < c  ParseError: 1:7: '<' cannot follow '<' without parentheses

-2^2 and 2--1 fail with expected a value. The table has no prefix row for -, so a minus where a value is due has nothing to parse it. Add the row. When -2^2 returns 4 instead, prefix minus binds tighter than ^ and negates the base before the power applies. Give it a power between * and ^.²

not a = 1 parses as (not a) = 1, which compares a boolean with a number. not binds tighter than the comparisons there. Move it to 30, between and and =.

a < b < c parses as (a < b) < c when the comparisons are left-associative. The second comparison then sets a boolean against c, and an evaluator that coerces booleans to numbers, as JavaScript does, answers without an error. Mark the comparisons non-associative so the parser asks for parentheses.

When not to do this

Do not write a Pratt parser for a language with three precedence levels. A recursive descent parser handles and, or, and the comparisons with one function each, and a reader sees the precedence in the order of the calls.

Do not choose it when the grammar is a specification other people review. A reviewer who thinks in grammar rules has to run the loop in their head to check a change to the numbers. Pratt’s paper already blamed the slow adoption of methods like his on that habit.³

Do not open the table to plugins without a test per operator. Plugins that pick the same number for different operators share a level by accident, because the table accepts duplicate powers.

Do not add Lark to a Node service only for this. The grammar reads well, but every parse then crosses into a Python process.

Related how-tos

• Remove left recursion from a PEG grammar

• Attach parse actions to grammar rules by name

• Write a recursive descent parser by hand in TypeScript

Last verified

Verified 2026-10-21 against Node 22.22.0, Python 3.13.16, peggy 5.1.0, and lark 1.3.1. Every output block is what the command preceding it printed, run in the sample directory. The output check normalizes test durations, so it confirms the timing test ran and passed, not the times it printed. Twelve runs by hand gave the Pratt parser 0.37 to 0.53 of peggy’s time.