A parser's job is to turn a flat sequence of tokens into a tree that reflects how the expression is actually structured -- 2 + 3 * 4 has to become "add 2 to (3 times 4)", not "multiply (2 plus 3) by 4". Recursive-descent parsing gets this right by encoding precedence directly into the call structure: each precedence level is its own function, and higher precedence means a deeper function call.

Tokens are a flat list: numbers, operator strings ("+" "-" "*" "/" "^"), and parenthesis strings ("(" ")"). Build an AST from two node shapes:

• ("num", value) -- a literal
• ("binop", op, left, right) -- a binary operation

Implement parse(tokens) following this grammar:

expr   := term (('+' | '-') term)*
term   := power (('*' | '/') power)*
power  := factor ('^' power)?
factor := NUMBER | '(' expr ')'

Example

parse([2, "+", 3, "*", 4])
# -> ("binop", "+", ("num", 2), ("binop", "*", ("num", 3), ("num", 4)))

Note * ends up NESTED INSIDE the + node, on the right -- that's precedence encoded structurally: to evaluate the tree, you evaluate the multiplication first because it's deeper.

The missing link: not every operator associates the same way

+, -, *, / are all left-associative -- 10 - 2 - 3 means (10 - 2) - 3. Every precedence level above handles this the same way: parse one operand, then LOOP, consuming more operators and wrapping the running result on the left each time.

^ (exponentiation) is different: it's right-associative. 2 ^ 3 ^ 2 means 2 ^ (3 ^ 2) (= 512), not (2 ^ 3) ^ 2 (= 64) -- mathematically, and in every real language that has this operator (Python's own ** included). A loop like the other levels use would build the WRONG tree here. The fix is structural, not a special case bolted on: power recurses back into itself on the right ('^' power, not ('^' factor)*), so the rightmost ^ ends up shallowest and the leftmost ends up deepest -- exactly backwards from how the loop-based levels nest, and exactly what right-associativity requires.

Constraints

• +/-/*// are left-associative: 10 - 2 - 3 must parse as (10 - 2) - 3.
• ^ is right-associative and binds tighter than *//: 2 * 3 ^ 2 must parse as 2 * (3 ^ 2), and 2 ^ 3 ^ 2 must parse as 2 ^ (3 ^ 2).
• Parenthesized subexpressions override precedence entirely -- parse_factor recursing back into parse_expr on ( is what makes this work.

Real-world grounding

• TypeScript's parser (same recursive-descent, precedence-climbing shape, a lot more grammar): src/compiler/parser.ts

Real parsers add a lot on top of this: error recovery (don't just crash on bad input), source location tracking for error messages, and often many more precedence levels -- but the core "one function per precedence level, each calling into the next tighter one" technique, loop for left-associative and recursion for right-associative, is exactly what you're building here.