The Compiler — AST to Bytecode

A Compiler With No AST

Tree-walking interpreters build a full AST and then walk it at runtime. A bytecode compiler can skip the intermediate tree entirely: parse and emit in the same pass. As the parser recognizes each expression, it directly writes opcodes into the current Chunk. No Expr node classes, no second traversal — the recursive-descent parser is the code generator.

This only works cleanly for expressions because expressions have a strict precedence hierarchy, and that's exactly what a Pratt parser encodes.

Pratt Parsing in One Picture

Every token that can start or continue an expression gets two roles:

• a prefix handler — how to parse it when it appears at the start of an expression (-5, (1+2), a number literal, a string literal)
• an infix handler — how to parse it when it appears after another expression (a + b, a < b), paired with a precedence level

The loop is the whole trick: as long as the next operator binds at least as tightly as what the caller asked for, keep consuming it as part of the current expression. 1 + 2 * 3 parses correctly because * has higher precedence than +, so after emitting 1, the + handler recurses into parse_precedence(PREC_FACTOR) for its right operand, which slurps up 2 * 3 before returning control to the outer +.

Literals and Grouping

Numbers, strings, true/false/nil are the simplest case: look at the previous token's lexeme, wrap it as a Value, add it to the chunk's constant pool, and emit OP_CONSTANT <index> (or a dedicated OP_NIL / OP_TRUE / OP_FALSE — no constant slot wasted on a value the VM can synthesize with zero operands).

( expr ) is a prefix rule too — it just recurses:

Note that grouping emits no opcode of its own — parentheses only affect parsing order, not runtime behavior.

Unary and Binary Operators

unary() parses the operator, recursively parses its operand at PREC_UNARY, then emits the opcode after the operand — bytecode is stack-based, so operands must already be on the stack before the operator that consumes them:

binary() is the infix handler: it already has the left operand on the stack (emitted before we got here), so it parses the right operand at one precedence level higher than its own (for left-associativity), then emits the operator:

What to build

Wire a precedence table (token type → prefix fn, infix fn, precedence), then implement number, string, literal (true/false/nil), grouping, unary, and binary on top of it. Feed COMPILE "1 + 2 * (3 - 1)" through and confirm the emitted bytecode, when run by your VM from the previous chapter, produces 5. Watch operator precedence edge cases like -2 * 3 (unary binds tighter than *) and right-side unary in binary expressions like 1 - -1.