Write a Compiler from Expressions to Bytecode

Compiling to Bytecode

A compiler walks source text and emits opcodes your VM already understands. Recursive descent is the standard approach for small languages: one parsing function per grammar rule, each emitting instructions as it goes.

Code Generation Patterns

Expression compilation is postfix-friendly on a stack VM:

Literals: emit `PUSH` or `LOAD_CONST`
Binary ops: compile left, compile right, emit `ADD`/`MUL`/etc.
`3 + 4 * 5` becomes `PUSH 3; PUSH 4; PUSH 5; MUL; ADD` (right operand first for left-associative ops)

Control flow needs jump patching:

Emit `JUMP_IF_FALSE` with a placeholder offset
Compile the `then` block
Emit `JUMP` past the `else`
Patch the false label, compile `else`, patch the end label

For example, `if 10 > 5 print 1 else print 0` compiles to a comparison, conditional jump, two print blocks, and two patched addresses.

This pipeline mirrors CPython's `compile.c` and Bob Nystrom's clox compiler in Crafting Interpreters.

Design Notes

Emit instructions in a single pass where possible, but keep the bytecode buffer growable. Real compilers use chunked buffers or vectors because function size is not known until parsing finishes. Reserve space for jump operands when you emit branch placeholders.

For This Exercise

This exercise asks you to build a tokenizer, recursive-descent parser, and bytecode emitter with jump backpatching. You will implement compilation for arithmetic, `if/else`, and `print`, then run the result in your interpreter.

Write a compiler that translates simple expressions and statements into your VM's bytecode in C.

Requirements:

Implement a tokenizer that recognizes numbers, operators (+, -, *, /, (, )), keywords (if, else, print), and semicolons
Implement a recursive descent parser with functions: parse_program(), parse_statement(), parse_if(), parse_print(), parse_expression(), parse_term(), parse_factor()
Implement emit_byte() and emit_bytes() to write opcodes into a bytecode array
Implement emit_jump() that writes JUMP_IF_FALSE with a placeholder offset, returning the offset for later patching
Implement patch_jump() that fills in the target address of a previously emitted jump
Compile expressions using the constant pool with OP_LOAD_CONST
After compilation, run the bytecode in your VM's interpreter loop
Demonstrate compiling and running: "print 3 + 4 * 5;" and "if 10 > 5 print 1 else print 0;"
Print the generated bytecode as human-readable instructions

Test:

Show compiler output
Show generated bytecode with opcodes and operands
Show expression compilation
Show emit operations adding instructions to the bytecode array

Compiling to Bytecode

Code Generation Patterns

Expression compilation is postfix-friendly on a stack VM:

Literals: emit `PUSH` or `LOAD_CONST`
Binary ops: compile left, compile right, emit `ADD`/`MUL`/etc.
`3 + 4 * 5` becomes `PUSH 3; PUSH 4; PUSH 5; MUL; ADD` (right operand first for left-associative ops)

Control flow needs jump patching:

Emit `JUMP_IF_FALSE` with a placeholder offset
Compile the `then` block
Emit `JUMP` past the `else`
Patch the false label, compile `else`, patch the end label

For example, `if 10 > 5 print 1 else print 0` compiles to a comparison, conditional jump, two print blocks, and two patched addresses.

This pipeline mirrors CPython's `compile.c` and Bob Nystrom's clox compiler in Crafting Interpreters.

Design Notes

For This Exercise

Write a compiler that translates simple expressions and statements into your VM's bytecode in C.

Requirements:

Implement a tokenizer that recognizes numbers, operators (+, -, *, /, (, )), keywords (if, else, print), and semicolons
Implement a recursive descent parser with functions: parse_program(), parse_statement(), parse_if(), parse_print(), parse_expression(), parse_term(), parse_factor()
Implement emit_byte() and emit_bytes() to write opcodes into a bytecode array
Implement emit_jump() that writes JUMP_IF_FALSE with a placeholder offset, returning the offset for later patching
Implement patch_jump() that fills in the target address of a previously emitted jump
Compile expressions using the constant pool with OP_LOAD_CONST
After compilation, run the bytecode in your VM's interpreter loop
Demonstrate compiling and running: "print 3 + 4 * 5;" and "if 10 > 5 print 1 else print 0;"
Print the generated bytecode as human-readable instructions

Test:

Show compiler output
Show generated bytecode with opcodes and operands
Show expression compilation
Show emit operations adding instructions to the bytecode array

Topic Overview

Compiling to Bytecode

Code Generation Patterns

Design Notes

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source

Write a Compiler from Expressions to Bytecode

Topic Overview

Compiling to Bytecode

Code Generation Patterns

Design Notes

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source