← Lectures
Back

1 / 8

Next

Slide 1 of 8: Four jobs, in order

Arrow keys move through the slides while these controls have focus.

The theatre is not shown, because your system asks for reduced motion. The lecture itself is below, in full.

Lecture · 8 slides

What a compiler actually does

A compiler is the piece of software most programmers depend on daily and fewest have looked inside. It has a reputation for depth that keeps people out — the dragon on the cover of the standard textbook has a lot to answer for — and the reputation is only half deserved. Some of what a compiler does is genuinely hard research. Most of what it does is four unglamorous jobs in a row, each of which can be explained in a paragraph.

The reason to understand the shape is practical rather than academic. Almost every confusing thing a compiler says to you is a message from one specific stage, and knowing which one tells you what kind of mistake you have made. A complaint about an unexpected token is a different species of problem from a complaint about a type, which is different again from a linker error, and they arrive from three different programs that happen to be invoked by one command.

This lecture walks the pipeline in order. The examples are C-shaped because C is the case where the stages are most visible, but the structure is the same in every compiler you are likely to use, including the ones hiding inside languages that are usually described as interpreted.

AssumesYou have compiled a program and read an error message from the compiler. Nothing about compilers themselves.

  1. Slide 1

    Four jobs, in order

    Everything a compiler does falls into four stages, and they run in a fixed sequence because each needs the previous one's output.

    First the text is broken into words. Then the words are arranged into a shape. Then the shape is inspected for whether it means anything. Then the meaning is written out again as instructions. Lexing, parsing, analysis, generation — every compiler has these, whatever it calls them, and the ones that seem not to have merged two of them together.

    What makes this worth learning is that the stages fail differently. A stray quotation mark is caught in stage one. A missing bracket is stage two. A misspelled variable is stage three. Being unable to find a library is a fifth program, the linker, that runs after all of this is over. Four of the most common frustrations in programming are four different programs failing, and the command line makes them look like one.

  2. Slide 2

    Lexing: text becomes words

    The first stage does something almost boring: it reads characters and groups them into the smallest units that mean anything.

    int n = count + 1;
    c

    That line is nine characters of meaning and eight of whitespace, and the lexer emits eight tokens: a keyword, an identifier, an equals sign, an identifier, a plus, a number, a semicolon. Whitespace and comments are discarded here and never mentioned again, which is why the compiler cannot tell you that your indentation is misleading.

    The subtlety, and the only interesting decision in the whole stage, is how much to swallow at once. Faced with >= the lexer must take two characters, not one, or the parser will see a greater-than followed by an equals and be correctly baffled. The usual rule is longest match wins, and it is why languages avoid operators that are prefixes of other operators in ambiguous positions. Small design decisions in a language are often really decisions about making this stage possible.

  3. Slide 3

    Parsing: words become a shape

    The second stage takes the flat list of tokens and discovers the structure that was implied by their order.

          =
     / \
    n   +
       / \
  count   1
    plaintext

    That tree is the same statement, with a claim added: the addition happens first, and its result is what gets assigned. Nothing in the token list said so. Precedence, associativity and every rule about which brackets you may leave out are decisions this stage makes, and it makes them from a grammar the language designer wrote down.

    This is the stage that produces the error message everyone has seen and nobody likes — *unexpected token*, usually pointing at a line after the actual mistake. The reason is structural rather than lazy. A missing closing brace is invisible until the parser reaches something that cannot follow what it has, which may be forty lines later. The parser is telling you truthfully where it noticed, and it has no way to know where you went wrong.

  4. Slide 4

    The tree is where the program lives

    From here on the text is gone. Everything the compiler does afterwards is done to the tree, and that fact explains more about compilers than any other single idea.

    It is why a formatter can rewrite your whitespace without changing your program: the whitespace was thrown away before anything meaningful happened. It is why a macro system that operates on the tree is more powerful and less error-prone than one that operates on text — the C preprocessor works on tokens and is famous for surprises that a tree-based macro system, like Lisp's or Rust's, cannot produce.

    And it is why the quine hanging in the Cabinet of Curiosities is more interesting than a trick. A program that prints itself has to reconstruct its own text, which is precisely the thing the compiler discarded on the way in.

  5. Slide 5

    Analysis: does this mean anything

    The third stage walks the tree asking questions the parser could not: does this name exist, does this type fit, is this variable used before it is set.

    This is where a language's character shows most. A compiler for a statically typed language does an enormous amount of work here and rejects a great many programs that would have run correctly. One for a dynamic language does almost none and defers the same questions to runtime. Neither is doing something the other cannot; they are choosing when to ask.

    The stage also builds the symbol table, which is the answer to "what does this name refer to here" — and scoping rules, closures and shadowing are all descriptions of how that table is arranged. A surprising amount of what feels like deep language semantics is a data structure being consulted.

  6. Slide 6

    Optimisation is a series of provable rewrites

    Between understanding the program and emitting it, most compilers rewrite it, sometimes drastically, under one rule: the result must behave the same.

    for (int i = 0; i < 4; i++)
  total += 1;
    c

    A compiler is entitled to turn that into total += 4, because it can prove nothing else observes the difference. It may inline a function, delete a branch it knows cannot be taken, keep a variable in a register instead of memory, or reorder two statements that do not depend on each other.

    The phrase carrying the weight is *nothing else observes the difference*, and it is where optimisation gets its reputation for danger. In C, code that relies on undefined behaviour has no defined result to preserve, so the compiler is free to assume it never happens — which is why a null check placed after a dereference can be deleted entirely. The compiler is not being clever at your expense. It is keeping a promise about a program you did not actually write.

  7. Slide 7

    Generation, and the problem of registers

    The last stage walks the optimised tree and writes instructions, and the hard part is not choosing them.

    The hard part is that a processor has perhaps sixteen general-purpose registers and your function has forty live values. Deciding which value lives in a register and which is spilled to memory is register allocation, it is equivalent to graph colouring, it is NP-complete, and every compiler solves it with heuristics that are usually very good and occasionally not.

    The assembly hanging in the Hall of First Words is what this stage produces, written by hand. Put it beside the C beside it and the whole pipeline is visible in one room: the same twelve characters of output, one version written in the language of the problem, the other in the language of the machine, with four stages of mechanical translation in between.

  8. Slide 8

    What is left when it finishes

    The output is an object file, and it is not yet a program.

    It contains machine code with holes in it — every call to a function defined elsewhere is a blank waiting to be filled with an address nobody knows yet. Filling them is the linker's job, a separate program with its own error messages, and this is why *undefined reference* looks so different from every other error you have seen: it comes from a stage that has never looked at your source code and has no idea what a type is.

    Which is the honest summary of the whole pipeline. There is no single program called a compiler doing something mysterious. There is a sequence of small transformations, each of which turns a representation you understand into a representation slightly closer to the machine, and every error message you have ever cursed is one of them reporting, accurately, that it could not continue.

Works in the collection

The arguments above are hanging on the walls of the museum, in one form or another. These are the ones worth looking at next.

The rest of the programme

  1. Compiled, interpreted, and the space betweenA distinction that stopped describing anything decades ago, why it persists, and what is actually different about the machinery underneath.
  2. Functional programming and object orientationTwo ways of arranging a program, what each one genuinely makes easy, and the trade-off underneath the argument that neither side can escape.
  3. The principles of object orientationEncapsulation, inheritance, polymorphism and SOLID, one at a time: what each actually claims, which held up, and which its own community abandoned.
  4. Types: what they can and cannot proveA type checker proves one thing about every possible run of your program. Knowing which proposition explains both the enthusiasm and the disappointment.
  5. Null, and the mistake its inventor apologised forTony Hoare called it his billion-dollar mistake. What was actually wrong with it, what the alternatives cost, and why the fix took forty years to arrive.
  6. What abstraction costsAbstraction is sold as free and is not. What you buy, what you pay, and how to tell before writing it which of the two is larger.
  7. Immutability, and what it is not free ofValues that never change buy sharing, comparison and time travel. They are not free, and it is worth knowing where they are expensive before you commit.
  8. Recursion, and why it feels like cheatingA function that calls itself looks like an unpaid debt. What makes it terminate, what it costs on the stack, and why some problems resist any other shape.
  9. Big-O, and what it deliberately ignoresComplexity notation throws away constants, hardware and every input you will actually see. Knowing what it discards is what makes the number useful.
  10. What regular expressions cannot matchThere is a precise boundary around what a regex can recognise. It explains the famous refusal to parse HTML, and why some patterns run forever.
  11. Concurrency is not parallelismOne is a way of structuring a program, the other a way of executing it. Keeping them apart explains why async helps a web server and threads often do not.
  12. Errors: exceptions, values, and what each hidesThrowing makes the happy path readable and the failure paths invisible. Returning errors as values does the opposite. Neither side has won.
  13. Why programs are hard to changeSoftware is called soft because it can be edited. Why editing gets harder every year, what the mechanism is, and which of the usual remedies work.

← All lecturesAtrium