3.1 — Source → Execution

Part 1 built a machine that executes machine code — numbered instructions the CPU fetches and runs (1.5). Part 2 built the operating system that loads and runs those instructions as processes (2.2). But you don't write machine code. You write things like return a + b; or console.log("hi") — text, in a human-readable language, full of names and indentation and words. Somewhere between that text file and the electrons switching in silicon, a translation must happen, and it is one of the most intricate and beautiful pieces of engineering in all of computing.

1.5 showed the result of that translation — return a + b becoming add eax, esi becoming the bytes 01 F0 — but it treated the translator itself as a black box labelled "the compiler." This chapter opens that box. We'll follow a single line of source code through every stage of a compiler: how raw text becomes words, how words become a structure, how that structure is checked for sense, optimised, and finally emitted as machine code — and then how the linker and loader take that output and turn it into a living process. By the end, "compiling" will no longer be a magic verb; it will be a pipeline of understandable steps, each solving a specific problem.

1. The problem: an enormous gap to cross

Consider what has to happen for this line to run:

total = price * quantity;

To you, that's obvious. To a computer, the file containing it is nothing but a sequence of character codes (1.4) — t, o, t, a, l, space, =… It has no notion that total is a name, that * means multiply, that the whole line is an instruction rather than a shopping list. The CPU, meanwhile, understands only numbered opcodes operating on registers and memory addresses (1.5) — it has never heard of a variable called price.

So the translator must bridge an enormous gap:

• Text → meaning. Recognise that this stream of characters forms names, operators, and a statement with a specific structure.
• Meaning → validity. Check it actually makes sense — do price and quantity exist? Are they numbers you can multiply, or is one a piece of text?
• Validity → machine. Decide where price and quantity physically live (registers? memory?), pick the right CPU instructions, and emit the bytes.

Doing this reliably, for millions of lines, in seconds, is what a compiler does. The strategy that makes it tractable is the one great engineering idea of the field: don't do it in one leap — build a pipeline of small stages, each transforming the program into a slightly more machine-like form. Each stage does one job and hands a cleaner representation to the next.

Figure 1 — The compiler pipeline. Each stage converts the program into a form closer to the machine. The front end understands the source language; the back end emits code for the target CPU. The stages in between are deliberately language- and machine-neutral.

2. Lexing: text becomes tokens

The first stage, the lexer (also called the scanner or tokeniser), does the job your eyes do when reading: it groups a stream of individual characters into meaningful words. You don't read "t-o-t-a-l"; you see the word "total" at a glance. The lexer does exactly that, producing a list of tokens — the atoms of the language, each tagged with what kind of thing it is.

Feed it total = price * quantity; and it emits roughly:

Token	Kind
total	identifier (a name)
=	operator (assignment)
price	identifier
*	operator (multiply)
quantity	identifier
;	punctuation (end of statement)

Notice what the lexer discards: whitespace and comments carry no meaning for execution, so they vanish here (which is why indentation is invisible to the compiler in most languages — and why Python, where indentation does matter, has a lexer that deliberately emits special INDENT/DEDENT tokens). Notice also what it does not do: it has no idea whether the statement makes sense. It would happily tokenise = * total ; — nonsense, but lexically fine words. Recognising valid arrangements is the next stage's job.

There's a lovely connection back to theory here. Recognising tokens — "a name is a letter followed by letters or digits," "a number is a run of digits" — is exactly the class of patterns a finite automaton can recognise, which 1.7 called the regular languages. That's why lexers are built from regular expressions or hand-written state machines: the theory tells us this is precisely the right (and cheapest) tool for the job. Lexing is regular languages doing honest work.

3. Parsing: tokens become a tree

Now the parser takes the flat list of tokens and discovers its structure — how the pieces relate. Its output is the single most important data structure in the whole pipeline: the Abstract Syntax Tree (AST), a tree that represents the program's meaning as nested relationships rather than a flat sequence.

Why a tree? Because programs are inherently nested: an expression contains sub-expressions, a function contains statements, a loop contains a body. A tree captures "this thing is made of those things" naturally. Our statement becomes:

Figure 2 — The Abstract Syntax Tree. Structure, not sequence: the assignment's value is a multiplication, whose operands are two variables. Every later stage walks this tree. "Abstract" because the punctuation (;, parentheses) has served its purpose and disappeared.

Read the tree: the root is an assignment; its left branch is the target (total); its right branch is a multiplication, which itself has two children. Evaluating it is now obvious — walk to the bottom, multiply the leaves, store into the target.

The AST is where a language's rules become concrete, and it quietly solves a problem you've relied on since school. Why does 2 + 3 * 4 equal 14 and not 20? Because the parser, following the language's grammar (its formal rules of structure), builds the multiplication deeper in the tree than the addition — and deeper means evaluated first. Operator precedence isn't a runtime rule; it's baked into the tree's shape at parse time. Change the grammar and you change the language. Similarly, a syntax error is simply the parser reaching a point where no valid tree can be built — = * total ; has tokens but no legal structure, so the parser stops and reports where it got stuck.

Theory reappears, one rung up. Nested structure — matching brackets, expressions inside expressions — is exactly what a finite automaton cannot handle and what a pushdown automaton (a state machine plus a stack) can: the context-free languages of 1.7. That's why parsers are stack-based, and why the theory chapter's ladder wasn't academic decoration — it precisely predicts the tool each stage of a real compiler needs. Lexing is regular; parsing is context-free.

4. Semantic analysis: does it actually make sense?

A program can be perfectly structured and still be nonsense. total = price * "hello"; parses into a valid tree — but multiplying a number by a piece of text is meaningless. Checking meaning rather than shape is semantic analysis, and it's where most of the errors you actually see come from.

The compiler walks the AST asking questions a grammar can't:

• Does every name exist? When it meets price, it consults a symbol table — a lookup structure recording every declared name, its type, and its scope (the region of the program where the name is visible). If price was never declared, that's the classic "undefined variable" error. The symbol table is also how scope is implemented: entering a function or block pushes a new layer, leaving it pops that layer, so inner names can shadow outer ones and local names vanish at the block's end.
• Do the types fit? Type checking verifies each operation is applied to things it makes sense for — you may multiply a number by a number, not by a string. This is the compiler catching bugs before the program ever runs, and it's the entire value proposition of statically-typed languages (Chapter 3.3 develops type systems properly; TypeScript's whole job, Chapter 3.7, is adding this stage to JavaScript).

The result is an annotated AST — the same tree, now decorated with resolved types and links from each name to its declaration. From here on, the compiler knows not just the shape of your program but what everything means.

5. Intermediate representation and optimisation

The compiler could now generate machine code directly from the AST — early compilers did. But two problems argue for one more step.

First, an engineering problem: if you support M source languages and N target CPUs, writing a direct translator for each pair means M \times N compilers — an unmaintainable explosion. Instead, translate every language into one common intermediate representation (IR), then translate that IR to each machine. Now you need only M front ends plus N back ends: add a new language and it instantly runs on every CPU; add a new CPU and every language instantly targets it. This is the architecture of LLVM, the compiler infrastructure behind Clang, Rust, and Swift — and it is simply "add a layer of indirection" applied at ecosystem scale, the same instinct as the VFS in 2.6.

Second, a practical problem: a tree is awkward to optimise. IR is typically a flat, simple, instruction-like form — machine code for an idealised machine with infinite registers — which is far easier to analyse and rewrite.

And rewriting is the point, because the optimiser is where compilers earn their reputation. It repeatedly transforms the IR into equivalent-but-better IR. A few of the classic moves, each intuitive:

• Constant folding — compute at compile time what can't change: x = 60 * 60 becomes x = 3600. The multiply never happens at runtime.
• Dead code elimination — delete work whose result is never used, including code after a return or behind an always-false condition.
• Common subexpression elimination — if a * b is computed twice with unchanged inputs, compute once and reuse.
• Loop-invariant code motion — hoist a computation that gives the same answer every iteration out of the loop, so it runs once instead of a million times.
• Inlining — replace a call to a small function with the function's body, removing call overhead and often exposing further optimisations.
• Register allocation — decide which values live in the CPU's few fast registers (1.2) versus slower memory. Given the memory hierarchy of 1.6, this single decision has enormous performance impact, and doing it well is a genuinely hard problem (it's equivalent to graph colouring — one of those NP-complete problems from 1.7, so compilers use good heuristics rather than perfect answers).

This is why -O2 (optimisation level 2) code can run several times faster than unoptimised code from identical source, and why "the compiler will probably handle it" is often — though not always — sound advice about micro-optimisations.

6. Code generation, linking, and loading

Code generation finally walks the optimised IR and emits real instructions for the target ISA (1.5) — choosing actual opcodes, assigning real registers, and computing memory offsets. The output is an object file: machine code for your code, but with holes. If your program calls printf, the compiler knows that you call it but not where it will live in memory, so it leaves a labelled gap.

The linker fills those holes. It takes all your object files plus the libraries you use, resolves every reference (patching "call printf" to the actual address), and produces a single executable. Two flavours matter:

• Static linking copies the library's code into your executable. Result: one big self-contained file that runs anywhere, but if the library is fixed for a security bug, every statically-linked program must be rebuilt.
• Dynamic linking leaves a reference to a shared library (.so on Linux, .dll on Windows, .dylib on macOS), resolved when the program starts. Result: smaller executables, one copy of the library in memory shared by every program using it (via memory-mapping, 2.5), and a security fix applies to everyone at once — at the cost of the classic failure "program won't start: required library not found."

Finally the loader, part of the OS, does the honours you already know from 2.2: on exec(), it reads the executable, maps its text and data segments into a fresh virtual address space (2.5), resolves any dynamic libraries, sets up the stack, and jumps to the entry point. Your text file is now a running process. That is the complete journey — source text → tokens → AST → checked AST → IR → optimised IR → machine code → object file → executable → process → transistors switching (1.1). Every layer of Parts 1, 2, and 3 in one unbroken chain.

7. The expert lens

Compilers are the reason abstraction is free — and that is civilisation-scale leverage. Every convenience you enjoy — named variables, functions, loops, types, objects — exists purely for humans; the machine sees none of it. The compiler is what lets you write in terms of your problem while the machine still gets its rigid, register-level instructions, usually with zero runtime cost (a named constant compiles to the same code as a literal; an inlined function costs nothing). This is what makes large software possible: without compilers, every program would be written in the machine's terms and human productivity would collapse. Understanding that the abstraction is compiled away also tells you when it isn't free (a virtual function call, a heap allocation, a dynamic type check — real work the compiler cannot always erase), which is the beginning of performance intuition.

The pipeline shape is the real lesson, and it recurs everywhere. Source → tokens → tree → checked tree → IR → target is a general pattern for hard transformations: break an impossible leap into stages, each with one job and a clean data structure between them. You'll meet the same shape in a browser turning HTML into pixels (Part 6: parse → DOM → layout → paint), in a database turning SQL into an execution plan (Part 7: parse → plan → optimise → execute), in data pipelines (Part 12), and in the Unix pipes of 2.8. Recognising "this is a compiler-shaped problem" is a genuinely reusable design instinct — and it's why so many tools you use (linters, formatters, bundlers, type checkers, pydot-style diagram generators) are literally compiler front ends that stop after the AST.

The AST is where modern tooling lives. Once you know a parser produces a tree, an entire category of tools stops being mysterious: a formatter (Prettier) parses to an AST and re-prints it with consistent whitespace — which is why formatting can never change your program's meaning. A linter (ESLint) walks the AST looking for suspicious shapes. A bundler (webpack, Vite — Part 6) parses modules to find their import statements. A codemod rewrites the AST and prints it back. TypeScript (Chapter 3.7) is a front end that type-checks and then simply erases the types. When you later hear "it works on the AST," you'll know exactly which stage of this pipeline is meant.

Next chapter: we've assumed the whole program is translated ahead of time into a finished executable. But JavaScript in a browser and Python at a prompt clearly don't work that way — they run source directly, translating as they go. Chapter 3.2 takes on compilation versus interpretation, the bytecode virtual machines in between, and the JIT — the hybrid that makes JavaScript, of all things, run at nearly the speed of C.

Recall

• A compiler bridges the gap from human text to machine code by a pipeline of small stages, each producing a more machine-like form.
• The lexer groups characters into tokens (words), discarding whitespace/comments — a regular-language job (1.7). The parser turns tokens into an Abstract Syntax Tree reflecting nested structure — a context-free job needing a stack. Operator precedence is baked into the tree's shape; a syntax error is "no valid tree exists."
• Semantic analysis checks meaning: a symbol table resolves every name and implements scope; type checking rejects nonsense like number × string — catching bugs before the program runs.
• An intermediate representation decouples M languages from N machines (the LLVM idea: M+N instead of M\times N) and is where the optimiser works — constant folding, dead-code elimination, inlining, loop-invariant motion, and register allocation.
• Code generation emits an object file; the linker resolves references into an executable (static = copied in, dynamic = shared library resolved at start); the OS loader maps it into a process (2.2) and jumps to its entry point.

Self-test: What does the lexer produce, and what does it throw away? Why is the parser's output a tree, and how does that explain why 2 + 3 * 4 is 14? What does a symbol table do? Why does an IR exist at all? What's the difference between static and dynamic linking, and what failure is unique to dynamic?

Quiz Bank

FoundationalWhat are the main stages of a compiler, in order?

Lexing (characters → tokens), parsing (tokens → Abstract Syntax Tree), semantic analysis (name resolution via a symbol table + type checking, producing an annotated AST), IR generation (into a machine-neutral intermediate representation), optimisation (rewriting the IR into faster equivalent IR), and code generation (IR → target machine code in an object file). Afterwards, outside the compiler proper: the linker combines object files/libraries into an executable, and the OS loader turns that into a running process. Each stage does one job and hands a cleaner representation to the next.

FoundationalWhat is a token, and what does the lexer discard?

A token is one "word" of the language, tagged with its kind — identifier (total), operator (*), literal (42), punctuation (;). The lexer scans the raw character stream and groups characters into this list of tokens, discarding whitespace and comments (which carry no execution meaning — hence indentation is invisible to most compilers). The lexer checks nothing about whether the arrangement makes sense; = * total ; tokenises fine and fails later, at parsing.

AppliedWhy is the parser's output a tree, and how does that explain operator precedence?

Programs are inherently nested — expressions contain sub-expressions, functions contain statements — and a tree naturally represents "this is made of those." The AST captures the program's structure rather than its character sequence. Precedence follows directly: parsing 2 + 3 * 4 by the language's grammar places the multiplication deeper in the tree than the addition, and evaluation works bottom-up, so 3 * 4 happens first, giving 14. Precedence is not a runtime rule — it's baked into the tree's shape at parse time.

AppliedWhat does semantic analysis check that parsing cannot?

Parsing only validates structure; semantic analysis validates meaning. Walking the AST, it (1) resolves names against a symbol table — does price exist, where was it declared, what is its scope? (producing "undefined variable" errors), and (2) performs type checking — is each operation applied to compatible types? (number * string parses fine but is meaningless). It outputs an annotated AST decorated with resolved types and declarations. This is the stage that catches a large share of real bugs before the program ever runs, and it's the core value of static typing.

InterviewWhy do compilers use an intermediate representation instead of generating machine code straight from the AST?

Two reasons. Engineering: with M source languages and N target CPUs, direct translators need M \times N implementations; funnelling everything through a common IR needs only M front ends + N back ends, so a new language instantly supports all CPUs and a new CPU instantly supports all languages (this is the LLVM architecture behind Clang, Rust, Swift). Practical: a tree is awkward to analyse and rewrite, whereas IR is a flat, simple, instruction-like form (an idealised machine with infinite registers) that makes optimisation passes far easier to express and compose.

InterviewExplain static vs dynamic linking, with the trade-offs.

The linker resolves references (like a call to printf) to real addresses. Static linking copies the library's code into your executable: the result is self-contained and runs anywhere with no dependencies, but the binary is larger, memory holds a separate copy per program, and a library security fix requires rebuilding and redeploying every program that embedded it. Dynamic linking leaves a reference to a shared library (.so/.dll/.dylib) resolved at program start: executables are smaller, one copy in memory is shared by all users of it (via memory-mapping — 2.5), and patching the library fixes every program at once — but the program now depends on the right library being present at the right version, producing the classic "cannot open shared object file" startup failure and version-conflict problems.

StaffA colleague hand-optimises code by replacing `x = 60 * 60` with `x = 3600` and hoisting a constant computation out of a loop, arguing it's faster. Evaluate this, and say where the argument does and doesn't hold.

For those two specific examples the argument is almost certainly wrong at any reasonable optimisation level: 60 * 60 is eliminated by constant folding (computed at compile time — the multiply never exists at runtime), and hoisting an unchanging computation out of a loop is textbook loop-invariant code motion, which optimisers perform automatically. So the hand-edits gain nothing while costing readability (3600 hides the meaning 60 * 60 conveyed). The general principle:

don't hand-perform transformations the optimiser reliably does — write for clarity and let -O2 do it. Where the argument does hold, and this is the important half: optimisers are conservative and cannot change program semantics, so they won't help when (1) the computation has side effects or calls an opaque/external function the compiler can't prove is pure, (2) pointer aliasing or shared mutable state means the compiler can't prove a value is unchanged across iterations, (3) the win is algorithmic (an O(n^2) approach — no optimiser will replace your algorithm), or (4) the win is about memory layout/access patterns (1.6), which the compiler largely cannot restructure. The staff framing: trust the compiler for local, provable, semantics-preserving rewrites; own the things it cannot prove or restructure — algorithms, data layout, and I/O — and always measure rather than assume.

Flashcards

FlashCompiler pipeline, in order

Lexer (tokens) → parser (AST) → semantic analysis (symbol table + types) → IR → optimiser → code generation (object file) → linker (executable) → loader (process).

FlashWhat the lexer does

Groups characters into tagged tokens (identifiers, operators, literals), discarding whitespace and comments. A regular-language job.

FlashWhat an AST is and why a tree

Abstract Syntax Tree — the program's nested structure as a tree; nesting matches how programs are built, and tree depth encodes operator precedence.

FlashSymbol table

The compiler's record of every declared name, its type and scope — used to resolve names and produce "undefined variable" errors.

FlashWhy an intermediate representation

Decouples M languages from N machines (M+N pieces instead of M×N) and provides a flat form that's easy to optimise. The LLVM idea.

FlashFour classic optimisations

Constant folding, dead-code elimination, common-subexpression elimination, loop-invariant code motion (plus inlining and register allocation).

FlashStatic vs dynamic linking

Static: library copied into the executable (self-contained, but rebuild to patch). Dynamic: shared library resolved at startup (small, shared, patch once — but must be present at runtime).

Scenario Drill

DrillYour team wants a tool that automatically renames a function across a large codebase, and someone proposes doing it with find-and-replace on the text. Explain why that's fragile and what the right approach is, using this chapter.

Text find-and-replace operates on characters, with no understanding of structure or meaning — precisely the gap the compiler pipeline exists to close. It will wrongly hit the name inside unrelated contexts: a string literal ("call getUser to continue"), a comment, a different variable that merely contains the same substring (getUserId), or a different getUser declared in another scope or module that must not be renamed. It will equally miss cases it should catch. The result is silent breakage — some of it not caught until runtime. The right approach is to work at the level where names have meaning: parse the code into an AST (section 3 above), run semantic analysis so every use of the name is resolved through the symbol table to the specific declaration it refers to, rename only the nodes bound to that one declaration, then print the tree back to source.

This is exactly what a codemod / IDE "Rename Symbol" refactor does, and why it's reliable where text replacement isn't — it distinguishes "the characters g-e-t-U-s-e-r" from "the identifier bound to this declaration," respecting scope, shadowing, strings, and comments automatically. Practically: use the language's existing tooling (TypeScript's language service, jscodeshift, an IDE refactor, gofmt -r) rather than building it — they're compiler front ends that stop after the AST, which is the general lesson:

any tool that must understand code, not just match text, belongs on the AST.