A Practical Compiler Design Guide: Overview

Building a programming language can feel daunting, especially given how dense the academic literature around it can be.

The purpose of this series is to teach compiler design from a practical angle and get you using your own language to build things.

I'll go over the fundamentals, but by the end you'll have something small, extensible, and easy to reshape around whatever you want to build.

We'll design the language in stages. Think of each stage as a process that makes something about its input more explicit.

source text -> tokens -> AST -> IR -> bytecode -> runtime behavior

This overview explains what those stages are, why they exist, and how they fit together.

The rest of this guide takes each stage separately and shows how to implement it.

The design is based on elf, my embedded scripting language.

It uses a hand-written compiler, an explicit abstract syntax tree and intermediate representation, slot-based bytecode, and a virtual machine, all written from scratch in C.

The examples use C, but you should be able to follow along using any other programming language.

What Building a Language Actually Means

I think of a programming language as an interface for expressing computation.

You write what you want the computer to do, and the implementation turns that description into behavior.

A language defines two things:

Syntax: what programs look like.
Semantics: what those programs do when they run.

Everything else—the lexer, parser, intermediate representation, bytecode, and runtime—exists to preserve those decisions all the way from text to execution.

So we'll design the language, the compiler, and the runtime that executes the result.

language implementation
|
|-- language definition
|   |-- syntax
|   `-- semantics
|
|-- compiler
|   |-- lexer: source characters -> tokens
|   |-- parser: tokens -> abstract syntax tree
|   |-- lowerer: AST -> intermediate representation
|   `-- bytecode generator: IR -> executable module
|
|-- runtime
|   |-- virtual machine
|   |-- value and object system
|   |-- functions, frames, and closures
|   `-- memory management
|
`-- host boundary
    |-- exposes native functions and data
    `-- lets an application compile and execute scripts

Not every language needs exactly these components. There are many kinds of implementations, and part of the fun is figuring out what yours actually needs.

A tree-walk interpreter may execute the AST directly. A tiny compiler may generate bytecode without a separate IR. A native compiler may continue lowering until it reaches machine code for a real processor.

The important idea is not the precise number of stages. Every stage should make the program easier to understand than it was before. If a stage only adds ceremony and does not simplify the next step, you probably do not need it.

Imagine Your Language

Before building anything, write a tiny program in the language you would actually like to use.

For me, I wanted something boringly simple, almost mundane.

make_multiplier := fun(factor) {
    ret fun(value) {
        ret value * factor
    }
}

double := make_multiplier(2)
answer := double(21)

if answer == 42 ? {
    print(answer)
}

Even this small example requires identifiers, literals, declarations, arithmetic, functions, lexical scope, a closure, conditional control flow, and a native print function.

That is already enough to give the compiler pipeline a real job. Now let's look at what each stage contributes.

Lexing: From Characters to Tokens

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

Given:

answer := left + 22

the lexer might produce:

IDENTIFIER("answer")
DECLARE
IDENTIFIER("left")
PLUS
INTEGER(22)
END_OF_FILE

The parser does not care about the individual letters in answer. It cares that answer is an identifier. The lexer removes that character-level detail so every later stage can work with useful categories instead.

A token usually carries its kind, its source text or decoded value, and enough location information to produce diagnostics. The lexer should remain deliberately simple: recognize one token, advance through the source, and report malformed text.

The focused article, Building a Lexer From Scratch, implements this stage in detail.

Parsing: From Tokens to Structure

Tokens tell us which pieces exist, but not how those pieces relate.

Consider:

left + right * 10

Because multiplication binds more tightly than addition, the parser should recover this structure:

Add
|- Identifier(left)
`- Multiply
   |- Identifier(right)
   `- Integer(10)

That structure becomes the abstract syntax tree, or AST. A node may represent a literal, identifier, declaration, function, call, block, loop, or expression. Parent nodes own the relationships between their children.

The tree is abstract because it does not need to preserve every comma, parenthesis, or piece of whitespace. It preserves the structure required for meaning, diagnostics, and later tooling.

Parsing and language design are closely connected. When a token stream permits more than one interpretation, the parser cannot solve the problem through guesswork. The grammar needs a rule. This is the stage where the language begins to acquire its actual shape.

The focused article, Building a Parser From Scratch, implements this stage with a hand-written recursive-descent parser, precedence climbing, an arena-backed AST, and shape-based parser tests.

Lowering: From Syntax to Operations

The AST resembles the way the programmer wrote the code. That makes it useful for understanding syntax, but not necessarily convenient for generating instructions.

Lowering transforms the AST into an intermediate representation, or IR. The IR removes distinctions that matter to the language's surface syntax but do not need to exist in the bytecode.

A while loop, for example, might appear in the AST as one structured node:

While
|- Condition
`- Body

The IR can express the same behavior through simpler control-flow operations:

loop_start:
    jump_if_false condition, loop_end
    body
    jump loop_start
loop_end:

Several different source constructs can lower to the same labels and jumps. The bytecode generator no longer needs to understand every kind of loop the language happens to offer.

Lowering is also a natural home for name resolution, lexical scopes, closure captures, assignment validation, and other work that requires more context than the parser should carry.

An IR is not mandatory. It earns its place when it makes both the AST and the backend simpler. That boundary became valuable in elf once generating code during parsing made new syntax increasingly difficult to reason about.

Bytecode Generation: From IR to a Module

The bytecode generator walks the IR and emits executable instructions. Constants become loads, arithmetic becomes operations, local references become slot indices, and control flow becomes jumps.

The result is normally more than one instruction array. A useful bytecode module may contain:

instruction streams;
pools for string and numeric constants;
metadata for every function;
the frame size required by each function;
closure and capture information; and
source mappings for diagnostics and debugging.

In a slot-based design, instructions name their inputs and outputs explicitly:

ADD destination, left, right

A stack-based design would instead push the operands before executing ADD. Neither model is universally correct. They expose different tradeoffs in instruction size, code generation, and runtime behavior.

The first generator should be obvious rather than clever. Produce unoptimized instructions, build a disassembler, and make the output readable before trying to make it small or fast.

Runtime: From Instructions to Behavior

The virtual machine repeatedly reads an instruction and performs the operation it describes:

while running:
    instruction = code[instruction_pointer]
    instruction_pointer += 1

    switch instruction.opcode:
        case LOAD_CONSTANT:
            slots[x] = constants[y]

        case ADD:
            slots[x] = add(slots[y], slots[z])

        case JUMP:
            instruction_pointer += instruction.offset

        case RETURN:
            leave_current_frame()

That dispatch loop is the center of the runtime, but it is not the entire runtime. The VM also needs to represent values, create call frames, preserve captured variables, report errors, and eventually release objects that are no longer reachable.

Dynamic typing moves some decisions into this stage. An ADD instruction may receive integers, floating-point values, strings, or an invalid combination. The runtime tags carried by those values determine what the instruction does.

Static analysis can settle more questions during compilation. Dynamic behavior leaves more questions for execution. The complexity does not disappear; the language design determines where it lives.

Embedding, Ownership, and Memory

This section is more about the design of the library itself, if you are interested in making your language embeddable.

An embedded language also needs a boundary between scripts and the host application. The host should be able to:

create and destroy a language state;
compile or load source;
expose native functions and data;
call script functions;
inspect returned values; and
retrieve useful diagnostics.

The API needs explicit ownership rules. If the host receives a string, how long is it valid? If it keeps a script object, what prevents that object from being collected? If compilation fails, who owns the error message?

Compiler data and runtime data often need different allocation strategies. Tokens, AST nodes, and IR nodes can live in temporary arenas discarded after compilation. Finalized modules must remain alive while their functions can run. Strings, tables, and closures need lifetimes determined by the running program.

Dividing objects by lifetime before choosing an allocation mechanism keeps memory management understandable. One universal allocator is not automatically simpler.

Roadmap

Build the lexer.
Parse the token stream and represent the AST.
Resolve names and lower the AST into IR.
Generate a bytecode module.
Execute that module in a virtual machine.
Add functions, closures, native calls, and memory management.

The Short Version

A language is a way of expressing computation.

Syntax is what the program looks like; semantics is what it does.
Each compiler stage should make one part of the program more explicit.
You don't need every stage, but separating them makes experimentation easier.
Keep every representation printable so you can see where something went wrong.
Build one tiny program through the complete pipeline before adding lots of features.
Start boring. Novel syntax can come later.

Additional Sources

elf source and documentation