← all systems · see it in The System
Compiler
In computing, a compiler is software that translates computer code written in one programming language (the source language) into another language (the target language), mainly from a high-level language to a low-level one (assembly, object or machine code) to create an executable program. The practice (compiler writers, testers, verifiers) and the structure (phases, representations, theory) are both walked.
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Compilers and interpreters |
| born at | 1951-1952 (Böhm's thesis 1951; A-0 May 1952; Glennie's Autocode 1952); first commercially available optimising compiler April 1957 (FORTRAN) |
| born precision | years |
| boundary | Inside: the translator itself (preprocessor, lexer, parser, semantic analyser and symbol table, intermediate representations, optimiser, back end with register allocator, instruction selector and scheduler, code and debug-data generator), the theory it is built from as held in its code, and the practice of the people who build, test and verify it. Outside: the programmer and the source program (input), the language definition (partner), the target processor and operating system, the linker and loader, the programs it produces (software, its fate), interpreters (a sibling kind), and attackers. Where compiling ends and interpreting begins is contested (C-2576). |
| nested level | Built from front, middle and back ends; part of a programming language's implementation (the language walk's L5) and of software's run-time and translation floor (software L4); its output is machine code, software's L2. |
| scale | technological |
Measures (21) published science
| characteristic clock: one compilation of a 47-statement FORTRAN job (IBM 704, 1957) | 6 minutes |
| machine instructions out per FORTRAN statement in | about 4 to 20 instructions per statement |
| coding-time reduction, assembly vs FORTRAN | about 4 to 20 ratio |
| FORTRAN I development effort | 18 man-years over two and one-half years |
| index registers on the IBM 704 | 3 registers |
| slowdown of early automatic programming systems (before FORTRAN) | 5 to 10 times slower |
| share of 704 machine instructions produced by FORTRAN (fall 1958) | more than half of instructions, on some 60 installations with about 66 704s |
| share of computer time spent debugging (1954) | one-quarter to one-half of machine time; programming and debugging up to three-quarters of operating cost |
| CompCert formal proof size | 42000 lines of Coq; about 3 person-years; 76% of it the correctness proof lines; person-years |
| CompCert code speed against GCC | 7% slower than gcc -O1; 12% slower than gcc -O2 (average, PowerPC) percent |
| compiler bugs found by random differential testing | more than 325 over three years bugs |
| testing spent on CompCert without finding a wrong-code bug | about 6 CPU-years |
| JIT VM-benchmark pairs that consistently reach a steady state of peak performance | at most 43.5 percent |
| Proebsting's law: compiler optimisation doubling time | 18 years (about 4% a year, against hardware's roughly 60% a year) |
| mean energy per benchmark solution: compiled languages | 120 J |
| mean energy per benchmark solution: virtual-machine languages | 576 J |
| mean energy per benchmark solution: interpreted languages | 2365 J |
| phase-ordering search space pruned by removing order-irrelevant phases | 89% on average percent |
| general-purpose registers, 64-bit x86 and 64-bit ARM | 16; 31 registers |
| student solutions analysed in the error-message study | 6339 solutions |
| characteristic clock: bootstrap stages to a self-hosting compiler | 3 to 4 stages |
Open contentions (2) open contention
Where sources or readings disagree. Both stay on the map.
- C-2586 Which was the first compiler?
booked: The map keeps the competing readings; none is ruled.
the other reading: Corrado Böhm's 1951 thesis: 'The first practical compiler' (src:wp:history-of-compiler-construction); Grace Hopper's A-0, May 1952, which coined the word but 'functioned more as a loader or linker than the modern notion of a full compiler' (src:wp:compiler); Alick Glennie's Autocode, 1952: 'compiler in the modern sense' (src:wp:history-of-compiler-construction, citing Knuth and Trabb Pardo); Laning and Zierler's system: 'the world's first operating algebraic compiler' (src:backus-1978-fortran-history), who could not recognise Glennie's AUTOCODE as algebraic; FORTRAN 1957: 'the first unambiguously complete compiler' (src:wp:compiler) - C-2606 How much do compiler optimisations really speed programs up?
booked: The map keeps the competing readings; none is ruled.
the other reading: Proebsting: optimisation advances 'double computing power every 18 years', about 4% a year against hardware's 60%, 'only marginal contributions' (an essay on the author's own assumed 4x and 36 years); Backus: FORTRAN I's optimisation was what made compiled code acceptable ('our emphasis on object program efficiency rather than on language design was basically correct'); CompCert's code is more than twice as fast as GCC without optimisations (src:leroy-2009-compcert)
Partners and parts published science
Built from / builds (13)
- Software
- Programming language
- Preprocessor
- Lexical analyzer (lexer, scanner)
- Parser
- Symbol table
- Intermediate representation
- Optimizer (middle end)
- Register allocator
- Code generator (back end)
- Compiler writers, testers and verifiers
- Compiled code against hand coding for the IBM 704 workload (1954-1958)
- Subverters and verifiers over compiler binaries
Sits inside / holds (3)
- Software
- Programming language
- Computer science (the field: the practice and the computation it studies)
Trades with (valence) (11)
- Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature via sys:written-record · Compiler gain
- Central processing unit via sys:computer-hardware · Compiler gain
- Human (Homo sapiens) via sys:written-record · Compiler gain
- Software via sys:electromagnetic-field · Compiler gain
- Operating system via sys:computer-hardware · Compiler gain
- Programming language via sys:written-record · Compiler gain
- Computer security via sys:software · Compiler loss
- Artificial intelligence via sys:written-record · Compiler gain
- Interpreter via sys:written-record · Compiler gain
- Logic gate via sys:written-record · Compiler gain
- Computer science (the field: the practice and the computation it studies) via sys:written-record · Compiler gain
expressed by (22)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Quality Improvement/Refinement
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Amplification/Scale-Up (Manufacture & Distribution)
- Evolvability/Plasticity Engineering (Design for Future Variation)
- Sensing/Scanning
- Mapping/Modeling
- Uncertainty Reduction/Learning
- Trail-Marking / Externalized Memory (Stigmergy)
- Offline Simulation & Replay-Guided Planning
- Physical/Virtual Barrier
- Self-Monitoring
- Validation of Identity/Intention
- Validation of Effectiveness
- Resilience & Repair
- Redundancy & Diversity
- Triage & Prioritized Allocation
- Quality Control & Error Correction
floor filled by (26)
- Computer memory
- Software
- Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature
- Central processing unit
- Programming language
- Human (Homo sapiens)
- Written record (durable external marks: texts, archives, canon)
- Operating system
- Artificial intelligence
- Type system
- Just-in-time compiler
- Formal grammar
- Proof assistant (Metamath, Lean, Isabelle and the like)
- Data structure
- Preprocessor
- Lexical analyzer (lexer, scanner)
- Parser
- Symbol table
- Intermediate representation
- Optimizer (middle end)
- Register allocator
- Code generator (back end)
- Static single-assignment form
- Linker
- Parser generator (Yacc)
- Finite-state automaton
Kinds (13)
- Software
- Interpreter
- Just-in-time compiler
- Cross-compiler
- Bootstrap compiler
- Source-to-source compiler (transpiler)
- Bytecode compiler
- Hardware compiler (synthesis tool)
- Compiler-compiler
- Optimizing compiler
- One-pass compiler
- Verified compiler
- Molecular (DNA circuit) compiler
wired (6)
- Programming language
- Libraries and packages
- Machine code
- Type system
- Specification
- Programmers and language communities
Notes published science
- When FORTRAN's makers first saw what their own compiler produced in 1956-57, they were 'often astonished': it rearranged the arithmetic and indexing in ways 'we would not have thought to make as programmers ourselves'. One unlabelled deck reached a lab that got it running by guesswork, and its first act was to point out a missing comma (src:backus-1978-fortran-history).
- A compiler can be taught a fact and then forget where it learned it: Ken Thompson showed a C compiler could keep inserting a trojan into every new compiler it built, with no trace in any source code ('No amount of source-level verification or scrutiny will protect you'). The cure, decades later, is to compile the compiler twice with a second, independent compiler and check the bits match (src:thompson-1984-trusting; src:wheeler-2009-ddc).
- Random test programs made every C compiler tested crash and silently produce wrong code, except one: CompCert, whose optimiser is mathematically proved correct, survived about six CPU-years of trying (src:yang-2011-csmith; src:leroy-2009-compcert).
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
a compiler as compiler writers describe it: the source program in, through the front, middle and back ends, to the target program out (reader's view)
- L1: The source program: characters in source files (and included files), written by programmers or generated by tools
- L2: Lexical analysis: the scanner (lexer), a finite-state automaton built from regular expressions, breaks text into tokens; the preprocessor works on tokens here in C
- L3: Syntax analysis: the parser builds a parse tree, then an abstract syntax tree, by the context-free grammar's rules (LL or LR parsing)
- L4: Semantic analysis: the symbol table, type checking, name binding; incorrect programs rejected; the front end's output, the intermediate representation
- L5: The middle end (optimizer): analysis (control-flow and call graphs, data-flow, SSA) and machine-independent optimisation of the IR
- L6: The back end: machine-dependent optimisation, instruction selection, register allocation, instruction scheduling, code generation and debug data
- L7: The target program: an executable (object or machine code, or bytecode, or a netlist) that should behave as the source's semantics prescribe, handed to the machine, the OS and the programmer
the boardroom (shared floors)
- L4: The front end's top: semantic analysis and the symbol table; names bound, types checked, incorrect programs rejected, the intermediate representation built
- L5: The middle end: analysis and machine-independent optimisation of the IR, steered by options, profiles and cost models
- L6: The back end: machine-dependent optimisation, instruction selection, register allocation and scheduling, code generation
- L7: The translation as delivered: a target program that should behave as the source's semantics prescribe; its correctness tested, and in one compiler proved
way in: Execution profiles (how often each part of the program runs)
- L1: The compiled program running on real inputs, at end-users' sites or inside a virtual machine
- L2: Counts of how often each block or path runs (FORTRAN I simulated them; a JIT counts them live)
- L3: Frequencies per basic block or hot path
- L4: Profile information made available to the compiler's transformations at link time, run time and between runs
way in: Included files and macros (the preprocessor's input)
- L1: Header files, macro definitions and conditional-compilation directives
- L2: The preprocessor substitutes macros on lexical tokens
- L3: The expanded text is parsed with the program
way in: Learned models (machine-learned heuristics)
- L1: Programs compiled and run many times to gather training data
- L2: Features extracted from each program
- L3: A model trained to predict good options
- L4: Deployed inside the compiler as its cost function
way in: Test programs and bug reports (validation suites, random differential tests, field reports)
- L1: Test programs: validation suites, randomly generated C programs (Csmith), users' failing programs
- L2: Compiled by several compilers
- L3: The executables are run and their outputs compared
- L4: A mismatch or crash marks a compiler bug
- L5: Bugs reported to the compiler's developers
- L6: Developers track the fault to the compiler section that owns it and issue a fix
way in: The compiler's own source (bootstrapping)
- L1: The compiler's source, written in the language it compiles
- L2: Lexed by the current compiler binary (stage 1 is 'enough to translate its own source')
- L3: Parsed like any other program; Hart and Levin's LISP compiler first ran on itself inside an interpreter
way in: The language's definition (grammar and rules), arriving when the compiler is built
- L1: The language definition: a grammar in Backus-Naur form (first used for ALGOL 60) and the semantic rules
- L2: A parser generator (compiler-compiler, e.g. Yacc) reads the grammar
- L3: The generated lexer and parser are installed as the front end's doors
way in: The source program written by programmers
- L1: Characters in source files
- L2: The lexer turns characters into tokens
- L3: The parser turns tokens into a tree
way in: The target machine (instruction set, registers, operating system)
- L1: The processor's instruction set and register file (e.g. 16 general-purpose registers on 64-bit x86, 31 on 64-bit ARM)
- L2: Described to the back end as the machine's details
way in: The user's options (optimisation level, target, flags)
- L1: Options typed on the command line or set in a build
- L2: Read by the compiler before it runs its passes; some optimisations are skipped by default
way out: A hardware configuration (hardware compilers)
- L1: The configured interconnection of transistors or lookup tables
- L6: A netlist describing a hardware configuration
way out: A new compiler (when the compiler compiles itself)
- L1: The new compiler replaces the old one as the official compiler
- L7: The full compiler produced from its own source
way out: Bytecode for a virtual machine
- L1: Executed by a bytecode interpreter or JIT-compiled later
- L5: The program delivered in a machine-independent intermediate form
way out: Debug data for debuggers
- L1: Read by a debugger to map the running program back to its source
- L6: Debug data generated with the code
way out: Error and warning messages to the programmer
- L1: A message on screen, often cryptic to learners
- L4: A syntax or type error is detected
way out: Machine code (or object code) to the processor
- L1: Loaded and executed on the processor
- L6: Code generation selects and schedules instructions and assigns registers
- L7: The executable target program is emitted
Sources (23) published science
History of compiler construction (Wikipedia, via Wikimedia Enterprise) (behind its links)
Leroy X 2009. Formal verification of a realistic compiler. Communications of the ACM 52(7):107-115, doi:10.1145/1538788.1538814 (author's copy) (behind its links)
Yang X, Chen Y, Eide E, Regehr J 2011. Finding and understanding bugs in C compilers. PLDI 2011, doi:10.1145/1993498.1993532 (authors' preprint) (behind its links)
Proebsting T. Proebsting's Law: compiler advances double computing power every 18 years (author's web essay, University of Arizona) (behind its links)
Pereira et al. 2017, Energy Efficiency across Programming Languages, SLE'17, doi:10.1145/3136014.3136031 (behind its links)
Wang Z, O'Boyle M 2018. Machine learning in compiler optimisation. Proceedings of the IEEE 106(11). arXiv:1805.03441 (behind its links)
Register allocation (Wikipedia, via Wikimedia Enterprise) (behind its links)
Bootstrapping (compilers) (Wikipedia, rev 1323208297, 2025-11-20, via Wikimedia Enterprise) (behind its links)
Wheeler 2009. Fully Countering Trusting Trust through Diverse Double-Compiling (PhD dissertation, CC BY-SA). arXiv:1004.5534 (behind its links)
Software (encyclopedia) (behind its links)
Programming language (Wikipedia via Wikimedia Enterprise, cached research/showcase/cache/wme) (behind its links)
Lattner C, Adve V 2004. LLVM: a compilation framework for lifelong program analysis & transformation. CGO 2004, doi:10.1109/CGO.2004.1281665 (authors' copy) (behind its links)
Optimizing compiler (Wikipedia, via Wikimedia Enterprise) (behind its links)
Thompson K 1984. Reflections on trusting trust (Turing Award lecture). Communications of the ACM 27(8):761-763. doi:10.1145/358198.358210 (behind its links)
Recursion (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Wikipedia: Central processing unit (behind its links)
Logic gate (Wikipedia, WME snapshot) (behind its links)