33. Pratt parsing

A ladder with too many rungs

In chapter 32 you parsed expressions by recursive descent, with one function per precedence level. Each function handles its own operators and calls the next, tighter level for its operands. It works, and it reads just like the grammar.

Now count what happens when it parses the lone number 7. Drip has six levels of binary operators (or, and, equality, comparison, + -, * /), then unary, then calls. Every level’s function is entered, finds no operator, and returns, before anyone reaches the 7. And adding an operator means adding a rung to the ladder.

The real Drip parser in companion/ts/src/parser.ts reads expressions differently: with one small table of numbers and one loop. The technique is named after Vaughan Pratt, who described it in 1973 as “top down operator precedence”^[2].

Binding power

The strength of each magnet is a number:

Here is the same table as it appears in the code:

// companion/ts/src/parser.ts (excerpt)
const BP = {
  or: 1,
  and: 2,
  '==': 3, '!=': 3,
  '<': 4, '<=': 4, '>': 4, '>=': 4,
  '+': 5, '-': 5,
  '*': 6, '/': 6,
  '(': 8, '.': 8,
};
const UNARY_BP = 7;

The whole precedence ladder from chapter 32 is now data. A new operator is one more line in a table, not one more function.

Prefix and infix

One more idea before the loop. The parser meets a token in one of two situations. Either it has nothing yet, and is looking for the start of an operand: a number, a name, a (, or a - as in -x. Or it already holds a finished operand, and the token comes after it: a +, a *, or a - as in a - b.

function prefix(): Expr {
  if (match('!', '-')) {
    const operator = previous();
    const right = pratt(UNARY_BP);
    return {
      kind: 'unary', operator, right,
    };
  }
  return primary(); // number, name, ( … )
}

The parser never has to guess what a - means. If it holds no left operand yet, the - must be “negate”. If it does, it must be “subtract”. In Drip a call f(x) and a property access p.x are infix too: ( and . come after an operand, with binding power 8, the strongest of all. A ( at the start of an operand is grouping instead.

The loop

Here is the heart of the parser, nearly as it is in the repository:

function pratt(minBp: number): Expr {
  let left = prefix();
  for (;;) {
    const bp = BP[peek().type];
    if (bp === undefined || bp <= minBp)
      break;
    const op = advance();
    left = infix(left, op, bp);
  }
  return left;
}

For an ordinary binary operator, infix builds a node whose right side is another call to pratt, passing the operator’s own binding power:

// inside infix(left, op, bp)
return {
  kind: 'binary', left, operator: op,
  right: pratt(bp),
};

Read minBp as a promise to the caller: “I am the right operand of an operator this strong, so I only take operators that are stronger.” The first call, pratt(0), has no such operator, so it takes everything. Step through it on 1 + 2 * 3 - 4:

function pratt(minBp) {
  let left = prefix();
  for (;;) {
    const bp = BP[peek().type];
    if (!bp || bp <= minBp) break;
    const op = advance();
    left = infix(left, op, bp);
  }
  return left;
}
// infix: { left, op, right: pratt(bp) }

Notice the order the tree forms in. The * node is built first, from the inside out, even though + came first in the text. The call stack holds the unfinished + while the * finishes.

Grouping, one number at a time

Left associativity falls out of that <=. In 1 - 2 - 3, the right operand of the first - is parsed by pratt(5). When it meets the second -, also 5, the test 5 <= 5 stops it, so it returns only 2. The first - becomes (- 1 2), and the outer loop then takes the second -: (- (- 1 2) 3), which is -4.

Unary minus calls pratt(7). That is stronger than *, so -2 * 3 groups as (* (- 2) 3). Run these and check each grouping in your head:

print 1 + 2 * 3 - 4;
print 1 - 2 - 3;
print -2 * 3;
print (1 + 2) * 3;
print 2 * 3 == 6;
print 8 / 4 / 2;

To make an operator group to the right instead, parse its right side with bp - 1. Then an equal operator on the right is stronger than the promise, and it nests inward. You will do exactly that in the extra exercise.

Drip’s one right-associative operator, =, is handled just outside the loop:

function assignment(): Expr {
  const expr = pratt(0);
  if (match('=')) {
    const value = assignment();
    if (expr.kind === 'variable')
      return { kind: 'assign',
        name: expr.name, value };
    // a.b = … becomes a 'set' node
    // anything else: an error
  }
  return expr;
}

There are two reasons. Calling assignment() again for the value makes a = b = 5 nest to the right. And the left side has to be checked after it is parsed: in a + b = 3, the parser reads a + b before it sees the =, and only then learns the target is not a name. That error is the next chapter’s business.

Your turn

The core exercise is the whole Pratt loop in miniature: plain JavaScript, tokens as strings, nodes as arrays. The extra one adds a right-associative power operator.

const BP = { '+': 5, '-': 5,
  '*': 6, '/': 6 };

function parse(ts) {
  let i = 0;
  function pratt(minBp) {
    let left = ts[i++];
    // your loop here
    return left;
  }
  return pratt(0);
}

const BP = { '+': 5, '-': 5,
  '*': 6, '/': 6, '^': 7 };

function parse(ts) {
  let i = 0;
  function pratt(minBp) {
    let left = ts[i++];
    for (;;) {
      const bp = BP[ts[i]];
      if (!bp || bp <= minBp) break;
      const op = ts[i++];
      left = [op, left, pratt(bp)];
    }
    return left;
  }
  return pratt(0);
}

What you learned

• A binding power says how tightly an operator holds its operands. The higher number wins a contested operand.
• A Pratt parser replaces the ladder of precedence functions with a table and one loop: parse a prefix, then keep absorbing infix operators whose power is greater than minBp.
• The right operand of an operator is parsed with that operator’s power as the new minBp, so it only takes tighter operators.
• bp <= minBp stops on equals, which makes operators left-associative. Recursing with bp - 1 makes one right-associative.
• In Drip, calls and . are infix operators, and assignment is parsed just outside the loop so its target can be checked.

Next: what the parser does when the tokens make no sense at all.