Operator Precedence

The flat token problem.

The lexer gives us tokens in order. But order alone doesn't tell us grouping. Consider:

a + b * c - d

Four tokens, three operators. Which operations happen first? In math class, you learned PEMDAS — multiplication before addition. But the parser doesn't know PEMDAS. It needs a systematic way to encode these rules into the tree it builds.

The answer: precedence levels. Each operator gets a number. Higher number = binds tighter = goes deeper in the tree. The parser uses these numbers to decide which operators "grab" their operands first.

Monk's 13 precedence levels.

From loosest (evaluated last) to tightest (evaluated first):

Level 1 is the loosest — assignment happens after everything else on the right side is computed. Level 13 is the tightest — function calls and property access bind before any arithmetic.

Left vs right associativity.

Precedence tells you which operator goes first when they're different. Associativity tells you which goes first when they're the same.

Left-associative (most operators): a - b - c means (a - b) - c. The leftmost operation happens first.

Right-associative (assignment, unary): a = b = c would mean a = (b = c). The rightmost operation happens first. But in Monk, assignment is a statement — you can't chain assignments like this. Unary operators are naturally right-associative: --x means -(-(x)).

The left subtree is deeper. The left subtraction evaluates first: 8 - 3 = 5, then 5 - 2 = 3. If it were right-associative, you'd get 8 - (3 - 2) = 7 — wrong answer.

How recursive descent encodes precedence.

The elegant trick: write one function per precedence level. Each function handles operators at its level, and calls the next-higher-level function for its operands. This naturally creates the right tree shape.

// Level 10: addition and subtraction
func parseAddition() Node {
    left := parseMultiplication()  // call the next level up
    while currentToken is PLUS or MINUS {
        op := consume()
        right := parseMultiplication()
        left = BinaryExpr(left, op, right)
    }
    return left
}

// Level 11: multiplication and division
func parseMultiplication() Node {
    left := parseUnary()  // call the next level up
    while currentToken is STAR or SLASH or PERCENT {
        op := consume()
        right := parseUnary()
        left = BinaryExpr(left, op, right)
    }
    return left
}

When parseAddition needs an operand, it calls parseMultiplication. That function will consume any * or / operators before returning. So by the time parseAddition builds its node, all the multiplications are already buried deeper in the tree.

Tracing through a + b * c - d.

Let's trace the recursive calls step by step:

The key moment: when parseAddition asks for the right operand of +, it calls parseMultiplication, which gobbles up the b * c into a single node. By the time control returns to parseAddition, the multiplication is already done and wrapped in a subtree.

Precedence climbing vs Pratt parsing.

What we described above — one function per level, each calling the next — is called precedence climbing. It's the most natural approach in recursive descent parsers.

An alternative is Pratt parsing (also called "top-down operator precedence"). Instead of one function per level, you have a single function with a precedence parameter. Operators register their binding power in a table, and the parser uses the table to decide when to stop.

Both produce identical trees. The difference is code organization, not output. Monk chose precedence climbing because each level is a simple function you can set a breakpoint in. When something parses wrong, you know exactly which level to look at.

Key takeaways