The Operator Carries Its Binding Power

An expression parser has to answer a local custody dispute.

In:

a + b * c

the operand b is between + and *. Does it belong to the addition on the left, or to the multiplication on the right?

Humans answer with a precedence convention. A common recursive descent parser answers by building a tower of functions:

expression -> term
term       -> factor (("+" | "-") factor)*
factor     -> power  (("*" | "/") power)*
power      -> unary  ("^" power)?
unary      -> "-" unary | primary
primary    -> number | name | "(" expression ")"

That works. It is also a little embarrassing. The grammar becomes a staircase whose shape is mostly determined by an operator table.

Pratt’s 1973 top-down operator precedence parser takes the table seriously.¹ Instead of writing one parser function per precedence level, it asks each token two questions:

nud: what do you mean when you start an expression?
led: what do you mean when an expression is already on your left?

The token - can answer both. As a nud, it is unary negation. As a led, it is binary subtraction. The token ( can start a grouped expression, and in a larger language it might also extend an expression as a function call.

Then one loop does most of the work.

function expression(rbp) {
  const t = advance();
  let left = nud(t);

  while (rbp < lbp(peek())) {
    const op = advance();
    left = led(op, left);
  }

  return left;
}

Here rbp is the right binding power requested by the caller, and lbp is the left binding power of the next token. Pratt’s original paper describes this state machine in terms of null and left denotations, and makes the binding-power comparison the point where the parser decides whether to keep extending the current expression or return to its caller.² Crockford’s JavaScript presentation uses the same compact expression(rbp) shape and helped make the technique visible to modern JavaScript readers.³

The parser is small because the hard question is not hidden. It is right there:

should the next token bind tighter than the caller's rbp?

Associativity Is A One-Number Difference

Suppose + has left binding power 10, * has 20, and ^ has 30.

For a left-associative operator such as +, the led function parses its right operand at the same binding power:

led("+", left):
  right = expression(10)
  return ["+", left, right]

That means the right operand stops before another +, because the loop tests a strict inequality:

10 < lbp("+") = 10     false

So:

a - b - c

becomes:

(- (- a b) c)

For a right-associative operator in this integer-table variant, the led function asks for the right operand at one less than its own left binding power:

led("^", left):
  right = expression(29)
  return ["^", left, right]

Now a second ^ is allowed into the right operand:

29 < lbp("^") = 30     true

So:

a ^ b ^ c

becomes:

(^ a (^ b c))

Other presentations use different numeric conventions. In Crafting Interpreters, the C bytecode compiler parses left-associative binary right operands at the next higher precedence level, while right-associative operators would use the same level.⁴ That is the same idea with a different table encoding: the recursive call chooses which future operators are allowed to join the right side.

Walk One Parse

For:

a + b * c

the standard table below uses:

+ -   lbp 10
* /   lbp 20
^     lbp 30
postfix ! lbp 40

The trace is:

expression(0)
  nud(a) -> a
  0 < lbp(+) = 10, take +
    led(+) asks for expression(10)
      nud(b) -> b
      10 < lbp(*) = 20, take *
        led(*) asks for expression(20)
          nud(c) -> c
          20 < lbp(end) = 0, stop
      return (* b c)
  return (+ a (* b c))

If + and * are deliberately assigned the same binding power, the same token stream becomes:

(* (+ a b) c)

No parser function changed. The grammar did not grow a new layer. The table changed, so the local custody dispute changed.

The Browser Lab

The lab implements a tiny expression language with names, numbers, grouping, prefix + and -, postfix !, left-associative + - * /, and switchable associativity for ^. The environment for displayed numeric values is:

a=2, b=3, c=4, d=2

The interesting control is not the example selector. It is the table selector. Use flat + and * to make addition and multiplication tie. Use left-assoc ^ to change only exponentiation’s recursive right binding power.

Expression

a + b * c

a + b * c a + b * c ^ d (a + b) * c a - b - c a ^ b ^ c -a ^ b! Binding table

standard powers

standard powers flat + and * left-assoc ^ Trace step

0 / 0

What The Default Run Checks

The default expression is:

a + b * c

With the standard table, the rendered AST is:

(+ a (* b c))

The trace contains the decisive comparison:

10 < lbp(*) = 20     take

That comparison happens inside the right operand of +. It is why the multiplication is admitted before the addition node is closed.

Switch the table to flat + and *, and the comparison changes:

20 < lbp(*) = 20     stop

The * waits for the outer call, and the AST becomes:

(* (+ a b) c)

The parser did not “forget” arithmetic. It obeyed a different local contract.

Reproducibility Check

The browser lab is also a CommonJS module:

node - <<'NODE'
const lab = require("./assets/js/pratt-parser-lab.js");
const EXPECTED_TOTALS = {
  checked: 188,
  rows: 25,
  criticalRows: 18,
  modes: 3,
  examples: 6,
  passed: 25,
  total: 25,
  passedChecks: 188,
  totalChecks: 188
};
const EXPECTED_BY_MODE = [
  "standard:11:32:57:11:86/86",
  "flat:7:32:37:7:51/51",
  "leftPower:7:32:37:7:51/51"
];
const EXPECTED_BY_EXAMPLE = [
  "grouped:4:30:20:4:30/30",
  "ladder:3:32:21:3:21/21",
  "leftChain:4:23:20:4:30/30",
  "powerChain:5:23:25:5:38/38",
  "simple:5:23:25:5:39/39",
  "unaryPostfix:4:23:20:4:30/30"
];
const EXPECTED_CRITICAL_CHECKS = [
  "AST string is non-empty:25/25:true:none",
  "evaluation is finite for the teaching environment:25/25:true:none",
  "expected AST: (* (+ a b) c):2/2:true:none",
  "expected AST: (+ a (* b c)):1/1:true:none",
  "expected AST: (- (- a b) c):1/1:true:none",
  "expected AST: (- (^ a (! b))):1/1:true:none",
  "expected AST: (^ (^ a b) c):1/1:true:none",
  "expected AST: (^ a (^ b c)):1/1:true:none",
  "expected value: -5:1/1:true:none",
  "expected value: -64:1/1:true:none",
  "expected value: 14:1/1:true:none",
  "expected value: 20:2/2:true:none",
  "expected value: 4096:1/1:true:none",
  "node and depth counts are finite:25/25:true:none",
  "parse consumed exactly the expression:25/25:true:none",
  "token stream ends with sentinel:25/25:true:none",
  "trace has a stop decision:25/25:true:none",
  "trace records nud and binding tests:25/25:true:none"
];
const EXPECTED_CASE_ROWS = [
  "1:standard / simple:simple/standard:(+ a (* b c)):5:23:14:7/7:true",
  "2:standard / ladder:ladder/standard:(+ a (* b (^ c d))):7:32:50:7/7:true",
  "3:standard / grouped:grouped/standard:(* (+ a b) c):5:30:20:7/7:true",
  "4:standard / leftChain:leftChain/standard:(- (- a b) c):5:23:-5:7/7:true",
  "5:standard / powerChain:powerChain/standard:(^ a (^ b c)):5:23:2.4178516392292583e+24:7/7:true",
  "6:standard / unaryPostfix:unaryPostfix/standard:(- (^ a (! b))):5:23:-64:7/7:true",
  "7:flat / simple:simple/flat:(* (+ a b) c):5:23:20:7/7:true",
  "8:flat / ladder:ladder/flat:(* (+ a b) (^ c d)):7:32:80:7/7:true",
  "9:flat / grouped:grouped/flat:(* (+ a b) c):5:30:20:7/7:true",
  "10:flat / leftChain:leftChain/flat:(- (- a b) c):5:23:-5:7/7:true",
  "11:flat / powerChain:powerChain/flat:(^ a (^ b c)):5:23:2.4178516392292583e+24:7/7:true",
  "12:flat / unaryPostfix:unaryPostfix/flat:(- (^ a (! b))):5:23:-64:7/7:true",
  "13:leftPower / simple:simple/leftPower:(+ a (* b c)):5:23:14:7/7:true",
  "14:leftPower / ladder:ladder/leftPower:(+ a (* b (^ c d))):7:32:50:7/7:true",
  "15:leftPower / grouped:grouped/leftPower:(* (+ a b) c):5:30:20:7/7:true",
  "16:leftPower / leftChain:leftChain/leftPower:(- (- a b) c):5:23:-5:7/7:true",
  "17:leftPower / powerChain:powerChain/leftPower:(^ (^ a b) c):5:23:4096:7/7:true",
  "18:leftPower / unaryPostfix:unaryPostfix/leftPower:(- (^ a (! b))):5:23:-64:7/7:true",
  "19:standard multiplication binds tighter:simple/standard:(+ a (* b c)):5:23:14:9/9:true",
  "20:flat table changes the tree:simple/flat:(* (+ a b) c):5:23:20:9/9:true",
  "21:parentheses override table:grouped/standard:(* (+ a b) c):5:30:20:9/9:true",
  "22:minus chains associate left:leftChain/standard:(- (- a b) c):5:23:-5:9/9:true",
  "23:power chains associate right:powerChain/standard:(^ a (^ b c)):5:23:2.4178516392292583e+24:8/8:true",
  "24:left power mode changes only caret:powerChain/leftPower:(^ (^ a b) c):5:23:4096:9/9:true",
  "25:prefix and postfix compose through rbp:unaryPostfix/standard:(- (^ a (! b))):5:23:-64:9/9:true"
];

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

function rowDrifts(actualRows, expectedRows) {
  const drifts = [];
  const rows = Math.max(actualRows.length, expectedRows.length);
  for (let index = 0; index < rows; index += 1) {
    const actual = index < actualRows.length ? actualRows[index] : null;
    const expected = index < expectedRows.length ? expectedRows[index] : null;
    if (!sameJson(actual, expected)) {
      drifts.push({ index, actual, expected });
    }
  }
  return drifts;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const totals = {
  checked: audit.checked,
  rows: audit.cases.length,
  criticalRows: audit.criticalChecks.length,
  modes: audit.byMode.length,
  examples: audit.byExample.length,
  passed: audit.passed,
  total: audit.total,
  passedChecks: audit.passedChecks,
  totalChecks: audit.totalChecks
};
const byModeRows = audit.byMode.map((row) =>
  `${row.mode}:${row.cases}:${row.maxTraceSteps}:${row.nodes}:` +
  `${row.passed}:${row.passedChecks}/${row.totalChecks}`
);
const byExampleRows = audit.byExample.map((row) =>
  `${row.example}:${row.cases}:${row.maxTraceSteps}:${row.nodes}:` +
  `${row.passed}:${row.passedChecks}/${row.totalChecks}`
);
const criticalRows = audit.criticalChecks.map((row) =>
  `${row.check}:${row.passed}/${row.total}:${row.ok}:` +
  `${row.failedCases.join(",") || "none"}`
);
const caseRows = audit.cases.map((row) =>
  `${row.caseId}:${row.name}:${row.example}/${row.mode}:${row.ast}:` +
  `${row.nodes}:${row.traceSteps}:${String(row.value)}:` +
  `${row.passedChecks}/${row.totalChecks}:${row.passed}`
);
const byModeDrifts = rowDrifts(byModeRows, EXPECTED_BY_MODE);
const byExampleDrifts = rowDrifts(byExampleRows, EXPECTED_BY_EXAMPLE);
const criticalDrifts = rowDrifts(criticalRows, EXPECTED_CRITICAL_CHECKS);
const caseRowDrifts = rowDrifts(caseRows, EXPECTED_CASE_ROWS);
const driftShape = {
  totals,
  byModeDrifts,
  byExampleDrifts,
  criticalDrifts,
  caseRowDrifts
};
const shapeErrors = [
  sameJson(totals, EXPECTED_TOTALS) ? null : "totals",
  byModeDrifts.length === 0 ? null : "byModeRows",
  byExampleDrifts.length === 0 ? null : "byExampleRows",
  criticalDrifts.length === 0 ? null : "criticalRows",
  caseRowDrifts.length === 0 ? null : "caseRows"
].filter(Boolean);
console.table(audit.byMode);
console.table(audit.byExample);
console.table(audit.criticalChecks);
if (shapeErrors.length) {
  throw new Error(
    `Pratt parser audit shape drifted in ${shapeErrors.join(", ")}:\n` +
    JSON.stringify(driftShape, null, 2)
  );
}
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  failed.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(`${summary}: ${JSON.stringify(failed, null, 2)}`);
}
console.log(summary);
NODE

The current audit grid has 25 cases and 188 individual checks. It verifies:

• every example under all three binding tables;
• standard multiplication binding tighter than addition;
• the deliberate flat-table parse change;
• parentheses overriding the table;
• left-associative subtraction chains;
• right-associative and left-associative exponent chains;
• prefix and postfix composition in -a ^ b!;
• full token consumption;
• finite evaluation in the displayed teaching environment; and
• the presence of both nud events and binding-power stop decisions in the trace.

The implementation is intentionally small: assets/js/pratt-parser-lab.js.

Where The Toy Stops

This is not a full language front end.

The tokenizer is tiny. Error recovery is fail-fast. There are no assignments, calls, subscripts, ternaries, statement forms, or contextual keywords. A serious compiler also has to decide how parsing interacts with types, scopes, diagnostics, incremental editing, and source spans.

That said, Pratt parsing scales surprisingly well into real tools. Crockford used a TDOP parser style in his JavaScript work.³ Nystrom’s articles and Crafting Interpreters present the same family of ideas as parselets and parse-rule tables, which make it easy to see which tokens can start or extend an expression.⁵⁴ Desmos has also written publicly about adopting Pratt parsing for mathematical expressions in the browser.⁶

The core reason is the same reason the toy is useful: expression syntax is not only a context-free grammar problem. It is a table of small token-local behaviors plus a binding comparison. When that table is visible, changes to the language become auditable:

which tokens can start?
which tokens can extend?
how tightly do they hold the expression on their right?

That is a good interface between language design and parser implementation.

1. Vaughan R. Pratt, “Top Down Operator Precedence”, originally presented at POPL 1973. ACM DOI: 10.1145/512927.512931. ↩

2. Pratt’s implementation section introduces the rbp < lbp test and the nud / led split for tokens with and without a preceding expression. See “Top Down Operator Precedence”, Section 3. ↩

3. Douglas Crockford, “Top Down Operator Precedence”, 2007. ↩ ↩²

4. Bob Nystrom, “Compiling Expressions”, Crafting Interpreters. ↩ ↩²

5. Bob Nystrom, “Pratt Parsers: Expression Parsing Made Easy”, 2011. ↩

6. Desmos Engineering, “How Desmos uses Pratt Parsers”, 2018. ↩