The parse tree from Week 10 is a faithful representation of the source program's structure, but it contains no information about where variables live, what types they have, or how to access them. Code generation adds two things the parse tree lacks: a symbol table that tracks every variable and its VM-level storage location, and a tree-walker that converts each parse-tree node into one or more VM commands. The result is VM bytecode — the output of the compiler's back end.
Reading
- Petzold Ch 22 ("Operating Systems," pp. 320-332) second visit: Petzold describes how the OS manages memory allocation. The
Memory.alloccall your generated code will emit fornewexpressions is exactly what Petzold describes — the runtime counterpart of the static symbol table you build this week. (~12 pages) - Petzold Ch 24 ("Languages High and Low," pp. 347-360) second visit: The code-generation section of Petzold's compiler chapter. He walks through how a high-level expression maps to machine instructions; your code generator does the same mapping, one level of abstraction higher (to VM bytecode rather than machine code). (~14 pages)
Lecture
3 hours. Key arc:
The symbol table. Every variable in a VirtusLang program has a kind (static, field, local, argument), a type (int, char, boolean, or a class name), and an index within its kind's VM segment:
from dataclasses import dataclass
from enum import Enum, auto
class VarKind(Enum):
STATIC = 'static'
FIELD = 'field'
LOCAL = 'local'
ARGUMENT = 'argument'
@dataclass
class VarInfo:
kind: VarKind
type_: str
index: int
class SymbolTable:
"""Two-scope symbol table: class scope + subroutine scope."""
def __init__(self):
self._class_scope: dict[str, VarInfo] = {}
self._subroutine_scope: dict[str, VarInfo] = {}
self._counts = {k: 0 for k in VarKind}
def start_subroutine(self):
"""Reset the subroutine scope; called at the start of each subroutine."""
self._subroutine_scope = {}
self._counts[VarKind.LOCAL] = 0
self._counts[VarKind.ARGUMENT] = 0
def define(self, name: str, type_: str, kind: VarKind):
"""Register a variable. Class vars go in class scope; others in subroutine scope."""
info = VarInfo(kind=kind, type_=type_, index=self._counts[kind])
self._counts[kind] += 1
if kind in (VarKind.STATIC, VarKind.FIELD):
self._class_scope[name] = info
else:
self._subroutine_scope[name] = info
def lookup(self, name: str) -> VarInfo | None:
"""Look up a variable: subroutine scope first, then class scope."""
return (self._subroutine_scope.get(name) or
self._class_scope.get(name))
def var_count(self, kind: VarKind) -> int:
return self._counts[kind]
def kind_of(self, name: str) -> VarKind | None:
info = self.lookup(name)
return info.kind if info else None
def type_of(self, name: str) -> str | None:
info = self.lookup(name)
return info.type_ if info else None
def index_of(self, name: str) -> int | None:
info = self.lookup(name)
return info.index if info else None
The VM segment mapping. Symbol kinds map to VM segments:
| Kind | VM segment |
|---|---|
STATIC |
static |
FIELD |
this (object fields via this pointer) |
LOCAL |
local |
ARGUMENT |
argument |
The code generator. Walks the parse tree and emits VM commands:
class CodeGen:
"""
Walks a parse tree (from Parser) and emits VM bytecode lines.
Maintains a SymbolTable, a class name, and a label counter for
unique if/while labels.
"""
def __init__(self):
self.sym = SymbolTable()
self.class_name = ''
self._label_count = 0
self.output: list[str] = []
def _new_label(self, prefix='L') -> str:
label = f"{prefix}_{self._label_count}"
self._label_count += 1
return label
def _emit(self, *lines: str):
self.output.extend(lines)
# --- Class-level compilation ---
def compile_class(self, node):
self.class_name = node.children[0].value # className node
self.sym = SymbolTable()
for child in node.children[1:]:
if child.tag == 'classVarDec':
self.compile_class_var_dec(child)
elif child.tag == 'subroutineDec':
self.compile_subroutine(child)
def compile_class_var_dec(self, node):
kind_str = node.children[0].value # 'static' or 'field'
kind = VarKind.STATIC if kind_str == 'static' else VarKind.FIELD
type_ = node.children[1].value
for child in node.children[2:]:
if child.tag == 'varName':
self.sym.define(child.value, type_, kind)
def compile_subroutine(self, node):
self.sym.start_subroutine()
subroutine_kind = node.children[0].value # constructor|function|method
return_type = node.children[1].value
name = node.children[2].value
params = node.children[3] # parameterList
body = node.children[4] # subroutineBody
# For methods, 'this' is argument[0]
if subroutine_kind == 'method':
self.sym.define('this', self.class_name, VarKind.ARGUMENT)
self._compile_parameter_list(params)
# Count locals from varDecs in body
var_decs = [c for c in body.children if c.tag == 'varDec']
n_locals = sum(len([c for c in v.children if c.tag == 'varName']) for v in var_decs)
fn_name = f"{self.class_name}.{name}"
self._emit(f"function {fn_name} {n_locals}")
# Constructor: allocate object memory
if subroutine_kind == 'constructor':
n_fields = self.sym.var_count(VarKind.FIELD)
self._emit(f"push constant {n_fields}",
"call Memory.alloc 1",
"pop pointer 0") # set 'this'
elif subroutine_kind == 'method':
self._emit("push argument 0",
"pop pointer 0") # set 'this' from arg[0]
self._compile_subroutine_body(body)
def _compile_parameter_list(self, node):
children = [c for c in node.children]
i = 0
while i < len(children):
type_ = children[i].value; i += 1
name = children[i].value; i += 1
self.sym.define(name, type_, VarKind.ARGUMENT)
def _compile_subroutine_body(self, node):
for child in node.children:
if child.tag == 'varDec':
kind = VarKind.LOCAL
type_ = child.children[0].value
for c in child.children[1:]:
if c.tag == 'varName':
self.sym.define(c.value, type_, kind)
elif child.tag == 'statements':
self._compile_statements(child)
# --- Statements ---
def _compile_statements(self, node):
for stmt in node.children:
tag = stmt.tag
if tag == 'letStatement': self._compile_let(stmt)
elif tag == 'ifStatement': self._compile_if(stmt)
elif tag == 'whileStatement': self._compile_while(stmt)
elif tag == 'doStatement': self._compile_do(stmt)
elif tag == 'returnStatement': self._compile_return(stmt)
def _compile_let(self, node):
var_name_node = node.children[0]
is_array = any(c.tag == 'arrayAccess' for c in node.children)
# Simple case: let x = expr
expr = node.children[-1]
self._compile_expression(expr)
self._push_pop_var(var_name_node.value, push=False)
def _compile_if(self, node):
l_false = self._new_label('IF_FALSE')
l_end = self._new_label('IF_END')
cond = node.children[0]
self._compile_expression(cond)
self._emit("not", f"if-goto {l_false}")
if_stmts = node.children[1]
self._compile_statements(if_stmts)
self._emit(f"goto {l_end}", f"label {l_false}")
if len(node.children) > 2: # else branch
self._compile_statements(node.children[2])
self._emit(f"label {l_end}")
def _compile_while(self, node):
l_top = self._new_label('WHILE_TOP')
l_end = self._new_label('WHILE_END')
self._emit(f"label {l_top}")
self._compile_expression(node.children[0])
self._emit("not", f"if-goto {l_end}")
self._compile_statements(node.children[1])
self._emit(f"goto {l_top}", f"label {l_end}")
def _compile_do(self, node):
self._compile_subroutine_call(node.children[0])
self._emit("pop temp 0") # discard return value
def _compile_return(self, node):
if node.children:
self._compile_expression(node.children[0])
else:
self._emit("push constant 0") # void function: return 0
self._emit("return")
# --- Expressions ---
def _compile_expression(self, node):
children = node.children
self._compile_term(children[0])
i = 1
while i < len(children):
op = children[i].value; i += 1
term = children[i]; i += 1
self._compile_term(term)
# Map operator to VM command
op_map = {
'+': 'add', '-': 'sub', '&': 'and', '|': 'or',
'<': 'lt', '>': 'gt', '=': 'eq',
'*': 'call Math.multiply 2',
'/': 'call Math.divide 2',
}
self._emit(op_map[op])
def _compile_term(self, node):
tag = node.tag
if tag == 'integerConstant':
self._emit(f"push constant {node.value}")
elif tag == 'keywordConstant':
if node.value == 'true':
self._emit("push constant 0", "not")
elif node.value in ('false', 'null'):
self._emit("push constant 0")
elif node.value == 'this':
self._emit("push pointer 0")
elif tag == 'stringConstant':
s = node.value
self._emit(f"push constant {len(s)}", "call String.new 1")
for ch in s:
self._emit(f"push constant {ord(ch)}", "call String.appendChar 2")
elif tag == 'varName':
self._push_pop_var(node.value, push=True)
elif tag == 'unaryOp':
self._compile_term(node.children[0])
self._emit("not" if node.value == '~' else "neg")
elif tag == 'parenExpr':
self._compile_expression(node.children[0])
elif tag == 'subroutineCall':
self._compile_subroutine_call(node)
def _compile_subroutine_call(self, node):
children = node.children
if children[0].tag == 'function':
# Unqualified call: method on current object
fn_name = f"{self.class_name}.{children[0].value}"
self._emit("push pointer 0") # push 'this'
expr_list = children[1]
n_args = self._compile_expression_list(expr_list) + 1 # +1 for 'this'
self._emit(f"call {fn_name} {n_args}")
else:
# Qualified: Foo.bar(...) or obj.bar(...)
receiver = children[0].value
method = children[1].value
expr_list = children[2]
info = self.sym.lookup(receiver)
if info:
# 'receiver' is a variable; call on its object
self._push_pop_var(receiver, push=True)
fn_name = f"{info.type_}.{method}"
n_args = self._compile_expression_list(expr_list) + 1
self._emit(f"call {fn_name} {n_args}")
else:
# 'receiver' is a class name (static/constructor call)
fn_name = f"{receiver}.{method}"
n_args = self._compile_expression_list(expr_list)
self._emit(f"call {fn_name} {n_args}")
def _compile_expression_list(self, node) -> int:
count = 0
for child in node.children:
if child.tag == 'expression':
self._compile_expression(child)
count += 1
return count
def _push_pop_var(self, name: str, push: bool):
info = self.sym.lookup(name)
if info is None:
raise NameError(f"Undefined variable: {name!r}")
seg = {
VarKind.STATIC: 'static',
VarKind.FIELD: 'this',
VarKind.LOCAL: 'local',
VarKind.ARGUMENT: 'argument',
}[info.kind]
cmd = 'push' if push else 'pop'
self._emit(f"{cmd} {seg} {info.index}")
Lab exercises
Five labs in labs/lab-11.md. Plan for ~5 hours.
- Lab 11.1. Finalize
toolchain/compiler/codegen.py. Test onConvertToBin.vl— a single-class, function-only program with no objects — and verify the VM output matchestests/compiler/ConvertToBin.vm. - Lab 11.2. Test on
Square/— a three-class program with objects and method dispatch. Run the generated VM through your VM translator from Week 8-9 and simulate on the CPU. - Lab 11.3. Wire the compiler pipeline:
compiler.py= tokenizer → parser → codegen → write VM file. Test the full pipeline end-to-end: VirtusLang source → VM → assembly → binary → simulation. - Lab 11.4 (five-category baseline). Using
Square/Main.vlas the test program, count the VM instructions generated for: (1) arithmetic operations, (2) function call preamble/epilogue, (3) conditional branch sequences, (4) loop overhead, (5) object method dispatch overhead. Record these five numbers in your Toolchain Diary as the "CSA-110 baseline." The CSA-201 peephole optimizer will reduce each category. - Lab 11.5 (Ghidra diagnostic). Compile
ExpressionLessSquare.vl→ VM → assembly → binary. Load the binary in Ghidra (RISCV:LE:32:default architecture). Identify one function in the disassembly that matches a VirtusLang method you compiled. Compare the disassembly to what you expected from the parse tree.
Independent practice
- Read the LLVM Language Reference Manual, "Overview of the LLVM IR" section. LLVM IR is the production-scale equivalent of your VM bytecode — an intermediate representation that multiple front ends (Clang, Rust, Swift) produce, and multiple back ends (x86-64, ARM, RV32I) consume. Note the structural similarities: phi nodes correspond to your if-goto patterns; alloca corresponds to your local segment allocation.
- Review your symbol table implementation and compare it against the symbol table in the nand2tetris Jack compiler specification. Identify one design difference and explain why it matters.
Architecture comparison sidebar
CSA-102 direct codegen vs CSA-110 VM intermediate representation.
CSA-102's Py6502v compiler emitted 6502 assembly directly from the parse tree. There was no intermediate representation. The advantage: simpler toolchain, fewer translation steps, easier to trace from source to binary. The disadvantage: the compiler is tightly coupled to the 6502 ISA — adding a new target architecture requires rewriting the entire back end.
CSA-110's compiler emits VM bytecode. The VM translator then handles the architecture-specific translation. This is the LLVM pattern at small scale: compiler front end produces IR; backend(s) consume IR. The compiler does not need to know whether the target is RV32I-Lite, x86-64, or ARM — it only needs to emit valid VM bytecode. The VM translator knows the target ISA and handles all the register allocation, instruction selection, and frame layout.
The five categories in Lab 11.4 are the same categories that LLVM's optimization passes target: arithmetic simplification (constant folding), call overhead (inlining), branch simplification (SCCP), loop overhead (loop unrolling), dispatch overhead (devirtualization). CSA-201 implements a subset of each. The CSA-110 baseline numbers are the starting point for measuring whether those optimizations help.
Reflection prompts
- The symbol table resolves
thisas a class field access (push this N) for field variables. What would happen if a local variable shadowed a class field with the same name? Write a VirtusLang program that exposes this ambiguity, and verify that your symbol table resolves it correctly (local takes precedence). - Lab 11.4 asks for the VM instruction count for five categories. Which category would you expect to have the highest count for a typical object-oriented program? Why?
- The
_compile_domethod discards the return value withpop temp 0. What would happen iftempwas already in use by the surrounding expression? Write a VirtusLang fragment that would produce wrong code from this implementation, and explain the fix.
What's next
Week 12 completes the compiler: multi-file compilation and OS-aware code generation. The compiler in Week 11 handles single-class programs. Week 12 adds the infrastructure to compile a multi-class program and link it against Virtus OS.