01Overview
In 1952 Grace Hopper’s A-0 system translated symbolic code into machine code and is regarded as the forerunner of the compiler. In 1957 the FORTRAN compiler showed that generated code could compete with hand-written assembly. In the 1960s Chomsky’s formal-language theory gave lexical and syntactic analysis its mathematical basis.
A modern compiler is usually split into a front end (lexing, parsing, semantics), a middle end (intermediate representation and optimisation) and a back end (instruction selection, register allocation). SSA form, data-flow analysis and loop optimisation are its core. In 2000 LLVM modularised the infrastructure, and today JIT compilation and machine-learning-driven heuristics are changing how optimisation is done.
02History
- 1952
The A-0 system
A compiler pioneer.
- 1957
A FORTRAN compiler
Generated code reaches usable speed.
- 1960
Parsing theory
LL and LR analysis mature.
- 1986
The Dragon Book
The classic compiler textbook.
- 2000
LLVM
Modular compiler infrastructure.
03Core concepts
Lexical analysis
Cutting a character stream into tokens, usually with a finite automaton.
Intermediate representation
A program form independent of both source language and target machine, convenient for optimisation.
SSA
Each variable is assigned once, which simplifies data-flow analysis.
04Hands-on
Do it once — it beats reading it ten times
Write a compiler for a tiny expression language down to a stack machine, then run it
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Lexical analysis"?
Cutting a character stream into tokens, usually with a finite automaton.
Can you explain "Intermediate representation"?
A program form independent of both source language and target machine, convenient for optimisation.
Can you explain "SSA"?
Each variable is assigned once, which simplifies data-flow analysis.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Grace Hopper
1906 – 1992
A pioneer of compilers and COBOL.
Frances Allen
1932 – 2020
Optimising compilers and parallelisation.
07Further reading
- Compilers: Principles, Techniques, and Tools
- Advanced Compiler Design and Implementation