A compiler translates representations; an interpreter executes a representation according to its rules.
By the end: Distinguish language semantics, translation stages, execution engines, and observable behavior.
This course assumes familiarity with variables, arithmetic expressions, conditionals, and functions in at least one programming language. It requires neither compiler experience nor assembly language, formal-language theory, calculus, or another course in this library. The aim is to follow expert explanations and investigate unfamiliar implementations, not to build a production compiler.
Define the behavior before changing the representation
A programming language specifies what its programs mean: which inputs are valid, how values behave, and which effects execution can produce. A compiler translates a program while preserving the required behavior. It does not merely replace words with machine instructions. The same source construct may require several operations, or disappear after a valid optimization.
An interpreter executes a representation directly. A system can compile source to bytecode and then interpret that bytecode. It can later compile frequently executed bytecode to native code. Compiled and interpreted therefore describe implementation choices, not mutually exclusive kinds of language.
Follow one expression without changing its meaning
Consider the source x * (2 + 3). Before choosing an implementation, specify what counts as its answer. The name x refers to the integer four in this lab. The parentheses put addition inside the right operand of multiplication. Addition produces five, and multiplication produces twenty. These statements describe the language's meaning. They do not yet require an operand stack, a particular processor instruction, or a decision about whether the addition happens during translation or during execution. Those choices need to implement the specified answer without redefining the expression.
Tokenization records x, *, (, 2, +, 3, and ) as separate tokens. Parsing then builds a multiplication node with x as its left child and an addition node as its right child. The addition has two literal children. Parenthesis tokens establish that grouping but need not remain as tree nodes. Unlike a list of source characters, this tree says which operation consumes which result. Its edges encode dependencies, while its positions on the screen have no numerical meaning.
Parentheses change the consuming operation
Original syntax trees. Lines join an operation to its operands. Geometry is schematic, with no time or address scale; left and right operand positions carry meaning.
A tree evaluator reads x, saves four while evaluating the other child, calculates two plus three, and multiplies the two child results. A bytecode compiler instead emits LOAD x, PUSH 2, PUSH 3, ADD, and MUL. Emitting ADD does not itself add anything during this translation. Later, the virtual machine executes that instruction against values on its operand stack. Translation creates a representation of the work; execution applies that representation's rules to an actual machine state.
The bytecode sequence gives a useful intermediate check. After LOAD x, the stack contains four. After the next two instructions, its bottom-to-top contents are four, two, three. ADD replaces the top pair with five, leaving four, five. MUL replaces that pair with twenty. The stack ends with exactly one value. Merely finding the expected number somewhere in the stack would be insufficient. The expression execution contract requires one result, with no unfinished operands left underneath it.
Now contrast the spelling x * 2 + 3. Multiplication binds more tightly than addition, so the tree has addition at its root. The multiplication consumes four and two first, producing eight, and the root adds three to produce eleven. A compiler that ignored the parentheses in the earlier expression would silently translate a different program. Checking only whether each source operator appeared somewhere in the output would miss this defect. The dependencies and operand roles must survive translation as well.
The saved left operand survives the addition
Snapshots for LOAD x; PUSH 2; PUSH 3; ADD; MUL, with x = 4. One cell is one operand value, not a byte or register. Top labels identify the next value to pop; snapshot spacing is not elapsed time.
Use the Names preset in the complete expression lab to locate these relationships yourself. Predict the root, the right child's result, and the five instructions before inspecting the display. Then edit the source to x * 2 + 3. The result should change from twenty to eleven even though the names, literals, and arithmetic symbols remain the same. Explain the change by identifying the new parent-child relationships, rather than treating the displayed result as evidence that the parser chose an arbitrary evaluation order.
Separate responsibilities, not necessarily physical passes
Lexing groups characters into tokens. Parsing groups tokens into syntax. Name resolution connects uses to declarations. Type checking enforces the language’s rules. Intermediate representations expose operations and control flow. Later stages transform them, select target instructions, assign storage, and connect compiled pieces.
These are conceptual responsibilities, not a mandatory sequence of separate executables or traversals. A compiler may combine work or repeat analyses after transformations. Our small expression implementation resolves names and checks types in one traversal. A clean diagram should not imply that every production compiler has the same architecture.
Ask what each responsibility establishes
A stage boundary is useful because it separates claims. A token stream establishes that the scanner found recognized spellings within its resource bounds. A syntax tree establishes that those tokens form an expression under the grammar. Neither establishes that every name exists. Binding checks that question against an environment. Type checking asks whether each operation accepts the types supplied by its children. In this implementation, binding and typing share a recursive walk, but they still answer different questions about the same tree.
Work through absent + 1. Every character belongs to a valid token, and addition can connect the name node to the literal node. The failure occurs when the checking traversal looks up absent and finds no binding. Compare flag + 1. Here lookup succeeds and supplies a boolean type. The addition rule requires integer children, so checking rejects the expression. The implementation does not try converting true to one. Recognizing the name and accepting its use as an arithmetic operand are separate obligations.
The first failed obligation differs
Source
Established before failure
First failure
absent + 1
Tokens and addition tree
Binding: absent is missing
flag + 1
Tokens, tree, flag binding
Typing: bool is not int
x + 1
Tokens, tree, integer operands
None; result 5
These outcomes use the fixed SmallExpr environment. Binding and typing share a traversal, but their obligations remain distinct.
An accepted tree can support more than one translation. The original emitter keeps the literal addition in x * (2 + 3). The constant folder replaces that numeric subtree with a literal five, and another emission produces LOAD x, PUSH 5, MUL. The two streams differ in length and intermediate states. Their required relationship is that they produce the same typed result under the relevant semantics. Internal similarity is neither necessary nor sufficient for a correct translation of a source expression.
There is a small structural argument behind the emitter. A literal or valid name emits code that adds one value to an existing stack. Assume each child's code preserves earlier stack entries and adds its own result. Emitting a binary node runs the left code and then the right code, so two new values appear in operand order. Its final arithmetic instruction consumes those values and adds one result. This argument explains composition for accepted expression trees, rather than relying only on one successful execution.
The argument has preconditions. Names must have valid bindings, arithmetic children must have integer types, and the VM operations must implement the same wrapping rules as the tree evaluator. It also assumes the emitter uses the intended traversal order and the VM treats the first popped value as the right operand. These are implementation obligations, not consequences of drawing a tree. Testing subtraction is particularly useful because reversing operands can remain invisible in addition examples that happen to produce the expected answer.
Static reasoning and execution evidence therefore complement each other. A structural argument covers arbitrary trees satisfying its assumptions, but a faulty implementation can violate those assumptions. A trace shows what this implementation did for one expression, but does not establish agreement for every accepted expression. When reading a compiler claim, ask whether it reports a checked invariant, a semantic argument, a collection of test results, or a measurement. Calling all four things verification without naming the evidence makes the conclusion harder to assess.
A stack invariant composes across the tree
Accepted node
Code action
Stack obligation
Literal or bound name
PUSH or LOAD
Preserve earlier entries; add one value
Unary minus
Child code, then NEG
Replace child result with one integer
Binary arithmetic
Left code, right code, operation
Consume right then left; add one result
Static proof outline for correctly checked SmallExpr trees. The invariant concerns an arbitrary earlier stack prefix; it is not a recorded execution or a native target proof.
Work through the mechanism
A complete expression translation
Presets replace the whole source. Editing replaces the current calculation and resets any execution trace. Names: x = 4, y = 7, flag = true. Use ASCII - for subtraction and negation. Arithmetic is signed 32-bit wrapping; booleans are not numbers. See lesson 1 for the full grammar and editor bounds.
Token stream
2number[0,1)
+symbol[2,3)
3number[4,5)
*symbol[6,7)
4number[8,9)
The end marker is at offset 9. Spans exclude whitespace; token categories do not prove the expression is valid.
Abstract syntax tree
Type: int. Direct evaluation: 14. VM result: 14. Original instructions: 5; after folding: 1.
PUSH2PUSH3PUSH4MULADD
The output is recalculated immediately. This bounded compiler implements expressions only, not the later pseudocode examples. The entered source is never passed to JavaScript eval or Function.
Representation
For 2 + 3 * 4
Tokens
2, +, 3, *, 4
Tree root
Addition, with multiplication as the right child
Stack code
PUSH 2; PUSH 3; PUSH 4; MUL; ADD
Result
14
The lab implements this bounded expression language. It does not invoke JavaScript eval or generate native executables.
Read the lab as evidence about representations
The complete expression view displays several products of one calculation. Its tokens describe the source spelling, its tree describes grouping, and its bytecode describes stack operations. The reported direct evaluation and VM result provide two execution routes through that grouping. Reading across these products can locate a disagreement more precisely than comparing final numbers alone. If the tree already has the wrong root, inspecting multiplication's stack implementation is unlikely to explain the first mistake. Start with the earliest representation that differs from your prediction.
Select the Precedence preset and predict fourteen. The multiplication child computes three times four as twelve before the addition combines it with two. Then select Parentheses and predict twenty. Now addition computes five before multiplication combines it with four. Both original streams contain five instructions because each has three leaves and two binary nodes. Equal instruction counts do not establish equivalent programs. Here the counts agree while the operation dependencies and final results differ, which the two trees make visible.
Next compare left-associated subtraction with explicitly nested subtraction. For 8 - 3 - 1, the first subtraction must consume eight and three before the final literal is used, leaving five and then four. For 8 - (3 - 1), the inner subtraction produces two, and the outer subtraction produces six. This is not a dispute about subtraction's arithmetic rule. The parser supplies different operand trees, and the compiler must preserve those trees when it decides where to place each SUB instruction.
The same five instructions need different order
Source grouping
Emitted instruction sequence
Stacks after each instruction, bottom first
(8 - 3) - 1
PUSH 8; PUSH 3; SUB; PUSH 1; SUB
[8]; [8,3]; [5]; [5,1]; [4]
8 - (3 - 1)
PUSH 8; PUSH 3; PUSH 1; SUB; SUB
[8]; [8,3]; [8,3,1]; [8,2]; [6]
Exact traces in the teaching VM. The instruction ordering preserves the parse tree; counts alone cannot distinguish these results.
The compilation status also reports an instruction count after folding. In 2 + 3 * 4, both arithmetic nodes have constant descendants, so folding can replace the entire tree with fourteen. The original emission has five instructions; the folded emission has one PUSH. That is an exact reduction in this defined instruction vocabulary. It is not a claim that the web page becomes five times faster, because rendering, checking, translation, and VM dispatch have costs outside that simple count.
For an additional check, enter x * 0 + y. Predict seven using x equal to four and y equal to seven. Do not predict that the implemented folder replaces the entire expression with seven. It folds numeric literal subtrees, not arbitrary expressions involving names, and it does not apply the identity that multiplication by zero yields zero. The original and folded streams therefore both contain five instructions. A transformation's mathematical possibility and its actual implementation are different claims that this example separates.
Finally enter flag by itself and then flag + 1. The first is a complete boolean expression and returns true without an arithmetic instruction. The second fails typing before successful compilation. The lab may still show the tokens and tree that it constructed before that failure. Those partial products are diagnostic evidence, not permission to execute an invalid expression. Record which responsibilities succeeded and which failed. This gives a more precise account than saying that the whole pipeline either worked or did nothing.
Count only what the instruction vocabulary defines
Source
Original / folded instructions
Result
2 + 3 * 4
5 / 1
14
(2 + 3) * 4
5 / 1
20
x * 0 + y
5 / 5
7
flag
1 / 1
true
Counts are exact abstract VM instructions, not timings or native instruction counts. Numeric constant folding does not replace names using the fixed environment.
Specify the small language used here
SmallExpr supports decimal literals from 0 through 999, true and false, names, parentheses, unary minus, and binary +, −, and *. Arithmetic requires integers and wraps to signed 32-bit results after each operation. Multiplication binds tighter than addition and subtraction; binary operators at the same level associate left. Operands are evaluated left before right.
The environment is x = 4, y = 7, flag = true. There are no calls, assignments, strings, loops, input/output, or implicit boolean conversion in SmallExpr. The live editor is bounded to 120 characters, 31 tokens, six-character ASCII names, eight leaves, and tree depth seven, plus eight levels of parenthesis nesting. The side-by-side optimization view further limits source trees to four leaves so both diagrams stay readable. Later loop, function, and memory examples are explicitly separate pseudocode, not extra features of this compiler.
Keep arithmetic and implementation boundaries explicit
SmallExpr's integer type describes signed 32-bit values, not unbounded mathematical integers. Its addition, subtraction, multiplication, and negation wrap after each operation. Wrapping retains the low 32 bits and interprets that pattern as signed. A result whose unsigned pattern exceeds the largest signed positive value therefore appears negative. This behavior belongs to the language contract used by every execution route here. It is not an accidental browser rounding error, and another language may choose a different contract for similar source spelling.
The wrapping preset reaches a large result without using an out-of-range literal. The first multiplication of 999 by 999 gives 998,001. Multiplying by another 999 gives 997,002,999, which still fits the signed range. The mathematical fourth product is 996,005,996,001. Removing 231 whole multiples of 4,294,967,296 leaves the unsigned remainder 3,868,550,625. That remainder has its signed bit set, so subtracting 4,294,967,296 gives the stored result negative 426,416,671. The final step changes representation, not the preceding decimal multiplication.
Track the mathematical product and its signed representation
Step
Exact integer quantity
Meaning
999 × 999
998,001
Fits signed 32 bits
998,001 × 999
997,002,999
Still fits
997,002,999 × 999
996,005,996,001
Mathematical fourth product
Subtract 231 × 4,294,967,296
3,868,550,625
Unsigned low-32-bit remainder
Subtract 4,294,967,296 again
−426,416,671
Signed interpretation
All quantities are integer values, not physical units. The last subtraction interprets the same 32-bit pattern as signed; it is not a further SmallExpr source operation.
The literal bound and the arithmetic range answer different questions. A source literal of 1000 exceeds this editor's supported literal range even though one thousand fits easily in a signed 32-bit value. Conversely, multiplying allowed literals can overflow that signed range. An int type therefore does not promise that arithmetic matches unbounded arithmetic, and a limit error does not imply that the requested mathematical operation is undefined. Keeping the two limits separate prevents a user-interface restriction from becoming an invented semantic guarantee.
The later lessons introduce additional representations through separate pseudocode. Their scope links, control-flow graph, live-temporary sets, object references, and relocation arithmetic teach responsibilities missing from this expression implementation. They do not extend the editor's grammar. Entering a variable declaration or a function call here will not reveal a hidden statement compiler. SmallExpr has fixed x, y, and flag bindings, no assignment, and no input or output effects. Its result comparisons are useful partly because the observable behavior is deliberately restricted.
A native backend would need further decisions even after our stack code is correct. Real instruction sets constrain available operations, operand locations, immediate encodings, and register use. A runtime may also need calling conventions and object representations. Our VM's LOAD reads a fixed binding by name; it does not demonstrate a physical memory load at a measured address. Likewise, its instruction count counts abstract operations, not processor cycles. Moving toward a target representation creates new proof obligations rather than erasing the earlier semantic ones.
Separate the executable model from later teaching models
Representation or mechanism
What this course implements
SmallExpr tokens, tree, bytecode
Working bounded expression translation and execution
Scope links and loop CFG
Separate pseudocode models
Live temporaries and heap references
Separate storage and reachability illustrations
Native instructions and relocation
Target responsibilities and hypothetical address arithmetic
No row adds statements, functions, heap allocation, a register allocator, or native emission to the SmallExpr editor.
Use these distinctions to assess a proposed improvement. Suppose someone replaces every accepted expression with its result for the current fixed environment. That could preserve this lab's returned values, but it would be specialization, not the implemented literal folder. If bindings could later change, the replacement would need a new justification. Ask what inputs and environments the equivalence covers, what observations matter, and what evidence supports the transformation. A smaller output representation is meaningful only after those questions have a defined answer.
Exercises
Compile and interpret in one system
A tool translates source into bytecode, then a virtual machine executes that bytecode one instruction at a time. Is compilation absent because a virtual machine is involved?
Hint
Ask which representation is translated and which is executed.
Worked answer
Step
Role
Source to bytecode
Compiler
Bytecode execution
Interpreter
Hot bytecode to native code
Possible JIT compiler
These roles can coexist in one implementation.
No. Translation from source to bytecode is compilation. Executing bytecode instruction by instruction is interpretation. A later just-in-time compiler could translate some bytecode to native code. Name the representations and engines rather than assign one label to the whole language.
Preserve the required behavior
Two implementations print the same final number, but one prints an extra line before it. Are they necessarily equivalent?
Hint
The observable result may include more than the final value.
Worked answer
Language property
What a translation must respect
Output is observable
Required output trace
Exceptions are specified
Required exception behavior
Pure SmallExpr expression
Typed returned value
A value-only test is sufficient only for an appropriately restricted language.
No. If output is observable under the language contract, the extra line changes behavior. Equivalence can also depend on exceptions, termination, memory interactions, and permitted nondeterminism. SmallExpr has no such effects, so its equivalence tests can compare returned values within its defined domain.
Sources and further reading
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected passages on tokenization, identifier recognition, and maximal munch. The book implements Lox; SmallExpr is a separate, smaller teaching language.
Selected material on IR structure, SSA, phi semantics, integer operations, and semantic constraints. A production IR reference, not a specification of SmallExpr or a claim that every compiler uses LLVM.