Write a Compiler from Expressions to Bytecode

Topic Overview

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:

1. Emit `JUMP_IF_FALSE` with a placeholder offset
2. Compile the `then` block
3. Emit `JUMP` past the `else`
4. 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.

Your Task

Write a single-pass compiler from a tiny language to this subtrack's stack bytecode, then run the result. The compiler has a tokenizer, a recursive-descent parser with correct precedence, variables mapped to local slots, and if/else and while compiled to labels and conditional jumps. It prints the generated assembly, then the program's output.

Language

cCopy
Loading…

Expressions from lowest to highest precedence: one optional comparison (<, >, ==, non-associative), then + - (left-associative), then * / (left-associative), then unary - and primaries: integers (0..2147483647), variables and ( expr ).

Code generation

Labels are numbered L0, L1, … in the order they are allocated: if allocates its else label first (and its end label only when an else follows), and while allocates top then end. The program ends with HALT.

Output

The listing (instructions indented two spaces, labels on their own lines), then ; N instructions, V variables (labels are not counted), --- run ---, and the program's output. At run time, int32 arithmetic wraps, INT_MIN / -1 gives INT_MIN, and division by zero prints runtime error: division by zero.

Compile errors stop everything and print one line, error at OFFSET: MESSAGE, where OFFSET is the character position in the input (0-based):

• unexpected character C
• number too large
• expected 'X' but found TOKEN (TOKEN is end of input at the end)
• expected an expression but found TOKEN
• expected a statement but found TOKEN
• expected a variable name but found TOKEN
• undeclared variable NAME
• variable already declared: NAME
• too many variables (8 max): NAME

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. One function per precedence level (expr → sum → term → primary), each emitting code as it parses.
2. Allocate labels before emitting the jumps that use them, and place them when their position is reached.

Hidden tests cover nested if inside while, if without else, precedence and left-associativity (10 - 3 - 2, 2 + 3 * 4), unary minus, division by zero at run time, and a compile error for a redeclared variable.