EVOPEDIA

← 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.

aliasesCompilers and interpreters
born at1951-1952 (Böhm's thesis 1951; A-0 May 1952; Glennie's Autocode 1952); first commercially available optimising compiler April 1957 (FORTRAN)
born precisionyears
boundaryInside: 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 levelBuilt 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.
scaletechnological

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 inabout 4 to 20 instructions per statement
coding-time reduction, assembly vs FORTRANabout 4 to 20 ratio
FORTRAN I development effort18 man-years over two and one-half years
index registers on the IBM 7043 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 size42000 lines of Coq; about 3 person-years; 76% of it the correctness proof lines; person-years
CompCert code speed against GCC7% slower than gcc -O1; 12% slower than gcc -O2 (average, PowerPC) percent
compiler bugs found by random differential testingmore than 325 over three years bugs
testing spent on CompCert without finding a wrong-code bugabout 6 CPU-years
JIT VM-benchmark pairs that consistently reach a steady state of peak performanceat most 43.5 percent
Proebsting's law: compiler optimisation doubling time18 years (about 4% a year, against hardware's roughly 60% a year)
mean energy per benchmark solution: compiled languages120 J
mean energy per benchmark solution: virtual-machine languages576 J
mean energy per benchmark solution: interpreted languages2365 J
phase-ordering search space pruned by removing order-irrelevant phases89% on average percent
general-purpose registers, 64-bit x86 and 64-bit ARM16; 31 registers
student solutions analysed in the error-message study6339 solutions
characteristic clock: bootstrap stages to a self-hosting compiler3 to 4 stages

Open contentions (2) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (13)

Sits inside / holds (3)

Trades with (valence) (11)

expressed by (22)

floor filled by (26)

Kinds (13)

wired (6)

Notes published science

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)

  1. L1: The source program: characters in source files (and included files), written by programmers or generated by tools
  2. 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
  3. 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)
  4. L4: Semantic analysis: the symbol table, type checking, name binding; incorrect programs rejected; the front end's output, the intermediate representation
  5. L5: The middle end (optimizer): analysis (control-flow and call graphs, data-flow, SSA) and machine-independent optimisation of the IR
  6. L6: The back end: machine-dependent optimisation, instruction selection, register allocation, instruction scheduling, code generation and debug data
  7. 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)

  1. L4: The front end's top: semantic analysis and the symbol table; names bound, types checked, incorrect programs rejected, the intermediate representation built
  2. L5: The middle end: analysis and machine-independent optimisation of the IR, steered by options, profiles and cost models
  3. L6: The back end: machine-dependent optimisation, instruction selection, register allocation and scheduling, code generation
  4. 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)

  1. L1: The compiled program running on real inputs, at end-users' sites or inside a virtual machine
  2. L2: Counts of how often each block or path runs (FORTRAN I simulated them; a JIT counts them live)
  3. L3: Frequencies per basic block or hot path
  4. 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)

  1. L1: Header files, macro definitions and conditional-compilation directives
  2. L2: The preprocessor substitutes macros on lexical tokens
  3. L3: The expanded text is parsed with the program

way in: Learned models (machine-learned heuristics)

  1. L1: Programs compiled and run many times to gather training data
  2. L2: Features extracted from each program
  3. L3: A model trained to predict good options
  4. L4: Deployed inside the compiler as its cost function

way in: Test programs and bug reports (validation suites, random differential tests, field reports)

  1. L1: Test programs: validation suites, randomly generated C programs (Csmith), users' failing programs
  2. L2: Compiled by several compilers
  3. L3: The executables are run and their outputs compared
  4. L4: A mismatch or crash marks a compiler bug
  5. L5: Bugs reported to the compiler's developers
  6. L6: Developers track the fault to the compiler section that owns it and issue a fix

way in: The compiler's own source (bootstrapping)

  1. L1: The compiler's source, written in the language it compiles
  2. L2: Lexed by the current compiler binary (stage 1 is 'enough to translate its own source')
  3. 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

  1. L1: The language definition: a grammar in Backus-Naur form (first used for ALGOL 60) and the semantic rules
  2. L2: A parser generator (compiler-compiler, e.g. Yacc) reads the grammar
  3. L3: The generated lexer and parser are installed as the front end's doors

way in: The source program written by programmers

  1. L1: Characters in source files
  2. L2: The lexer turns characters into tokens
  3. L3: The parser turns tokens into a tree

way in: The target machine (instruction set, registers, operating system)

  1. L1: The processor's instruction set and register file (e.g. 16 general-purpose registers on 64-bit x86, 31 on 64-bit ARM)
  2. L2: Described to the back end as the machine's details

way in: The user's options (optimisation level, target, flags)

  1. L1: Options typed on the command line or set in a build
  2. L2: Read by the compiler before it runs its passes; some optimisations are skipped by default

way out: A hardware configuration (hardware compilers)

  1. L1: The configured interconnection of transistors or lookup tables
  2. L6: A netlist describing a hardware configuration

way out: A new compiler (when the compiler compiles itself)

  1. L1: The new compiler replaces the old one as the official compiler
  2. L7: The full compiler produced from its own source

way out: Bytecode for a virtual machine

  1. L1: Executed by a bytecode interpreter or JIT-compiled later
  2. L5: The program delivered in a machine-independent intermediate form

way out: Debug data for debuggers

  1. L1: Read by a debugger to map the running program back to its source
  2. L6: Debug data generated with the code

way out: Error and warning messages to the programmer

  1. L1: A message on screen, often cryptic to learners
  2. L4: A syntax or type error is detected

way out: Machine code (or object code) to the processor

  1. L1: Loaded and executed on the processor
  2. L6: Code generation selects and schedules instructions and assigns registers
  3. L7: The executable target program is emitted

Sources (23) published science

Compiler (Wikipedia, rev 1373605841, 2026-09-06, via Wikimedia Enterprise)
Backus J 1978/1981. The history of FORTRAN I, II, and III. History of Programming Languages (ACM HOPL I), 25-74, doi:10.1145/800025.1198345 (Software Preservation Group copy) (behind its links)
History of compiler construction (Wikipedia, via Wikimedia Enterprise) (behind its links)
Backus JW, Beeber RJ, Best S, Goldberg R, Haibt LM, Herrick HL, Nelson RA, Sayre D, Sheridan PB, Stern H, Ziller I, Hughes RA, Nutt R 1957. The FORTRAN automatic coding system. Proceedings of the Western Joint Computer Conference, 188-198 (Computer History Museum Software Preservation Group copy) (behind its links)
Thubagere AJ, Thachuk C, Berleant J, Johnson RF, Ardelean DA, Cherry KM, Qian L 2017. Compiler-aided systematic construction of large-scale DNA strand displacement circuits using unpurified components. Nature Communications 8:14373, doi:10.1038/ncomms14373 (PMC5331218) (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)
Barrett E, Bolz-Tereick CF, Killick R, Mount S, Tratt L 2017. Virtual machine warmup blows hot and cold. Proceedings of the ACM on Programming Languages 1 (OOPSLA), doi:10.1145/3133876. arXiv:1602.00602 (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)
Zhou Z, Wang S, Qian Y 2021. Learning from errors: exploring the effectiveness of enhanced error messages in learning to program. Frontiers in Psychology 12:768962, doi:10.3389/fpsyg.2021.768962 (PMC8669433) (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)