Compiler Foundations: Language, Tokens, Grammar

This course builds a language in six milestones. You are constructing a tool whose intermediate artifacts you can inspect, save, and test. Coding exercises isolate one implementation boundary; capstones provide the surrounding helpers and require you to connect them. They do not automatically paste your earlier submissions into the next exercise. Keep your own notes and regression examples when transferring an idea to the supplied next-version types.

Course map

Milestone	New capability	Artifact you should be able to explain
Expressions	Tokens, precedence, postfix lowering	Token list → expression AST → instruction sequence
v2 programs	Bindings, branches, named functions	Checked Program → BC1 → executable VM state
v3 values	Collections, nested functions, closures	BC2 function IDs, closure environments, reachable heap graph
v4 flow	for, loop exits, lazy boolean operators	Jump targets and scope cleanup on every path
v5 modules	Imports, exports, separate compilation	Module artifacts → relocated function IDs and Main addresses
v6 types	Explicit function signatures, structural types	Type-directed diagnostics before the same dynamic VM

Early exercises deliberately omit later features. v1 has no strings or statements to lower; v2 has no closures; v3/v4 have no module linker; v5 has no static type annotations. BC1 calls functions by name; BC2 calls a closure value. Those are representation changes, not additional spellings of the same API.

Worked reconstruction

Consider the expression 8 - 2 * 3:

Stage	Output	What it has decided
Lex	NUMBER 8, MINUS, NUMBER 2, STAR, NUMBER 3, EOF	Character boundaries and positions
Parse	Sub(8, Mul(2,3))	Multiplication binds more tightly
Lower	PUSH 8; PUSH 2; PUSH 3; MUL; SUB	Evaluation order and stack protocol
Hand execution	[8,2,3] → [8,6] → [2]	Numeric result under runtime rules

The expression lexer can tokenize missing + 1; it does not know whether missing has a binding. Likewise a parser can construct a well-formed tree for a name that semantic analysis will reject. Later let x = ; fails parsing before names can be checked. In v2, let x = "a" - 1; has valid syntax and names but fails runtime numeric checks; v6 can reject that mismatch earlier.

How to use a module

First predict a small artifact on paper. Then compare the worked trace, implement the exercise, and deliberately break one invariant. Keep the smallest input that distinguishes the correct and broken implementations. Finally solve the transfer task without the worked example open. A checkpoint identifies a misunderstanding; its review link is a route back to the representation you need to reconstruct.

Use a six-column notebook: source, tokens, AST, diagnostics, bytecode, VM state. Fill only the columns relevant to the current milestone. When a final value is wrong, inspect the earliest differing column instead of editing every stage.

Reference approaches and boundaries

Nand2Tetris syntax analysis separates tokenizer and parser artifacts before its code-generation project. This course uses Go structs and BC1/BC2 instead of Jack/XML and its VM language. The LLVM tutorial provides another cumulative route from a lexer to generated code. Our target is a small stack VM, not LLVM IR or native code. The external projects are useful comparisons, not specifications for the local grader.

Debugging lab

A student fixes 8 - 2 * 3 by changing the VM so every subtraction multiplies the right operand by three. The parser produced Mul(Sub(8,2),3). Identify the first wrong representation and a second input that exposes the proposed patch.

Compare your diagnosis after attempting the lab

The AST is already wrong: precedence belongs to parsing. 9 - 4 exposes the VM patch because subtraction must remain ordinary subtraction. Fix the tree, preserve the VM arithmetic contract, and retain both tests.

Transfer task

Build a failure-stage table for @, 1 +, unknown + 1, and "s" - 1 in a v2 program context. Write the earliest stage that can reject each and what evidence that stage needs. Revisit the table after v6 to identify which failures move earlier.

Carry forward

Carry a version table and one minimal counterexample per stage into the lexer. Do not import a later feature until its module explicitly changes the contract.