1 + 2 * 3 is not left to right
Tokens are a flat list, but programs have structure: in 1 + 2 * 3 the multiplication happens first. The parser turns tokens into a syntax tree that makes this explicit. We'll write trees in a bracketed form, so 1 + 2 * 3 shows as (1 + (2 * 3)) — every pair of brackets is one node.
{ type: "Infix", op: "+",
left: { type: "Number", value: 1 },
right: { type: "Infix", op: "*",
left: { type: "Number", value: 2 },
right: { type: "Number", value: 3 } } }Binding power
A Pratt parser gives every infix operator a number: its precedence, or binding power. == is 1, comparisons 2, +/- 3, *///% 4. Prefix operators (-x, !x) bind at 5, tighter than any infix operator. One function, expression(min), parses a prefix piece and then keeps folding in operators that bind tighter than min.
function expression(min) {
let left = prefix();
while ((PRECEDENCE[peek().type] ?? 0) > min) {
const op = next();
left = { type: "Infix", op: op.type, left, right: expression(PRECEDENCE[op.type]) };
}
return left;
}Parsing the right side at the same level (not one higher) with a strict > makes equal operators group to the left: a - b - c becomes ((a - b) - c).