Building a Compiler from Scratch

Why Build a Compiler?

Every time you write code, a compiler transforms your human-readable instructions into machine code that processors can execute. Understanding this process demystifies the magic of programming and makes you a significantly better developer.

Building a compiler teaches you about language design, parsing algorithms, data structures, optimization techniques, and how computers actually execute code. These skills transfer to virtually every area of software engineering.

Compiler Architecture Overview

A modern compiler consists of several distinct phases, each with a specific responsibility:

Source Code
    ↓
[Lexer/Tokenizer] → Token Stream
    ↓
[Parser] → Abstract Syntax Tree (AST)
    ↓
[Semantic Analyzer] → Annotated AST
    ↓
[Optimizer] → Optimized IR
    ↓
[Code Generator] → Target Code

Lexical Analysis (Tokenization)

The first phase of compilation is lexical analysis (or tokenization). The lexer breaks the raw source code into a stream of tokens—the fundamental units of the language.

// Example: Tokenizing "let x = 42;"
enum TokenType {
  LET, IDENTIFIER, EQUALS, NUMBER, SEMICOLON, EOF
}

interface Token {
  type: TokenType;
  value: string;
  line: number;
  column: number;
}

// Input: "let x = 42;"
// Output: [
//   { type: LET, value: "let", line: 1, column: 1 },
//   { type: IDENTIFIER, value: "x", line: 1, column: 5 },
//   { type: EQUALS, value: "=", line: 1, column: 7 },
//   { type: NUMBER, value: "42", line: 1, column: 9 },
//   { type: SEMICOLON, value: ";", line: 1, column: 11 }
// ]

Parsing and AST Construction

The parser takes the token stream and builds an Abstract Syntax Tree (AST)—a hierarchical representation of the program structure that captures the grammatical relationships between tokens.

// AST Node types
type ASTNode =
  | { type: 'Program'; body: Statement[] }
  | { type: 'VariableDeclaration'; name: string; init: Expression }
  | { type: 'NumberLiteral'; value: number }
  | { type: 'BinaryExpression'; op: string; left: Expression; right: Expression };

// "let x = 42;" becomes:
{
  type: 'Program',
  body: [{
    type: 'VariableDeclaration',
    name: 'x',
    init: { type: 'NumberLiteral', value: 42 }
  }]
}

Semantic Analysis

Once we have an AST, semantic analysis verifies that the program makes sense: types match, variables are declared before use, and function calls have the correct arguments.

Code Generation

Finally, code generation transforms the validated AST into target code—whether that's machine code, bytecode, or another high-level language (transpilation).

; Generated from: let x = 40 + 2;
section .data
    x: dq 0

section .text
    mov rax, 40      ; Load 40
    add rax, 2       ; Add 2
    mov [x], rax     ; Store in x