How a Compiler Works: From Source Code to Machine Code

Take this small function:

int square(int x) {
    return x * x;
}

To a programmer, its meaning is immediately obvious: accept an integer, multiply it by itself, and return the result.

The processor sees something very different.

An x86-64 CPU does not understand functions, variable names, types, expressions, or C++ syntax. It executes encoded machine instructions that manipulate registers, memory, and control flow.

A compiler is responsible for crossing that gap.

The same function might eventually become assembly similar to:

square:
    mov eax, edi
    imul eax, edi
    ret

Those assembly instructions can then be encoded into the machine instructions executed by the processor.

But a compiler does not normally jump directly from:

return x * x;

to:

imul eax, edi

A modern compiler progressively transforms the program through several internal representations. Each stage answers a different question about the source code.

In this chapter, we will follow that transformation from the first character of a source file to instructions that can run on an x86-64 processor.

What You Will Learn

By the end of this chapter, you will be able to:

• Explain what a compiler actually does.
• Describe how source text becomes tokens.
• Understand why compilers build an Abstract Syntax Tree.
• Explain what semantic analysis checks.
• Understand the purpose of Intermediate Representation.
• See how IR can be lowered into x86-64 assembly.
• Distinguish assembly language from machine code.
• Explain the roles of the compiler front end, middle end, and back end.
• Compare ahead-of-time compilation, interpretation, and JIT compilation.

What Is a Compiler?

A compiler transforms a program from one representation into another.

The input is usually called the source language.

The output is the target representation.

For example:

C++ source
    ↓
Compiler
    ↓
x86-64 machine code

But machine code is not the only possible target.

A compiler might instead produce:

• Assembly language.
• Object code.
• Bytecode.
• WebAssembly.
• Another programming language.
• An Intermediate Representation used by another compiler stage.

This means a compiler is better understood as a program transformation system than simply a tool that converts text into machine code.

One requirement remains fundamental:

A correct compiler must preserve the behaviour of a valid source program.

Optimisation may change how the program is implemented, sometimes dramatically, but it must not arbitrarily change what the program means.

Following a Function Through the Compiler

Consider a function written in a small C-like language:

fn square(x: int): int {
    return x * x;
}

We can use this function to examine the major transformations performed by a compiler.

At the beginning, the compiler has nothing more than a sequence of characters:

f n   s q u a r e ( x :   i n t ) :   i n t ...

Characters alone do not tell the compiler very much.

It must first identify which characters belong together.

Stage 1: Lexical Analysis

The first stage is lexical analysis, usually performed by a component called the lexer or scanner.

The lexer reads the source text and groups characters into meaningful units called tokens.

Our function:

fn square(x: int): int {
    return x * x;
}

might produce tokens conceptually similar to:

FN
IDENTIFIER("square")
LEFT_PAREN
IDENTIFIER("x")
COLON
INT
RIGHT_PAREN
COLON
INT
LEFT_BRACE
RETURN
IDENTIFIER("x")
STAR
IDENTIFIER("x")
SEMICOLON
RIGHT_BRACE
END_OF_FILE

The lexer does not yet understand that square is a function or that x * x is a multiplication expression.

Its job is more basic.

It answers questions such as:

• Is return a keyword?
• Is square an identifier?
• Is 123 an integer literal?
• Is * an operator?
• Where does one token end and another begin?

For example, the characters:

return

should become one keyword token, not six independent character tokens.

Similarly:

12345

should normally become one integer token rather than five individual digits.

The output of the lexer becomes the input to the parser.

Source characters
        ↓
      Lexer
        ↓
      Tokens

Stage 2: Parsing

A token stream tells us what pieces exist, but not how those pieces fit together.

That is the parser’s job.

The parser checks whether the tokens follow the grammar of the language and turns them into a structural representation of the program.

Consider:

return x * x;

The lexer sees something approximately like:

RETURN IDENTIFIER STAR IDENTIFIER SEMICOLON

The parser recognises a much richer structure:

ReturnStatement
└── MultiplicationExpression
    ├── Identifier: x
    └── Identifier: x

That distinction matters.

These tokens:

x + y * z

cannot simply be interpreted from left to right if the language defines multiplication as having higher precedence than addition.

The parser must understand the expression as:

x + (y * z)

rather than:

(x + y) * z

The grammar of the language determines how these structures are formed.

Stage 3: Building the Abstract Syntax Tree

Compilers commonly represent the parsed program using an Abstract Syntax Tree, usually abbreviated to AST.

For our complete function, a simplified AST might look like:

FunctionDeclaration
├── name: square
├── parameters
│   └── Parameter
│       ├── name: x
│       └── type: int
├── returnType: int
└── body
    └── ReturnStatement
        └── BinaryExpression (*)
            ├── Identifier(x)
            └── Identifier(x)

Notice that details such as parentheses, colons, braces, and semicolons are no longer represented directly.

They were important while parsing the source code, but many of them are unnecessary once the compiler understands the structure of the program.

That is why the tree is called abstract.

It preserves the important meaning and structure while discarding much of the original textual syntax.

The compiler has now moved from:

characters

to:

tokens

to:

program structure

But there is still a problem.

A syntactically valid program is not necessarily a meaningful one.

Stage 4: Semantic Analysis

Consider this program:

fn square(x: int): int {
    return missing * x;
}

There is nothing obviously wrong with its grammar.

The parser can construct an AST for it.

But missing has never been declared.

Now consider:

fn square(x: int): int {
    return x * "hello";
}

Again, the syntax could be completely valid.

The problem is semantic: multiplying an integer by a string may not be permitted by the language.

These are the kinds of problems handled during semantic analysis.

Semantic analysis asks questions such as:

• Has this variable been declared?
• Is this identifier visible in the current scope?
• Does this function exist?
• Are the correct number of arguments supplied?
• Are the argument types valid?
• Can these two values be used with this operator?
• Does the returned value match the declared return type?
• Has a name been declared twice where that is illegal?

For the valid square function:

fn square(x: int): int {
    return x * x;
}

the analyser can determine that:

x → parameter of square
type(x) → int
type(x * x) → int
return type of square → int

Everything is consistent.

Only after this stage does the compiler have confidence that the program is structurally and semantically valid.

Stage 5: Intermediate Representation

The AST closely reflects the source language.

That makes it convenient for parsing and semantic analysis, but less convenient for optimisation and machine-code generation.

Compilers therefore often lower the program into an Intermediate Representation, or IR.

A simple IR for:

return x * x;

might look like:

t0 = multiply x, x
return t0

Here, t0 represents a temporary value.

The original syntax:

x * x

has been transformed into a lower-level operation:

multiply x, x

The compiler no longer needs to care whether the source language originally expressed multiplication using *, a function call, or some other syntax.

That is one of the main strengths of IR.

It creates a boundary between understanding the source language and generating code for a particular machine.

Conceptually:

Source language
      ↓
    Front end
      ↓
      IR
      ↓
    Back end
      ↓
Target architecture

A compiler that supports multiple languages and architectures can potentially reuse substantial parts of its optimisation pipeline.

This idea is central to compiler infrastructures such as LLVM.

Stage 6: Optimisation

Once the program exists in an IR designed for transformation, the compiler can attempt to improve it.

Consider:

let x: int = 10 * 20;

A straightforward IR might initially contain:

t0 = multiply 10, 20
x = t0

But the multiplication can be performed during compilation.

An optimisation pass could transform it into:

x = 200

This technique is known as constant folding.

Other optimisations can:

• Remove computations whose results are never used.
• Eliminate unreachable code.
• Simplify expressions.
• Propagate known constant values.
• Remove redundant loads or stores.
• Simplify branches.
• Inline selected function calls.
• Improve loops.
• Reduce unnecessary instructions.

Optimisation is not simply about making a program “faster.”

A compiler might optimise for:

• Execution speed.
• Executable size.
• Memory use.
• Power consumption.
• Compilation speed.
• Debuggability.

Most importantly, an optimisation must preserve the observable behaviour allowed by the language.

Stage 7: Instruction Selection

Eventually the compiler must leave its architecture-independent representations behind.

Our target is x86-64.

Suppose our IR contains:

t0 = multiply x, x
return t0

The backend must determine which x86-64 instructions can perform those operations.

Under a calling convention where the integer argument x arrives in edi, one possible result is:

square:
    mov eax, edi
    imul eax, edi
    ret

Breaking that down:

mov eax, edi

copies the function argument into eax.

Then:

imul eax, edi

multiplies the value by itself.

Finally:

ret

returns control to the caller.

The return value is left in eax, as required by the calling convention for this type of integer result.

At this point, the compiler is dealing with the actual rules of the target processor and platform.

Stage 8: Register Allocation

Real programs contain far more values than the processor has convenient registers available for at the same time.

Consider an expression containing many intermediate values:

a + b * c - d * e

The compiler may conceptually generate several temporary values:

t0 = multiply b, c
t1 = add a, t0
t2 = multiply d, e
t3 = subtract t1, t2

Those temporary names do not correspond to an unlimited collection of real CPU registers.

The backend must decide where the values should live.

That process is called register allocation.

A value might be placed:

• In a general-purpose register.
• On the stack.
• In memory.
• In a register temporarily before being moved elsewhere.

When there are not enough registers available, some values may need to be spilled to memory.

Register allocation is one of the points where an abstract program becomes constrained by the physical architecture of the machine.

Stage 9: Assembly

After instruction selection, register allocation, and other backend work, the compiler can emit assembly.

Assembly is a textual notation for machine instructions.

For example:

mov eax, edi
imul eax, edi
ret

is readable by a programmer familiar with x86-64 assembly.

The processor itself does not execute the letters:

m o v

or:

i m u l

Those mnemonics exist for humans.

An assembler converts the assembly into machine-code bytes.

In this series, we use NASM for that job.

Conceptually:

x86-64 assembly
       ↓
      NASM
       ↓
    Object code

Stage 10: Machine Code

The final CPU instructions are encoded as binary data.

For example, an x86-64 instruction that appears in assembly as:

ret

has a corresponding machine-code encoding.

The processor fetches encoded instructions from memory, decodes them, and executes the operations they represent.

Machine code therefore sits at the end of our compiler journey:

Si source
    ↓
Tokens
    ↓
AST
    ↓
Semantic analysis
    ↓
IR
    ↓
Optimised IR
    ↓
x86-64 instructions
    ↓
NASM assembly
    ↓
Machine code

But producing instructions alone is usually not enough to create a usable executable.

From Object File to Executable

An assembler normally produces an object file, not the complete application.

An object file may contain:

• Machine code.
• Data.
• Symbol information.
• Relocation information.
• References to code defined elsewhere.

A linker combines the required object files and resolves references between them.

In our compiler project, generated code will eventually need to interact with a small runtime containing functions such as:

print(value)

That means the final build process will look roughly like:

Si source
    ↓
Our compiler
    ↓
x86-64 assembly
    ↓
NASM
    ↓
Program object file
    +
Runtime object file
    ↓
Linker
    ↓
Linux executable

The linker is therefore an important part of getting from generated assembly to something the operating system can actually load and execute.

The Front End, Middle End, and Back End

The individual stages we have examined are often grouped into three larger parts.

The Front End

The front end understands the source language.

It generally contains stages such as:

Source code
    ↓
Lexing
    ↓
Parsing
    ↓
AST
    ↓
Semantic analysis

Its job is to answer:

What program did the programmer write, and is it valid?

The front end is heavily influenced by the design of the source language.

A compiler for C++, for example, requires very different language rules from a compiler for Si.

The Middle End

The middle end works primarily with Intermediate Representations.

It is much less concerned with how the original program was written.

Instead, it analyses and transforms the program.

Typical work includes:

• Constant folding.
• Dead-code elimination.
• Control-flow analysis.
• Data-flow analysis.
• Simplification.
• Other optimisation passes.

Its central question is:

Can we represent this program in a better form without changing its required behaviour?

Because IR can abstract away much of the source language, optimisation infrastructure can often be reused.

The Back End

The back end targets a particular machine architecture.

For us, that architecture is x86-64.

It handles tasks such as:

• Instruction selection.
• Register allocation.
• Stack-frame construction.
• Calling conventions.
• Branch generation.
• Function calls.
• Assembly emission.

Its question is:

How do we express this program using the instructions and resources available on this machine?

These three sections form a useful mental model:

          FRONT END
Source → Tokens → AST → Semantic Analysis
                         ↓
                     MIDDLE END
                         IR
                         ↓
                   Optimisation
                         ↓
                      BACK END
                  x86-64 lowering
                         ↓
                      Assembly

Real production compilers can contain many more stages and representations, but this model gives us a useful foundation.

Why Use an Intermediate Representation?

Without IR, a compiler supporting several source languages and several target architectures could quickly become difficult to maintain.

Imagine supporting:

C
C++
Rust
Si

and targeting:

x86-64
ARM64
RISC-V

If every language frontend generated every target independently, we could end up needing transformations conceptually similar to:

C      → x86-64
C      → ARM64
C      → RISC-V

C++    → x86-64
C++    → ARM64
C++    → RISC-V

Rust   → x86-64
Rust   → ARM64
Rust   → RISC-V

An intermediate representation gives us a cleaner architecture:

C ──────┐
C++ ────┼──→ IR ───→ x86-64
Rust ───┤      ├───→ ARM64
Si ─────┘      └───→ RISC-V

The real implementation is more complicated, but the architectural benefit is important.

Front ends can focus on languages.

Back ends can focus on processors.

Optimisation can operate between them.

Compilation Is Not Always Straight to Native Code

Not every language follows the exact pipeline we are building.

Different language implementations make different choices about when and how code is translated.

Ahead-of-Time Compilation

An ahead-of-time, or AOT, compiler performs compilation before the resulting program is executed.

Languages such as C, C++, and Rust commonly use this approach for native applications.

A simplified workflow looks like:

Source
   ↓
Compiler
   ↓
Native executable
   ↓
Run

Our Si compiler follows this model.

We compile the source first and produce a native x86-64 executable that can be launched afterwards.

Interpretation

An interpreter executes a program through another runtime rather than necessarily producing a native executable beforehand.

The exact implementation varies.

An interpreter might:

• Walk an AST directly.
• Execute an internal instruction format.
• Execute bytecode in a virtual machine.
• Combine interpretation with compilation.

For example, CPython compiles Python source into bytecode and executes that bytecode using the Python virtual machine.

So the common explanation that an interpreter simply “reads and executes source code line by line” is often too simplistic.

Just-in-Time Compilation

A Just-in-Time compiler, or JIT, generates machine code while a program is running.

A runtime can initially execute code in one form while collecting information about its behaviour.

Frequently executed sections can then be compiled into optimised machine code.

A simplified model is:

Program
   ↓
Runtime
   ↓
Execution + profiling
   ↓
JIT compiler
   ↓
Optimised machine code

Modern JavaScript engines and managed runtimes can combine:

• Interpretation.
• Bytecode.
• Profiling.
• JIT compilation.
• Multiple optimisation levels.

Compilation and interpretation are therefore not mutually exclusive categories.

They are techniques that can be combined inside the same runtime.

Why Compiler Construction Teaches Computer Architecture

Compiler development forces high-level programming concepts to meet the limitations of real hardware.

When we eventually generate x86-64 code, decisions that previously seemed abstract become concrete.

A local variable must exist somewhere.

A function argument must be passed somewhere.

A return value must follow a calling convention.

A branch must eventually become a jump instruction.

A function call affects registers and the stack.

A complex expression must be broken into operations the processor actually provides.

Concepts such as:

• Registers.
• Memory.
• Stack frames.
• Calling conventions.
• Instruction selection.
• Branches.
• Alignment.
• Object files.
• Linking.

stop being isolated computer-architecture topics.

They become problems our own compiler has to solve.

The Black Box Is a Pipeline

When you write:

fn square(x: int): int {
    return x * x;
}

and eventually execute a native binary, a large number of transformations have taken place.

The important idea from this chapter is that compilation is not one enormous translation step.

It is a sequence of smaller transformations:

Source text
    ↓
Lexical structure
    ↓
Syntactic structure
    ↓
Semantic meaning
    ↓
Intermediate operations
    ↓
Optimised operations
    ↓
Target instructions
    ↓
Encoded machine code

Each representation makes a different problem easier to solve.

The lexer does not need to know how registers work.

The parser does not need to know machine instruction encodings.

The optimiser does not need to care whether a multiplication originally used the * character.

The x86-64 backend does not need to parse source text.

That separation is what turns the apparent compiler “black box” into a system we can actually understand and build.

Chapter Summary

In this chapter, we followed a program through the major conceptual stages of compilation.

We saw that:

• A compiler transforms programs between representations while preserving their required behaviour.
• Lexical analysis converts characters into tokens.
• Parsing discovers grammatical structure.
• An Abstract Syntax Tree represents the meaningful structure of the source program.
• Semantic analysis checks names, scopes, types, and other language rules.
• Intermediate Representation separates language-specific analysis from later transformations.
• Optimisation improves the program’s representation without changing its required behaviour.
• The backend selects target instructions and manages machine resources such as registers and the stack.
• Assembly is a human-readable representation of machine instructions.
• An assembler turns assembly into object code.
• A linker combines object files into an executable.
• AOT compilation, interpretation, and JIT compilation are different implementation strategies that can also be combined.

We began with:

fn square(x: int): int {
    return x * x;
}

and ended with the instructions needed to execute that idea on a real processor.

The black box is already beginning to open.

Next Chapter

In Chapter 2, we will stop looking at compilers from the outside and begin designing our own.

We will define the syntax and type system of Si, write the first version of its grammar, decide which language features our compiler will support, and create the C++ development environment that the rest of the project will use.