Lesson S5 · Special topics

Inside a compiler

Open up a real, tiny compiler and watch one expression, x + 2 * 3, change shape at every stage. A lexer cuts it into tokens, a recursive-descent parser builds an abstract syntax tree, a type checker marks every node int, and the tree is flattened into intermediate code. The optimiser folds 2 * 3 into 6 before the program ever runs, and the code generator writes three instructions for a stack machine, which runs them to get 10. Finally, see why compilers such as LLVM split into a front end and a back end.

14 min10 steps5 questionsAdvanced

Fig S5 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01What does the lexer produce from x + 2 * 3?

The lexer only groups characters into tokens, the words of the language, and drops the spaces. Building the tree is the parser's job.

02In the recursive-descent parser, why does 2 * 3 end up below + in the tree?

Each grammar rule is a function. term handles *, and expr handles + by calling term, so 2 * 3 is built as one branch first and + joins x to it.

03What does constant folding do to t1 = 2 * 3?

2 * 3 uses only constants, so the compiler can work it out before the program runs. The answer stays the same; the running program just has less to do.

04The stack machine runs LOAD x, PUSH 6, ADD with x = 4. What is on the stack at the end?

LOAD x pushes 4, PUSH 6 pushes 6, and ADD pops both and pushes their sum, 10.

05In LLVM, what do you write to support a brand-new kind of processor?

Front ends read a language and write LLVM IR; back ends turn that IR into one machine's code. A new chip needs a new back end, and every language with an LLVM front end can then use it.

Key terms

Glossary

Lexer: The first stage of a compiler: it reads characters and groups them into tokens, such as names, numbers and operators.
Recursive-descent parser: A parser with one function per grammar rule; the functions call each other, following the grammar, to build the syntax tree.
Abstract syntax tree (AST): A tree of the program's operators and values. Spacing and brackets are gone; the tree's shape shows what is worked out first.
Type checking: Making sure every operation gets values of the right type, for example that + gets two numbers, before any code runs.
Intermediate representation (IR): The compiler's own simple in-between form of the program, such as three-address code: t1 = 2 * 3.
Constant folding: Working out expressions made only of constants, such as 2 * 3, at compile time instead of every time the program runs.
Stack machine: A machine that keeps its working values on a stack: instructions push values on top and take them off the top.
Front end / back end: The front end reads one language and writes IR; the back end turns IR into code for one kind of machine.

Fine print

Notes and sources

The language is tiny on purpose: whole numbers, names, + and * (and brackets). Both source lines are also valid Python, and Python gives the same answer, 10. The figure compiles line 2 only; line 1 would become PUSH 4 and a STORE x instruction, which this tiny machine leaves out.
Python's own parser builds the same shape for line 2: BinOp(left=Name(id='x'), op=Add(), right=BinOp(left=Constant(value=2), op=Mult(), right=Constant(value=3))).
Constant folding, constant propagation (copying the 6 into the next line) and dead-code removal (dropping t1) are three separate optimisations; the figure shows them together. CPython folds this expression too: dis shows the constant 6 and no multiply.
Many compilers, LLVM among them, count the optimiser as a third, middle phase between the front end and the back end. Real back ends also choose registers and machine instructions instead of a stack. The IR is the hand-off between the two ends: the front end writes it and the back end reads it, so the figure sets the IR card at the start of the back-end plate, where the front end passes it over.
The stack machine is a model, like the operand stack of the Java virtual machine or the stack CPython's bytecode runs on. A CPU chip runs machine code; a back end for a real chip writes that instead.

Quiz Unlocks after the last step.