# How to write a Pratt parser for operator precedence in filters > Parse and, or, not, comparisons, and arithmetic with a table of binding powers and one loop, then measure it against layered grammar rules in peggy and Lark. Source: https://voxgig.com/howto/pratt-parser-for-operator-precedence - Audience: api-producer - Level: intermediate - Languages: typescript, python - Verified: 2026-10-21 - Published: 2026-10-20 ## 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](https://nodejs.org/api/typescript.html) 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](/howto/recursive-descent-parser-in-typescript) if tokens and parse trees are unfamiliar. ## Approaches compared | Approach | When it fits | What it costs you | When to pick something else | | --- | --- | --- | --- | | [hand-written Pratt parser](https://tdop.github.io/) | Many precedence levels, or operators that plugins add at run time | A lexer and error messages you write yourself, and precedence that reads as numbers rather than grammar | The grammar is a specification that several people review | | [Lark](https://lark-parser.readthedocs.io/en/stable/) | The consumer is Python, and the grammar should read like the specification | One rule per precedence level, a transformer method per operator, and a Python runtime | The service runs on Node, or operators change at run time | | [peggy](https://peggyjs.org/documentation.html) | Node, a grammar file as the source of truth, and a generate step | One rule per level, a left fold in each action, and about twice the Pratt parse time | Long filters arrive on a hot path, or the operator set changes at run time | 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.[^1] ```ts title="pratt.ts" // 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](https://docs.python.org/3/reference/expressions.html#operator-precedence) 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. ```ts title="pratt.ts" // 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: ```bash node demo.ts ``` ```text output 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 `^`: ```text title="filter.peggy" 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](https://lark-parser.readthedocs.io/en/stable/tree_construction.html) when it matched a single child, so the tree records only the levels where an operator appeared: ```text title="filter.lark" // 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](https://lark-parser.readthedocs.io/en/stable/parsers.html) 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: ```bash node compare.ts ``` ```text output 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. ```bash node --test bench.test.ts ``` ```text output 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](https://lark-parser.readthedocs.io/en/stable/parsers.html) 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](https://nodejs.org/api/test.html). The test for prefix minus covers the shared token from both sides: ```ts title="pratt.test.ts" 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))') }) ``` ```bash node --test pratt.test.ts ``` ```text output 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: ```bash node pitfall.ts ``` ```text output 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 `^`.[^2] `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.[^3] 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](/howto/remove-left-recursion-from-a-peg-grammar) - [Attach parse actions to grammar rules by name](/howto/attach-parse-actions-by-rule-name) - [Write a recursive descent parser by hand in TypeScript](/howto/recursive-descent-parser-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. [^1]: Pratt did not claim the numbers. [His paper](https://tdop.github.io/) credits Floyd's 1963 operator precedence with storing association decisions in a table, encoded as one number per argument position. Such numbers, the paper adds, are sometimes called binding powers. The paper's contribution was to hang code on tokens rather than on grammar rules. A token may denote two codes, and the paper's own example is the one this page trips over: the null denotation of `-` is unary minus, and its left denotation is binary minus. [^2]: Conventions differ here. [Python's reference](https://docs.python.org/3/reference/expressions.html#the-power-operator) says the power operator binds more tightly than a unary operator on its left, and works the example: `-1**2` results in `-1`. [Microsoft's table for Excel](https://support.microsoft.com/en-us/excel/calculation-operators-and-precedence-in-excel) lists negation before exponentiation, so a spreadsheet negates first and squares second. Users of a filter language arrive having learned one convention or the other, which is the case for pinning `-2^2` in a test. [^3]: [The paper](https://tdop.github.io/) asks why an approach like its own had not been generally adopted. It names a "preoccupation with BNF grammars and their various offspring" as the likely cause. [Douglas Crockford's account](https://crockford.com/javascript/tdop/tdop.html), written for *Beautiful Code* and dated 2007, records that Pratt presented the paper at the first Principles of Programming Languages symposium, in Boston in 1973. Thirty-four years on, Crockford calls the approach "completely neglected today."