Every program you have ever written in C, C++, Java or Go had to be turned into something the processor can actually run. Your CPU does not understand for loops, variables or printf. It only understands long sequences of bits that encode very simple instructions such as "add these two registers" or "jump to this address". The software that bridges this huge gap is the compiler.
In this chapter we will see what a compiler is, why we need one, what it looks like from the outside, the different kinds of compilers you meet in practice, and how a compiler for a brand-new language can be built (bootstrapping and T-diagrams). All the compiler outputs shown here are real: they were produced with GCC 15.2 on x86-64 Linux. (We added the options -fcf-protection=none -U_FORTIFY_SOURCE so that the extra security instructions some Linux distributions enable by default, such as endbr64 and __printf_chk, do not clutter the listings.)
What Is a Compiler?
A compiler is a program that reads a program written in one language (the source language) and translates it into an equivalent program in another language (the target language). While doing so, it reports any errors it finds in the source program.
Two words in this definition are very important:
Equivalent: the translated program must do exactly what the source program says. A compiler is allowed to change how the work is done (for speed or size), but never what result is produced.
Reports errors: a compiler is also a checker. Missing semicolons, undeclared variables and type mismatches are caught before the program ever runs.
+------------+
source program -->| COMPILER |--> target program
(e.g. C code) +------------+ (e.g. x86-64 machine code)
|
v
error messages
and warnings
Usually the source is a high-level language (C, C++, Rust, Java) and the target is machine code or assembly language for a particular processor. But the definition is general: the target can be another high-level language, a bytecode for a virtual machine, or even a hardware description.
Once the target program is produced, it can be run again and again on new inputs without the compiler being present:
input --> [ target program ] --> output
This "translate once, run many times" model is the key difference between a compiler and an interpreter, which we compare in detail in the next chapter, Language Processors: Interpreter, Assembler, Linker & Loader.
Why Do We Need Compilers?
A processor executes machine code: instructions encoded as bytes. Writing programs directly in bytes is slow, error-prone and tied to one processor family. Programming languages were invented to let humans think in terms of the problem, and compilers do the boring, exact work of converting that to machine code.
Here is one tiny C function seen at three levels.
int square(int x) {
return x * x;
}
GCC (gcc -O2 -S -masm=intel) produces this x86-64 assembly:
square:
imul edi, edi ; edi = edi * edi (x arrives in register edi)
mov eax, edi ; return value goes in eax
ret
And the assembler turns that into these machine-code bytes (shown by objdump -d):
0: 0f af ff imul edi,edi
3: 89 f8 mov eax,edi
5: c3 ret
Level | What it looks like | Who reads it |
|---|---|---|
High-level language |
| Humans |
Assembly language |
| Humans (with effort), assemblers |
Machine code |
| The CPU |
Notice what the compiler had to know: that the first integer argument arrives in register edi and the result must be left in eax (these rules come from the x86-64 System V calling convention), and which instruction multiplies integers. The programmer never has to think about any of this.
Benefits a compiler gives us
Productivity: one line of C can become many machine instructions.
Portability: the same C source can be compiled for x86, ARM or RISC-V by using a different compiler back end.
Error checking: type errors and syntax errors are caught before running.
Performance: optimizing compilers often produce faster code than an average human writing assembly.
A Compiler Is Also an Optimizer
Consider this program:
#include <stdio.h>
int main(void) {
int sum = 0;
for (int i = 1; i <= 10; i++)
sum = sum + i;
printf("sum = %d\n", sum);
return 0;
}
With optimization turned off (-O0), GCC translates the loop almost literally. The variables live in memory on the stack:
main:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR -8[rbp], 0 ; sum = 0
mov DWORD PTR -4[rbp], 1 ; i = 1
jmp .L2
.L3:
mov eax, DWORD PTR -4[rbp]
add DWORD PTR -8[rbp], eax ; sum = sum + i
add DWORD PTR -4[rbp], 1 ; i++
.L2:
cmp DWORD PTR -4[rbp], 10
jle .L3 ; loop while i <= 10
... ; then call printf
With optimization turned on (-O2), the loop disappears completely:
main:
sub rsp, 8
mov esi, 55 ; the answer, computed at compile time!
lea rdi, .LC0[rip] ; address of "sum = %d\n"
xor eax, eax
call printf@PLT
xor eax, eax
add rsp, 8
ret
The compiler worked out that the loop always produces 1 + 2 + ... + 10 = 55 and simply printed the constant. The program prints sum = 55 either way; only the amount of work at run time changed. This is what "equivalent program" means: same observable behaviour, possibly very different code. We study these transformations in Code Optimization Techniques.
What Makes a Good Compiler?
Property | Meaning |
|---|---|
Correctness | The target program must preserve the meaning of the source. This is non-negotiable; a fast but wrong compiler is useless. |
Good diagnostics | Clear error messages that point to the right line and suggest the real cause. |
Efficient target code | The generated program should run fast and use little memory (and, on phones, little energy). |
Reasonable compile time | Developers recompile constantly; a compiler that takes an hour per build slows everyone down. |
Portability and maintainability | Easy to add a new target machine or a new language feature. |
Error recovery | After an error, continue checking so that many errors are reported in one run, not just the first. |
Some of these goals conflict. Heavy optimization makes compilation slower, which is why compilers offer levels such as -O0 (fast compile, easy debugging) and -O2 / -O3 (slower compile, faster program).
The Big Picture: Analysis and Synthesis
Internally, every compiler does two broad jobs:
Analysis (front end): read the source, break it into pieces, check that it follows the rules of the language, and build an internal representation of its meaning. Errors in the source are found here.
Synthesis (back end): take that internal representation and produce the target program, improving it along the way.
source --> [ FRONT END ] --> intermediate --> [ BACK END ] --> target
analysis representation synthesis
(depends on (IR) (depends on the
the language) target machine)
The front end depends on the source language; the back end depends on the target machine. The intermediate representation (IR) in between is the contract that lets them be developed separately.
Why the split matters: m + n instead of m x n
Suppose we want to support 4 languages on 3 processors. Without a shared IR we would need 4 x 3 = 12 separate compilers. With a common IR we need only 4 front ends + 3 back ends = 7 components, and any front end can be paired with any back end.
C ---\ /--- x86-64
C++ ----\ /
Rust -----> common IR ---->---- ARM64
Swift----/ \
\--- RISC-V
This is exactly how GCC and LLVM are organised. Clang (C/C++), the Rust compiler and the Swift compiler all produce LLVM IR, and LLVM's back ends generate code for many processors. The detailed breakdown of the front end and back end into six phases is the topic of Phases of a Compiler.
Types of Compilers
Type | What it does | Example |
|---|---|---|
Native compiler | Runs on a machine and produces code for the same machine. | GCC on an x86-64 laptop producing x86-64 programs |
Cross compiler | Runs on one machine but produces code for a different machine. | Compiling Arduino (AVR) or Android (ARM) code on an x86 PC |
Single-pass compiler | Reads the source once and produces target code in that one pass. | Early Pascal compilers (Pascal was designed so this is possible) |
Multi-pass compiler | Processes the program (or its IR) several times, each pass doing part of the work. | GCC, LLVM, most optimizing compilers |
Source-to-source compiler (transpiler) | Translates one high-level language into another. | TypeScript to JavaScript; Babel (modern JS to older JS) |
Just-in-time (JIT) compiler | Compiles code to machine code while the program is running, usually only the parts that run often ("hot" code). | Java HotSpot JVM, JavaScript V8 engine, .NET runtime |
Ahead-of-time (AOT) compiler | Compiles everything before the program runs (the traditional model). | GCC, Clang, the Go and Rust compilers |
Bytecode compiler | Produces code for a virtual machine instead of a real CPU. |
|
Decompiler | Goes the other way: machine code or bytecode back to a high-level form. | Java decompilers, Ghidra's C decompiler |
Single-pass vs multi-pass
A pass is one complete reading of the program (or of its intermediate form) from start to end. A single-pass compiler is fast and uses little memory, but it cannot do optimizations that need to see the whole program, and the language must be designed so that everything is declared before it is used. A multi-pass compiler uses more memory and time, but each pass can be simpler and the later passes can use information gathered by earlier ones. Modern machines have plenty of memory, so nearly all production compilers are multi-pass.
Bootstrapping and T-Diagrams
Here is a puzzle: the GCC C compiler is itself written mostly in C and C++. So how was the first C compiler compiled? The answer is bootstrapping.
Bootstrapping is the technique of building a compiler for a language using a simpler compiler (often for a subset of the same language), and eventually having the compiler compile itself. A compiler that is written in the language it compiles is called self-hosting.
T-diagram notation
Every compiler involves three languages: the source language S it accepts, the target language T it produces, and the implementation language I it is written in. This is drawn as a "T":
+-----------------+
| S ---> T | a compiler from S to T,
+-----+ +-----+ written in language I
| I |
+-----+
In text we will write such a compiler as [S → T, in I]. For example, GCC on an x86-64 laptop is [C → x86-64, in x86-64]: it accepts C, produces x86-64 code, and is itself an x86-64 program.
A compiler can only be run on a machine if it is written in that machine's code. A compiler that exists only as C source code, [S → T, in C], is just a program waiting to be compiled.
The one rule for combining T-diagrams
If you take a compiler written in language I and feed it, as an ordinary input program, to another compiler that translates I to M, you get the same compiler (same source S, same target T), but now written in M:
program being compiled compiler we run result
+-----------------+ +-----------------+ +-----------------+
| S ---> T | | I ---> M | | S ---> T |
+-----+ +-----+ + +-----+ +-----+ = +-----+ +-----+
| I | | M | | M |
+-----+ +-----+ +-----+
[S -> T, in I] compiled by [I -> M, in M] gives [S -> T, in M]
Two checks: the implementation language of the input (I) must equal the source language of the compiler we run, and the result's implementation language is that compiler's target (M). Only the "foot" of the T changes.
Worked example 1: bootstrapping a new language
We invent language L and want a compiler for it on machine M.
Write a small compiler for a subset L0 of L directly in M's machine/assembly code: [L0 → M, in M]. It runs on M.
Write the full L compiler using only the features of L0: [L → M, in L0].
Compile the program from step 2 with the compiler from step 1: [L → M, in L0] compiled by [L0 → M, in M] gives [L → M, in M], a full L compiler running on M.
From now on the compiler can be written in full L and compiled by its own previous version. It has become self-hosting.
Worked example 2: a C compiler for a new machine (cross compilation)
Given: a working native C compiler on machine M, [C → M, in M]. We have written a C compiler for a new machine N in C: [C → N, in C]. Goal: a native C compiler that runs on N.
Step 1: [C -> N, in C] compiled by [C -> M, in M] gives [C -> N, in M]
runs on M but emits N code: a CROSS compiler
Step 2: [C -> N, in C] compiled by [C -> N, in M] gives [C -> N, in N]
runs on N and emits N code: a NATIVE compiler for N
In step 1 the C source of the new compiler is translated into M code, so the result runs on M. In step 2 we compile the same source again, this time with the cross compiler, so the result is N code. Copy it to machine N and it can compile C programs there by itself. This two-step trick is how compilers are brought up on new processors.
A Short History
Year | Milestone |
|---|---|
1952 | Grace Hopper's A-0 system for the UNIVAC I, often called the first compiler (it assembled pre-written subroutines into a program) |
1957 | IBM's FORTRAN compiler, led by John Backus: the first widely used high-level language compiler, and already an optimizing one |
1960 | The ALGOL 60 report describes syntax with BNF (Backus-Naur Form), the notation behind context-free grammars in compilers |
1965 | Donald Knuth introduces LR parsing |
1970s | Lex and Yacc at Bell Labs make scanner and parser generation routine |
1987 | First release of GCC by Richard Stallman |
2003 | First release of LLVM (started by Chris Lattner in 2000); Clang later builds on it |
1990s to today | JIT compilers (Java HotSpot, JavaScript V8) make "interpreted" languages fast |
Where Compiler Techniques Are Used
Even if you never write a full compiler, the ideas in this subject show up everywhere:
Editors and IDEs: syntax highlighting uses a lexer; auto-complete and "go to definition" use a parser and a symbol table.
Linters and formatters: ESLint, Pylint, Prettier and clang-format parse code into trees.
Databases: an SQL query is lexed, parsed, checked, optimized and turned into an execution plan, which is a compiler pipeline.
Data formats: JSON, XML and configuration file readers are parsers.
Web browsers: HTML, CSS and JavaScript are all parsed; JavaScript is JIT-compiled.
Machine learning: frameworks compile model graphs into fast GPU code (for example XLA and TVM).
Regular-expression engines: regex patterns are compiled into automata, the same theory used by lexical analysers.
Common Mistakes Students Make
"A compiler runs the program." No. A compiler only translates. Running is done later by the CPU (or by a virtual machine).
"A compiler always produces machine code." The target can be assembly, bytecode or another high-level language (a transpiler).
"Optimization changes the output of the program." A correct optimization never changes observable behaviour of a valid program; it only changes speed or size.
Confusing phases with passes. A phase is a logical step (like syntax analysis); a pass is one reading of the program. Several phases can be done in one pass. See Phases of a Compiler.
Getting T-diagram composition backwards. When you compile a compiler, its source and target languages stay the same; only its implementation language changes.
GATE / Interview Questions
1. Define a compiler. What are its two main tasks?
A compiler translates a program in a source language into an equivalent program in a target language. Its two tasks are translation (producing equivalent target code) and error detection/reporting in the source program.
2. What is a cross compiler? Give an example.
A compiler that runs on one machine (the host) but generates code for another machine (the target). Example: avr-gcc running on an x86 PC and producing code for an Arduino's AVR microcontroller.
3. Why are compilers divided into a front end and a back end?
The front end depends only on the source language, the back end only on the target machine, and they meet at an intermediate representation. Supporting m languages on n machines then needs m + n components instead of m x n complete compilers, and optimizations on the IR are shared by all.
4. We have a compiler for language L written in L that generates code for machine N, and a working L compiler running on machine M that generates M code. How do we get a native L compiler for N?
First compile [L → N, in L] with [L → M, in M] to get [L → N, in M], a cross compiler that runs on M and produces N code. Then compile the same source [L → N, in L] again with this cross compiler to get [L → N, in N], which runs on N and produces N code.
5. What is bootstrapping?
Building a compiler using a simpler or older compiler (often for a subset of the same language) and then using the compiler to compile itself. The result is a self-hosting compiler, i.e. one written in the language it compiles.
6. Is a JIT compiler a compiler or an interpreter?
It is a compiler that runs at run time. Systems like the Java HotSpot JVM start by interpreting bytecode, measure which methods are hot, and then JIT-compile those to native machine code. So the overall system mixes interpretation and compilation.
7. What is the difference between single-pass and multi-pass compilers?
A single-pass compiler reads the source once and emits code directly: fast and memory-light but limited in optimization and requires declare-before-use. A multi-pass compiler processes the program or its IR several times: slower and needs more memory, but allows better analysis, optimization and a cleaner modular design.
8. Why might gcc -O2 make a loop disappear?
If the compiler can compute the loop's result at compile time (as with summing the constants 1 to 10) and the loop has no other observable effect, it replaces the loop with the final value. The program's output does not change, so the transformation is legal.
Summary
A compiler translates a source program into an equivalent target program and reports errors in the source.
The CPU only runs machine code; compilers give us productivity, portability, error checking and performance.
A compiler is also an optimizer:
-O2turned a loop summing 1..10 into the constant 55.Internally, the front end (analysis) depends on the language and the back end (synthesis) on the machine; they meet at an intermediate representation, turning m x n compilers into m + n components.
Kinds of compilers: native, cross, single-pass, multi-pass, source-to-source, JIT, AOT, bytecode, and decompilers.
Bootstrapping builds compilers with simpler compilers; T-diagrams track source, target and implementation languages, and compiling a compiler changes only its implementation language.
Next, in Language Processors: Interpreter, Assembler, Linker & Loader, we look at the other programs that work alongside the compiler to turn source code into a running process.