- Atlas
- Computer Science
- Compiler Design
Compiler Design
A compiler is a program that reads source code in one language and writes an equivalent program in another—usually machine code or something close to it.
12 frameworks, from 1959 to today · Programming Languages · Computer Science
- Formal grammar and parsing theory 1959-Present
- Interpreters and bytecode virtual machines 1960-Present
- Phase-based compilation pipeline 1960-Present
- Semantic analysis 1960-Present
- Dataflow analysis and optimizing transformation 1968-Present
- Parser generators and compiler-compilers 1968-Present
- Intermediate representations and SSA 1970-Present
- Register allocation and instruction scheduling 1975-Present
- Retargetable compiler infrastructure 1987-Present
- Just-in-time compilation 1990-Present
- Verified compilation 2005-Present
- Machine-learning-guided compilation 2013-Present
Overview
A compiler is a program that reads source code in one language and writes an equivalent program in another—usually machine code or something close to it12. Compiler design is the craft and science of building these translators: how to read a program's text, check that it makes sense, reshape it so it runs fast, and emit instructions a processor can execute1. The stakes are enormous. Every language feature a designer dreams up must eventually be made real by a compiler, and the difference between a naive translation and a well-optimized one can be a factor of ten or more in speed. The history of compiler design is therefore a history of ideas about how to make translation correct, automatic, and fast—three goals that have pulled against each other for seventy years.
From hand-written code to the first compilers, 1940s–1950s
In the earliest electronic computers, programmers wrote machine instructions directly, often in octal or binary, and "assembly" was done by hand. The first assemblers—programs that mapped mnemonic names to opcodes—appeared in the early 1950s and were a modest but crucial step: they automated the bookkeeping of addresses and instruction encoding. The idea that a program could translate a higher-level notation into machine code was initially met with skepticism, partly because early machines had tiny memories and partly because people doubted any automatic translator could produce code as good as a skilled hand coder.
The breakthrough came with FORTRAN, developed at IBM under John Backus and released in 19571. FORTRAN's compiler was a landmark not just because it translated a formula-oriented language, but because it optimized: it analyzed the flow of a program to keep frequently used values in registers and to simplify arithmetic. This established the central bargain of compiler design—that a compiler could, in principle, generate code competitive with hand-written assembly—and made high-level languages practical for scientific computing. Around the same time, the team led by Grace Hopper produced early compiler work (the A-0 system and later FLOW-MATIC), and the ALGOL effort in Europe and the US pushed language design and compilation forward together.
Formal grammar and the theory of parsing, late 1950s–1960s
A compiler's first job is to recognize structure in a stream of characters. Early compilers used ad hoc techniques, but the late 1950s brought a theoretical foundation. Noam Chomsky's work on formal grammars (from 1956 onward) classified languages by the rules needed to describe them, and this framework was taken up by computer scientists. John Backus and Peter Naur developed the notation now called BNF (Backus–Naur Form) for describing ALGOL 60's syntax, giving language designers a precise, machine-readable way to specify grammar.
The practical payoff came with parsing algorithms. The 1960s saw the development of methods that could mechanically turn a grammar into a recognizer: top-down techniques such as recursive descent, and bottom-up techniques including the operator-precedence method and, later, LR parsing, described by Donald Knuth in 1965. LR parsing could handle a broad class of grammars efficiently and detect errors early. These ideas were codified in influential textbooks—notably the "dragon book" by Alfred Aho and Jeffrey Ullman (first edition 1977, later with Ravi Sethi and Monica Lam)—and parser generators such as yacc (Stephen Johnson, 1970s) let programmers write a grammar and have the parser produced automatically. Parsing became the most thoroughly formalized part of compilation.
Semantic analysis and the typed program, 1960s–1970s
Recognizing syntax is not enough; a compiler must check that a program means something coherent. Semantic analysis covers name resolution (which declaration does this identifier refer to?), type checking (does this operation make sense on these operands?), and the construction of symbol tables that record what each name denotes1. The rise of ALGOL 60 and its successors, with block structure and nested scopes, made scope resolution a real problem, and the development of typed languages—culminating in Pascal (Niklaus Wirth, 1970) and later strongly typed systems—made type checking central.
The theoretical underpinning came from type theory, but the compiler-design contribution was practical: algorithms for building and querying symbol tables, for checking type compatibility, and for inserting implicit conversions. Semantic analysis also became the stage where a compiler builds its internal representation of the program, connecting the front end (reading and checking) to the back end (generating code)1.
Intermediate representations and the phase-based pipeline, 1960s–1970s
As compilers grew, designers found it useful to break translation into distinct phases, each transforming one representation into another1. The canonical pipeline—lexical analysis, parsing, semantic analysis, intermediate code generation, optimization, code generation—became the standard architecture, described in textbooks and embodied in countless real compilers. The key idea is the intermediate representation (IR): a language-neutral form of the program, often a graph or a sequence of simple three-address instructions, that decouples the source language from the target machine.
IRs took several shapes. Control-flow graphs, in which nodes are basic blocks (straight-line instruction sequences) and edges are jumps, became the workhorse for analysis and optimization. Static single assignment (SSA) form, introduced by Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, and Kenneth Zadeck in 1991, rewrote each variable so it is assigned exactly once, with special "phi" functions merging values at control-flow joins. SSA made many analyses simpler and faster and became the dominant IR in modern optimizing compilers3. The phase-based pipeline itself is a design philosophy: each phase has a clear contract, which makes compilers easier to build, test, and retarget1.
Dataflow analysis and program optimization, 1960s–1980s
Optimization is where compilers earn their reputation. The foundational technique is dataflow analysis: computing, for each point in a program, facts such as which variables are live, which definitions reach which uses, and which expressions are available4. Frances Allen's work in the late 1960s and early 1970s, and the parallel work of John Cocke, established dataflow analysis as a systematic framework, and Gary Kildall's 1973 paper gave it a lattice-theoretic foundation. These analyses enabled a family of transformations: constant propagation, dead-code elimination, common-subexpression elimination, loop-invariant code motion, and strength reduction.
Loops received special attention because that is where programs spend most of their time5. Loop optimization—unrolling, fusion, interchange, and vectorization—became a major research area, especially for scientific code. The 1980s and 1990s brought more ambitious transformations, including inlining, partial evaluation, and profile-guided optimization, in which the compiler uses data from actual runs to decide where to focus effort. The tension throughout is between aggressiveness (more optimization) and predictability (compile time and code size), and different compilers have resolved it differently1.
Register allocation and instruction scheduling, 1970s–1990s
The back end of a compiler faces two tightly coupled problems. Register allocation decides which values live in the processor's small, fast registers and which spill to memory; instruction scheduling orders instructions to hide latency and exploit parallelism167. Early compilers used simple heuristics, but the 1980s brought graph-coloring register allocation, developed by Gregory Chaitin and colleagues at IBM (1981), which modeled interference between live values as a graph-coloring problem. Later refinements, including linear-scan allocation (Massimiliano Poletto and Vivek Sarkar, 1999), traded some quality for speed and became popular in just-in-time compilers.
Instruction scheduling interacts with allocation because both depend on the same dependencies. List scheduling and software pipelining (especially modulo scheduling, developed in the 1980s and 1990s) became standard for exploiting instruction-level parallelism. These back-end problems are where compiler design meets computer architecture most directly: as processors added pipelines, caches, and multiple issue slots, the compiler's job of arranging instructions grew more consequential.
Retargetable compilers and the GCC era, 1980s–1990s
For a long time, each new machine meant writing a new compiler. The retargetable compiler architecture changed that: separate the machine-independent middle (IR and optimizations) from a machine description that captures the target's instructions and costs18. The GNU Compiler Collection (GCC), begun by Richard Stallman in 1987, became the emblem of this approach, supporting many languages and many architectures from a shared infrastructure. GCC's success demonstrated that a well-factored compiler could be ported widely and improved collaboratively.
A parallel development was LLVM, started by Chris Lattner at the University of Illinois in 2000 and later industrialized9. LLVM's design—a typed SSA-based IR with a clean library architecture—made it easy to build new front ends and new back ends, and it became the foundation for many languages and tools. The retargetable philosophy is now standard: a compiler is a framework, and a new language or a new chip plugs into it.
Interpreters, just-in-time compilation, and adaptive optimization, 1990s–2000s
Not all programs are compiled ahead of time. Interpreters execute a program directly, instruction by instruction, which is simple and portable but slow. The middle ground is just-in-time (JIT) compilation: translate code to machine instructions at run time, often only for the parts that are actually hot110. The Self project (David Ungar and Randall Smith, 1980s–1990s) pioneered adaptive optimization—starting with an interpreter, profiling execution, and recompiling hot code with more aggressive optimizations. Java's HotSpot virtual machine (late 1990s) brought this to a mass audience, and modern JavaScript engines (V8, SpiderMonkey) and the Java Virtual Machine rely on it.
Adaptive optimization raises new design questions: how to gather profiles cheaply, when to recompile, how to deoptimize (fall back to a slower version) when assumptions fail, and how to keep compilation latency low enough for interactive programs. These questions are now central to compiler design for dynamic languages.
Verified compilation, 2000s–present
A compiler bug can silently corrupt a program, and for safety- or security-critical software that is unacceptable. Verified compilation aims to prove, with machine-checked mathematics, that the compiler's output behaves as the source language's semantics require111. The landmark is CompCert, developed by Xavier Leroy and colleagues from the mid-2000s: a compiler for a large subset of C, written and proved correct in the Coq proof assistant. CompCert showed that formal verification of a realistic optimizing compiler is feasible, and it inspired a generation of work on verified parsing, verified instruction selection, and verified JITs. The approach is demanding—every optimization must come with a proof—but it has changed how the field thinks about compiler correctness.
Machine-learning-guided compilation, 2010s–present
The newest turn applies machine learning to decisions that were traditionally hand-tuned heuristics: which optimization passes to run and in what order, how to schedule instructions, how to allocate registers, and how to choose inlining thresholds. Early work used supervised learning to predict good choices from features of the code; later work used reinforcement learning, notably in the compiler-autotuning systems developed around 2018–2020, where a learned policy selects optimization sequences. These methods can outperform hand-tuned heuristics on some benchmarks, but they raise questions of generalization, interpretability, and trust—especially when combined with verification. The field is still working out where learning genuinely helps and where classical analysis remains superior.
The present: a layered, collaborative, still-open craft
Today's compiler design is layered and modular1. Front ends parse and type-check; middle ends use SSA-based IRs and dataflow analyses to optimize; back ends allocate registers and schedule instructions for specific machines. Retargetable frameworks such as LLVM and GCC dominate, JITs and adaptive optimization serve dynamic languages, and verified compilation offers a path to trust for critical code. Machine learning is being folded in as another tool in the optimizer's kit.
Open questions remain. How can compilers be made both aggressive and predictable1? How should verification scale to the full complexity of modern optimizers? Can learned policies be made reliable enough for production? And as hardware grows more heterogeneous—GPUs, accelerators, specialized instructions—the back end's job of mapping programs onto machines keeps getting harder. The history of compiler design is a history of turning hard translation problems into systematic, automatable ones; that work is far from finished.
References
- Compiler (introduction, History, Front end, Three-stage compiler structure, Compiler construction, Middle end, Types, Compiler correctness), Wikipedia
- History of compiler construction, Wikipedia
- Static single-assignment form, Wikipedia
- Data-flow analysis, Wikipedia
- Loop optimization, Wikipedia
- Register allocation, Wikipedia
- Instruction scheduling, Wikipedia
- Retargeting, Wikipedia
- LLVM (History), Wikipedia
- Just-in-time compilation, Wikipedia
- Compiler correctness, Wikipedia
The frameworks of Compiler Design
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1959-Present
Formal grammar and parsing theory
How can a grammar mechanically recognize a program's structure?
- 1960-Present
Interpreters and bytecode virtual machines
How can a program be executed directly from its source form?
- 1960-Present
Phase-based compilation pipeline
How should translation be divided into stages?
- 1960-Present
- 1968-Present
Dataflow analysis and optimizing transformation
Which program facts let a compiler safely rewrite code?
- 1968-Present
Parser generators and compiler-compilers
How can a tool build a parser from a grammar?
- 1970-Present
Intermediate representations and SSA
What form should a program take inside a compiler?
- 1975-Present
Register allocation and instruction scheduling
How should values be placed in registers and instructions ordered?
- 1987-Present
Retargetable compiler infrastructure
How can one compiler serve many different machines?
- 1990-Present
Just-in-time compilation
How can code be compiled while the program runs?
- 2005-Present
- 2013-Present
Machine-learning-guided compilation
Can a compiler learn its own optimization heuristics?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Parser generators and compiler-compilers grew out of Formal grammar and parsing theory
Parser generators mechanized the grammar-to-recognizer methods of formal parsing theory; yacc (Stephen Johnson, 1970s) turned an LR grammar into a parser automatically, making the theory directly executable.
Carried by Stephen C. Johnson; yacc.
Intermediate representations and SSA grew out of Phase-based compilation pipeline
The phase-based pipeline introduced intermediate code generation as a distinct stage, and the intermediate representation grew out of that stage as the language-neutral form passed between front and back ends.
Phase-based compilation pipeline influenced by Formal grammar and parsing theory
Grammar-based parsing supplied the front-end phase of the canonical pipeline; lexical analysis and syntax analysis were defined as distinct phases using formal-language methods.
Carried by Alfred V. Aho; Jeffrey D. Ullman.
Semantic analysis influenced by Formal grammar and parsing theory
Formal grammar and BNF gave compilers a precise syntax to parse before semantic checking; the parse tree produced by grammar-based parsing became the structure on which name resolution and type checking operate.
Carried by John Backus; Peter Naur.
Dataflow analysis and optimizing transformation grew out of Phase-based compilation pipeline
The optimization phase of the phase-based pipeline became the home of dataflow analysis and transformation; separating optimization as its own phase made systematic program analysis possible.
Carried by Frances E. Allen.
Register allocation and instruction scheduling grew out of Phase-based compilation pipeline
The code-generation phase of the pipeline was split into register allocation and instruction scheduling as back-end subproblems once the phase structure separated machine-dependent from machine-independent work.
Retargetable compiler infrastructure grew out of Phase-based compilation pipeline
Retargetable compilers generalized the phase-based pipeline by making the machine-independent middle explicit and isolating the target description in the back end, as in GCC's architecture.
Carried by Richard Stallman; GNU Compiler Collection.
Intermediate representations and SSA influenced by Dataflow analysis and optimizing transformation
Dataflow analysis problems such as reaching definitions and live variables motivated SSA form, which Cytron, Ferrante, Rosen, Wegman and Zadeck designed to make these analyses simpler and faster.
Carried by Ron Cytron; Jeanne Ferrante; Barry Rosen.
Register allocation and instruction scheduling influenced by Dataflow analysis and optimizing transformation
Liveness analysis from dataflow provided the interference information that graph-coloring register allocation used to build its interference graph.
Carried by Gregory J. Chaitin.
Just-in-time compilation influenced by Dataflow analysis and optimizing transformation
Just-in-time compilers adopted dataflow-based optimizations and, later, linear-scan register allocation derived from liveness analysis to optimize hot code at run time.
Carried by Massimiliano Poletto; Vivek Sarkar.
Machine-learning-guided compilation influenced by Dataflow analysis and optimizing transformation
Machine-learning-guided compilation applies learned models to the heuristic decisions of optimization and dataflow-driven transformation, such as inlining and unrolling choices.
Retargetable compiler infrastructure influenced by Intermediate representations and SSA
Retargetable compilers such as GCC built their machine-independent middle on intermediate representations, and later infrastructures like LLVM made a typed SSA IR the central retargetable interface.
Carried by Chris Lattner; LLVM.
Just-in-time compilation influenced by Intermediate representations and SSA
JIT compilers adopted SSA-based intermediate representations to perform analyses and optimizations on hot methods at run time, as in modern Java and JavaScript engines.
Verified compilation influenced by Intermediate representations and SSA
Verified compilers such as CompCert formalize each translation over an intermediate representation, proving that SSA-based and other IR transformations preserve semantics.
Carried by Xavier Leroy; CompCert.
Just-in-time compilation influenced by Register allocation and instruction scheduling
Linear-scan register allocation, developed for static compilers, was adopted by JIT compilers because its speed suited compilation at run time.
Carried by Massimiliano Poletto; Vivek Sarkar.
Just-in-time compilation influenced by Retargetable compiler infrastructure
JIT compilers reused retargetable compiler infrastructure and machine descriptions to generate code for the host machine at run time, as in early Java JITs built on existing back ends.
Verified compilation influenced by Retargetable compiler infrastructure
Verified compilation efforts such as CompCert were built as retargetable compilers with a machine-independent middle whose phases could be proved correct separately.
Carried by Xavier Leroy; CompCert.
Machine-learning-guided compilation influenced by Register allocation and instruction scheduling
Machine-learning approaches have been applied to back-end decisions such as instruction scheduling and register allocation, learning heuristics where hand-tuned ones were used.
Machine-learning-guided compilation influenced by Retargetable compiler infrastructure
Learned compilation research often targets retargetable infrastructures such as LLVM, using their IR and pass structure as the environment for learned heuristics.
Carried by LLVM.
Beyond the field
Where Compiler Design's ideas came from in other fields, and what they led to there: the strongest 12 of 44 links.
Formal grammar and parsing theory influenced ALGOL 60 in Language Design
The ALGOL 60 report introduced Backus-Naur Form to define the language's syntax, and this formal grammar notation became the basis of parsing theory and compiler construction. BNF directly enabled the development of formal parsing methods.
Carried by John Backus; Peter Naur; ALGOL 60 Report (1960).
Formal grammar and parsing theory influenced by Generative Grammar in Linguistics
Chomsky's generative grammar, especially the 1956-57 formalization of phrase-structure and transformational rules, supplied the model of grammar that early parsing work in computer science took up. His formalization of context-free grammars was directly adopted as a parsing formalism.
Carried by Noam Chomsky; Syntactic Structures (1957).
Formal grammar and parsing theory influenced by Formal Foundations of Computation and Logic in Computational Logic
Turing machines, recursive function theory and Post's production systems from mathematical logic provided the formal machinery of grammars and automata that parsing theory built on. Chomsky explicitly drew on Post and on recursive function theory when defining the grammar hierarchy.
Carried by Alan Turing; Emil Post; Noam Chomsky.
Register allocation and instruction scheduling influenced by General-register architecture in Instruction Set Architecture
Register allocation exists as a compiler problem because general-register architectures replaced accumulator machines, forcing compilers to map many virtual values onto a small fixed set of registers. Graph-colouring allocation and later scheduling work are defined against that register file.
Carried by John Cocke; Gregory Chaitin.
Verified compilation influenced by Mechanized semantics in Pl Semantics
Verified compilation depends on mechanized semantics of source and target languages, since correctness theorems are stated and proved against formal semantics in a proof assistant. Mechanized semantics supplies the objects the compiler proof relates.
Carried by Xavier Leroy.
Verified compilation influenced by Formal verification in Programming Languages
Verified compilation applies formal verification to compilers, proving that a compiler preserves semantics; it grew directly out of the formal-verification tradition in programming languages. CompCert is the landmark result carrying that method to compilers.
Carried by Xavier Leroy; CompCert.
Formal grammar and parsing theory influenced Constraint-based parsing in Psycholinguistics
Constraint-based parsing in psycholinguistics borrowed from formal grammar and parsing theory the notion of parsing as satisfaction of simultaneous grammatical constraints rather than serial rule application. The computational formalism supplied the architecture the psycholinguistic models adopted.
Formal grammar and parsing theory influenced Garden-path parsing models in Psycholinguistics
Garden-path parsing took from formal grammar and parsing theory the idea of a deterministic parser with a grammar-driven choice among alternatives, as in the computational parsing work of the period. The psycholinguistic models borrowed the architecture of formal parsers to explain human misanalysis.
Formal grammar and parsing theory influenced Tree-Adjoining Grammar in Syntax
TAG drew on formal grammar and parsing theory from computer science, and its parsers were developed in the same formal-language tradition that produced compiler parsing algorithms.
Carried by Aravind Joshi.
Formal grammar and parsing theory influenced by Context-free grammars and pushdown automata in Automata
Parsing theory for compilers adopted context-free grammars and pushdown automata as its formal basis, carrying the automata results into practical parser construction.
Carried by John Backus.
Interpreters and bytecode virtual machines influenced Vectorized and compiled execution in Query Processing
Vectorized execution was framed as an alternative to the tuple-at-a-time interpreter model that bytecode virtual machines embody, and the comparison to virtual machine dispatch overhead drove the design. The X100 paper measured and argued against interpreter overhead in query engines.
Carried by Marcin Zukowski; Peter Boncz.
Interpreters and bytecode virtual machines influenced by Digital Logic and Computer Architecture in Electrical Engineering
The stored-program architecture and its instruction-set model gave interpreters their basic execution loop: fetch an instruction, decode it, and perform the operation. Early interpreters such as those for Lisp were built directly on this machine model.
Carried by John McCarthy.

Compiler Design is a planet in Nousfarer
Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.
Land on Compiler DesignRelated fields
Fields its ideas are linked to
- Instruction Set Architecture 7 links
- Language Design 6 links
- Computer Architecture 5 links
- Query Processing 5 links
- Programming Languages 5 links
- Linguistics 2 links
- Psycholinguistics 2 links
- Syntax 2 links
- Pl Semantics 2 links
- Microarchitecture 1 link
- Digital Systems 1 link
- Electrical Engineering 1 link
More in Programming Languages
- Concurrency Models
- Language Design
- Pl Semantics
- Program Analysis
- Programming Languages
- Programming Paradigms
- Type Systems
See where Compiler Design sits on the Map of Human Knowledge