Build a Rust Subset Compiler

Compile Rust expressions to native x86_64 ELF binaries from scratch.

Introduction

30 Second Summary

Every program on your computer is ultimately a file full of raw numbers that your CPU reads and executes. Compilers are the tools that transform human-readable source code into those numbers.

In this project, you will build a compiler called "rustlet" that takes a tiny subset of Rust source code and produces a native Linux executable from scratch. No assembler, no linker, no LLVM.

What You'll Build

You type an arithmetic expression inside fn main(), run your compiler, and get a real native binary you can execute immediately and show the computed result.

By the end of this project, you'll have:

  • A working compiler that reads fn main() -> i64 { (2 + 3) * 4 - 1 } and produces a native x86_64 binary that computes 19 when you run it.
  • A zero-copy lexer and bump-allocated AST that processes source code without per-token or per-node heap allocations.
  • An extensible architecture with an IR layer and a Backend trait, so adding a new CPU target (ARM64, RISC-V) requires implementing a single trait.
  • Secret Mission: Extend the compiler with unary negation and the modulo operator, touching every stage of the pipeline.

Are there any prerequisites?

This project assumes Rust proficiency (ownership, lifetimes, traits, unsafe), a basic understanding of assembly and machine code, and comfort with the Linux command line.

You do not need prior compiler experience. The project teaches lexing, parsing, and code generation from first principles.

Before We Start

Before We Start...

Before we dive in, let's lock in what you're about to build and why it matters.

Set Up the Project

Every compiler needs a foundation before it can process a single byte of source code.

In this step, you will create the Rust project, add bumpalo as the sole dependency for arena allocation, and establish the module structure that mirrors the compiler pipeline: lexer, parser, codegen, and ELF writer.

In this step, get ready to:
  • Create the rustlet Cargo project with edition 2024.
  • Add the bumpalo arena allocator as the sole dependency.
  • Create empty module files for each compiler stage.
Create the project and configure dependencies

Rust projects are managed by Cargo, which handles dependencies, compilation, and project layout.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create the rustlet project and move into it by running these commands:
cargo new rustlet
cd rustlet

You should see Creating binary (application) `rustlet` package in the terminal output.

What did cargo new create?

This command scaffolded a Cargo.toml manifest and a src/main.rs file with a Hello World program.

By default, cargo new uses edition 2021. You will change this to edition 2024 next.

  • Open the project in Zed by running:
zed .
  • In the Zed sidebar, click on Cargo.toml to open it.
  • Replace the entire contents of Cargo.toml with the following:
[package]
name = "rustlet"
version = "0.1.0"
edition = "2024"

[dependencies]
bumpalo = "3.20"

What does this configure?

  • edition = "2024" opts into the Rust 2024 edition, which was stabilized in Rust 1.85.0.
  • bumpalo = "3.20" adds the bumpalo arena allocator. Your entire AST will live in a single bump-allocated arena with zero per-node heap allocations.
  • Save Cargo.toml.

✔️ Awesome, I've got everything!

Great. Make sure you have saved the file before moving on.

ⓧ I'd like to double check the full code

[package]
name = "rustlet"
version = "0.1.0"
edition = "2024"

[dependencies]
bumpalo = "3.20"
Create the module files and entry point

The compiler pipeline has four stages, each in its own module: lexer, parser, codegen, and ELF writer.

  • Create the four empty module files by running this command in your terminal:
touch src/lexer.rs src/parser.rs src/codegen.rs src/elf.rs
  • Confirm the files exist by running:
ls src/

You should see codegen.rs, elf.rs, lexer.rs, main.rs, and parser.rs listed.

  • In Zed, open src/main.rs from the sidebar.
  • Replace the entire contents with the following:
mod lexer;
mod parser;
mod codegen;
mod elf;

fn main() {
    println!("rustlet compiler");
}

What does this code do?

  • The four mod statements tell Rust to include each module file as part of this crate. Even though the files are empty, the compiler needs the declarations to know they exist.
  • The main() function is a placeholder that proves the project compiles and runs.
  • Save src/main.rs.

✔️ Awesome, I've got everything!

Great. Double check you have saved the file.

ⓧ I'd like to double check the full code

mod lexer;
mod parser;
mod codegen;
mod elf;

fn main() {
    println!("rustlet compiler");
}
Verify the build

Before you run the next command, predict: will cargo build succeed even though the module files are completely empty?

  • Build the project by running:
cargo build

The build completes with zero errors and zero warnings. Empty module files are valid Rust. Cargo also downloads and compiles the bumpalo crate during this first build.

  • Run the compiler to confirm the placeholder works:
cargo run

You should see rustlet compiler printed to the terminal.

Seeing a compilation error?

  • If you see an error about an unknown edition, make sure edition = "2024" is in your Cargo.toml and that your Rust version is 1.85.0 or higher. Run rustup update stable to get the latest version.
  • If you see a module-not-found error, check that all four files (src/lexer.rs, src/parser.rs, src/codegen.rs, src/elf.rs) exist in the src/ directory.
  • help me debug my cargo build error

Your project skeleton is in place. Next up, you will build the zero-copy lexer that transforms raw bytes into structured tokens without allocating a single string.

Build the Zero-Copy Lexer

Your compiler needs to break raw source text into meaningful pieces before it can understand structure. This process is called lexical analysis, and the component that does it is called a lexer.

Most lexers copy substrings out of the source for each token. Your lexer will operate directly on raw bytes (&[u8]) and store token spans as slices pointing back into the original source. The source is read once and never duplicated. This is the zero-copy foundation for the entire pipeline.

In this step, get ready to:
  • Define the token types and zero-copy token struct.
  • Implement the full lexer with byte-level dispatch and helper methods.
  • Test the lexer by tokenizing a hardcoded source string and printing the token stream.
Define the token types

Every lexer needs a vocabulary of token kinds it can recognize. Your lexer handles arithmetic operators, grouping symbols, the function arrow, the fn keyword, identifiers, and integer literals.

  • Open src/lexer.rs in Zed. Replace the empty file with the following token type definitions:
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TokenKind {
    Int(i64),
    Plus,
    Minus,
    Star,
    Slash,
    LParen,
    RParen,
    LBrace,
    RBrace,
    Arrow,
    Fn,
    Ident,
    Eof,
}

#[derive(Debug, Clone, Copy)]
pub struct Token<'src> {
    pub kind: TokenKind,
    pub span: &'src [u8],
}

pub struct Lexer<'src> {
    src: &'src [u8],
    pos: usize,
}

What does this code do?

TokenKind enumerates every kind of token the lexer can produce. Each variant maps to a symbol, keyword, or literal in the source.

Token holds a kind and a span: &'src [u8]. The span is a slice that points directly into the source bytes. No copy, no allocation. The lifetime 'src ties each token back to the original source buffer.

Lexer holds the source slice and a position cursor. It advances through the bytes one token at a time.

  • Save src/lexer.rs.
  • Confirm the types compile by running:
cargo build

You should see compilation succeed with some dead-code warnings. The types exist but nothing uses them yet.

Seeing a compilation error?

Check that each variant in TokenKind ends with a comma. Missing commas between enum variants are the most common Rust enum syntax error.

Why won't my Rust lexer module compile?

Implement the lexer methods

The lexer needs a constructor, a method to produce all tokens at once, and the core dispatch logic that reads one byte and decides which token to emit.

  • Below the Lexer struct definition in src/lexer.rs, add the impl block with the constructor and tokenization loop:
impl<'src> Lexer<'src> {
    pub fn new(src: &'src [u8]) -> Self {
        Self { src, pos: 0 }
    }

    pub fn tokenize(&mut self) -> Vec<Token<'src>> {
        let mut tokens = Vec::new();
        loop {
            let tok = self.next_token();
            let is_eof = tok.kind == TokenKind::Eof;
            tokens.push(tok);
            if is_eof { break; }
        }
        tokens
    }

What does this code do?

new() takes a byte slice and sets the read position to zero. tokenize() repeatedly calls next_token() until it hits Eof, collecting every token into a Vec.

  • Directly below the tokenize method (still inside the same impl block), add the core dispatch method:
    fn next_token(&mut self) -> Token<'src> {
        self.skip_whitespace();
        if self.pos >= self.src.len() {
            return Token { kind: TokenKind::Eof, span: &self.src[self.src.len()..] };
        }
        let start = self.pos;
        let byte = self.src[self.pos];
        match byte {
            b'+' => { self.pos += 1; Token { kind: TokenKind::Plus, span: &self.src[start..self.pos] } }
            b'*' => { self.pos += 1; Token { kind: TokenKind::Star, span: &self.src[start..self.pos] } }
            b'/' => { self.pos += 1; Token { kind: TokenKind::Slash, span: &self.src[start..self.pos] } }
            b'(' => { self.pos += 1; Token { kind: TokenKind::LParen, span: &self.src[start..self.pos] } }
            b')' => { self.pos += 1; Token { kind: TokenKind::RParen, span: &self.src[start..self.pos] } }
            b'{' => { self.pos += 1; Token { kind: TokenKind::LBrace, span: &self.src[start..self.pos] } }
            b'}' => { self.pos += 1; Token { kind: TokenKind::RBrace, span: &self.src[start..self.pos] } }
            b'-' => {
                if self.pos + 1 < self.src.len() && self.src[self.pos + 1] == b'>' {
                    self.pos += 2;
                    Token { kind: TokenKind::Arrow, span: &self.src[start..self.pos] }
                } else {
                    self.pos += 1;
                    Token { kind: TokenKind::Minus, span: &self.src[start..self.pos] }
                }
            }
            b'0'..=b'9' => self.lex_number(start),
            b'a'..=b'z' | b'A'..=b'Z' | b'_' => self.lex_ident(start),
            _ => panic!("Unexpected byte: 0x{:02x} at position {}", byte, self.pos),
        }
    }

What does this code do?

next_token() is a byte-level dispatch. It skips whitespace, checks for end-of-input, then matches the current byte against single-character operators and multi-character patterns.

The - arm peeks one byte ahead. If the next byte is >, it consumes two bytes and returns Arrow. Otherwise it returns Minus. Digits and letters delegate to helper methods.

  • Still inside the same impl block, add the three helper methods and then the closing brace:
    fn lex_number(&mut self, start: usize) -> Token<'src> {
        while self.pos < self.src.len() && self.src[self.pos].is_ascii_digit() {
            self.pos += 1;
        }
        let span = &self.src[start..self.pos];
        // SAFETY: span contains only ASCII digits (0x30..=0x39), which are valid UTF-8.
        let s = unsafe { std::str::from_utf8_unchecked(span) };
        let value: i64 = s.parse().expect("invalid integer literal");
        Token { kind: TokenKind::Int(value), span }
    }

    fn lex_ident(&mut self, start: usize) -> Token<'src> {
        while self.pos < self.src.len()
            && (self.src[self.pos].is_ascii_alphanumeric() || self.src[self.pos] == b'_')
        {
            self.pos += 1;
        }
        let span = &self.src[start..self.pos];
        let kind = if span == b"fn" { TokenKind::Fn } else { TokenKind::Ident };
        Token { kind, span }
    }

    fn skip_whitespace(&mut self) {
        while self.pos < self.src.len() && self.src[self.pos].is_ascii_whitespace() {
            self.pos += 1;
        }
    }
}

What does this code do?

lex_number() advances while bytes are ASCII digits, then uses from_utf8_unchecked to convert the digit bytes to a string for parsing. This is safe because you already know every byte in the span is an ASCII digit.

lex_ident() consumes alphanumeric bytes and underscores, then checks if the result is the fn keyword. skip_whitespace() advances past any ASCII whitespace between tokens.

  • Save src/lexer.rs.
  • Confirm the full module compiles by running:
cargo build

You should see compilation succeed. The dead-code warnings are still there because nothing calls the lexer yet.

Seeing a lifetime or borrow error?

Make sure your impl<'src> line declares the same lifetime parameter as the struct. Also verify that Token<'src> uses the same lifetime. Mismatched lifetime names cause borrow-checker failures.

Help me fix lifetime errors in my Rust lexer

Test the lexer with a hardcoded source string

The lexer compiles, but you need to see it actually tokenize source code. You will temporarily replace the placeholder main() with one that feeds a byte string into the lexer and prints every token.

  • Open src/main.rs and replace the entire file contents with:
mod lexer;
mod parser;
mod codegen;
mod elf;

fn main() {
    let source = b"fn main() -> i64 { 2 + 3 * 4 }";
    let mut lex = lexer::Lexer::new(source);
    let tokens = lex.tokenize();
    for tok in &tokens {
        println!("{:?}", tok.kind);
    }
}

What does this code do?

The b"..." prefix creates a byte string literal (&[u8; N]). This feeds directly into your lexer with no UTF-8 overhead. The loop prints each token's kind so you can verify the lexer splits the source correctly.

  • Save src/main.rs.

Before you run this, what sequence of tokens do you expect for the source string fn main() -> i64 { 2 + 3 * 4 }? Think through each character group.

  • Run the compiler to see the token stream:
cargo run

You should see this output:

Fn
Ident
LParen
RParen
Arrow
Ident
LBrace
Int(2)
Plus
Int(3)
Star
Int(4)
RBrace
Eof

Each line corresponds to one token. Fn is the keyword, Ident covers both main and i64, and Arrow proves the two-byte lookahead works.

Output looks wrong or panics?

If you see a panic about an unexpected byte, check that your match arms cover all the symbols in the source string. The - arm must appear before the catch-all _ arm.

If integers show wrong values, verify that lex_number starts consuming from the byte that triggered the digit branch (the start parameter should equal the position of the first digit).

Help me debug my lexer output

Why does operating on bytes matter?

A lexer recognizes a regular language. Each byte-match branch in next_token corresponds to a transition in a deterministic finite automaton (DFA). By working directly on &[u8] instead of &str, you skip UTF-8 validation overhead entirely. For ASCII source code, every byte is exactly one character.

✔️ Awesome, I've got everything!

Great. Double check you have saved both src/lexer.rs and src/main.rs.

ⓧ I'd like to double check the full code

Here is the full src/main.rs:

mod lexer;
mod parser;
mod codegen;
mod elf;

fn main() {
    let source = b"fn main() -> i64 { 2 + 3 * 4 }";
    let mut lex = lexer::Lexer::new(source);
    let tokens = lex.tokenize();
    for tok in &tokens {
        println!("{:?}", tok.kind);
    }
}

For src/lexer.rs, confirm you have these sections in order: the TokenKind enum (15 variants), the Token struct, the Lexer struct, then one impl block containing new, tokenize, next_token, lex_number, lex_ident, and skip_whitespace. Scroll up and verify each chunk matches what you pasted.

Your lexer transforms a flat byte stream into structured tokens without a single heap allocation per token. Next up, you will parse those tokens into an AST and compile your first expression all the way to a running native binary.

Parse, Compile, and Run Your First Binary

Your lexer transforms raw bytes into structured tokens. But tokens alone are inert data. To produce a running program you need three more stages: a parser that builds a tree of operations, a code generator that emits raw machine instructions, and a binary writer that wraps those instructions in a format the OS can execute.

In this step, you will implement all three stages and connect them to the lexer. By the end, you will compile a Rust source file into a native x86_64 Linux binary that computes an arithmetic result and reports it as its exit code.

In this step, get ready to:
  • Build a recursive descent parser that constructs a bump-allocated AST.
  • Implement an x86_64 code generator and ELF binary writer from scratch.
  • Wire the full pipeline and compile your first expression into a native executable.
Implement the recursive descent parser

A parser consumes the flat token stream and builds an Abstract Syntax Tree (AST) that captures the structure of the expression. Each AST node lives in a bumpalo arena so there are zero individual heap allocations.

  • Open src/parser.rs in your editor and add the AST type definitions at the top of the file:
use bumpalo::Bump;
use crate::lexer::{Token, TokenKind};

#[derive(Debug)]
pub enum Expr<'ast> {
    Int(i64),
    BinOp {
        op: BinOp,
        lhs: &'ast Expr<'ast>,
        rhs: &'ast Expr<'ast>,
    },
}

#[derive(Debug, Clone, Copy)]
pub enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
}

What does this code do?

Expr<'ast> is the AST node type. Int holds a literal integer value. BinOp holds an operator and two references to child expressions.

The 'ast lifetime ties every node reference to the bumpalo arena. When the arena drops, all nodes drop together in one shot.

  • Below the type definitions, add the Parser struct, its constructor, and the top-level parse_program method:
pub struct Parser<'src, 'ast> {
    tokens: &'src [Token<'src>],
    pos: usize,
    bump: &'ast Bump,
}

impl<'src, 'ast> Parser<'src, 'ast> {
    pub fn new(tokens: &'src [Token<'src>], bump: &'ast Bump) -> Self {
        Self { tokens, pos: 0, bump }
    }

    pub fn parse_program(&mut self) -> Result<&'ast Expr<'ast>, String> {
        self.expect(TokenKind::Fn)?;
        self.expect_ident(b"main")?;
        self.expect(TokenKind::LParen)?;
        self.expect(TokenKind::RParen)?;
        self.expect(TokenKind::Arrow)?;
        self.expect_ident(b"i64")?;
        self.expect(TokenKind::LBrace)?;
        let expr = self.parse_expr(0)?;
        self.expect(TokenKind::RBrace)?;
        Ok(expr)
    }

What does parse_program do?

It expects the fixed wrapper tokens fn main() -> i64 { ... } one by one, then delegates to parse_expr for the actual expression inside the braces.

The min_prec: 0 argument passed to parse_expr means "accept any operator regardless of precedence". You will see how this parameter controls binding strength in the methods below.

  • Still inside the impl block (before the closing }), add the expression parsing methods:
    fn parse_expr(&mut self, min_prec: u8) -> Result<&'ast Expr<'ast>, String> {
        let mut lhs = self.parse_atom()?;
        loop {
            let Some((op, prec)) = self.peek_binop() else { break; };
            if prec < min_prec { break; }
            self.pos += 1;
            let rhs = self.parse_expr(prec + 1)?;
            lhs = self.bump.alloc(Expr::BinOp { op, lhs, rhs });
        }
        Ok(lhs)
    }

    fn parse_atom(&mut self) -> Result<&'ast Expr<'ast>, String> {
        let tok = self.current();
        match tok.kind {
            TokenKind::Int(val) => {
                self.pos += 1;
                Ok(self.bump.alloc(Expr::Int(val)))
            }
            TokenKind::LParen => {
                self.pos += 1;
                let expr = self.parse_expr(0)?;
                self.expect(TokenKind::RParen)?;
                Ok(expr)
            }
            _ => Err(format!("Expected expression, got {:?}", tok.kind)),
        }
    }

    fn current(&self) -> &Token<'src> {
        &self.tokens[self.pos]
    }

How does precedence climbing work?

parse_expr accepts a min_prec threshold. It only consumes an operator if that operator's precedence is at or above the threshold. When it recurses for the right-hand side, it passes prec + 1, which forces higher-precedence operators to bind tighter before control returns.

parse_atom handles the base cases: integer literals and parenthesized sub-expressions. Parentheses reset the threshold to 0, allowing any operator inside them.

  • Add the utility methods that complete the parser, then close the impl block:
    fn peek_binop(&self) -> Option<(BinOp, u8)> {
        match self.current().kind {
            TokenKind::Plus => Some((BinOp::Add, 1)),
            TokenKind::Minus => Some((BinOp::Sub, 1)),
            TokenKind::Star => Some((BinOp::Mul, 2)),
            TokenKind::Slash => Some((BinOp::Div, 2)),
            _ => None,
        }
    }

    fn expect(&mut self, kind: TokenKind) -> Result<(), String> {
        if self.current().kind == kind {
            self.pos += 1;
            Ok(())
        } else {
            Err(format!("Expected {:?}, got {:?}", kind, self.current().kind))
        }
    }

What do the precedence levels mean?

peek_binop returns a tuple of the operator and its precedence level. Addition and subtraction sit at level 1. Multiplication and division sit at level 2. A higher number means the operator binds tighter.

  • Add the final helper method and the closing brace of the impl block:
    fn expect_ident(&mut self, expected: &[u8]) -> Result<(), String> {
        let tok = self.current();
        match tok.kind {
            TokenKind::Ident | TokenKind::Fn => {
                if tok.span == expected {
                    self.pos += 1;
                    Ok(())
                } else {
                    Err(format!("Expected '{}', got '{}'", String::from_utf8_lossy(expected), String::from_utf8_lossy(tok.span)))
                }
            }
            _ => Err(format!("Expected identifier, got {:?}", tok.kind)),
        }
    }
}

Why match both Ident and Fn?

The lexer classifies fn as TokenKind::Fn (a keyword), not Ident. But expect_ident is also used for main and i64, which ARE identifiers. Matching both kinds lets it handle the keyword fn case if called with b"fn" while still working for regular identifiers.

  • Save src/parser.rs.
  • Verify the parser compiles by running:
cargo build

You should see the build succeed with no errors. You may see an "unused import" warning for parser since main.rs does not use it yet. That is expected.

Seeing a compilation error?

  • Check that every method is inside the impl<'src, 'ast> Parser<'src, 'ast> block and the block ends with a single closing }.
  • Verify your use statement at the top imports Token and TokenKind from crate::lexer.
  • Make sure Bump is imported from bumpalo, not from std.

Help me debug a compilation error in my parser

Build the x86_64 code generator and ELF writer

The code generator translates AST nodes into raw x86_64 machine instructions. It uses a stack-based model: each value is pushed onto the hardware stack, and operators pop their operands, compute, and push the result back.

  • Open src/codegen.rs and add the IR definition and lowering functions:
use crate::parser::{Expr, BinOp};

#[derive(Debug, Clone)]
pub enum IrOp {
    PushInt(i64),
    Add,
    Sub,
    Mul,
    Div,
}

pub fn lower_to_ir(expr: &Expr) -> Vec<IrOp> {
    let mut ops = Vec::new();
    lower_expr(expr, &mut ops);
    ops
}

fn lower_expr(expr: &Expr, ops: &mut Vec<IrOp>) {
    match expr {
        Expr::Int(val) => ops.push(IrOp::PushInt(*val)),
        Expr::BinOp { op, lhs, rhs } => {
            lower_expr(lhs, ops);
            lower_expr(rhs, ops);
            match op {
                BinOp::Add => ops.push(IrOp::Add),
                BinOp::Sub => ops.push(IrOp::Sub),
                BinOp::Mul => ops.push(IrOp::Mul),
                BinOp::Div => ops.push(IrOp::Div),
            }
        }
    }
}

What is the IR layer?

IrOp is a flat, stack-machine intermediate representation. lower_to_ir walks the tree and emits a linear sequence of operations: push integers, then combine them with arithmetic ops.

This decouples the parser from any specific CPU architecture. The backend reads the IR without needing to know how the AST was structured.

  • Below the IR code, add the Backend trait and the X86_64Backend struct with its instruction emission helpers:
pub trait Backend {
    fn compile(&mut self, ops: &[IrOp]) -> Vec<u8>;
}

pub struct X86_64Backend {
    code: Vec<u8>,
}

impl X86_64Backend {
    pub fn new() -> Self {
        Self { code: Vec::with_capacity(256) }
    }

    fn emit(&mut self, bytes: &[u8]) {
        self.code.extend_from_slice(bytes);
    }

    fn emit_mov_rax_imm64(&mut self, val: i64) {
        self.emit(&[0x48, 0xB8]);
        self.emit(&val.to_le_bytes());
    }

    fn emit_push_rax(&mut self) { self.emit(&[0x50]); }
    fn emit_pop_rax(&mut self) { self.emit(&[0x58]); }
    fn emit_pop_rcx(&mut self) { self.emit(&[0x59]); }
    fn emit_pop_rdi(&mut self) { self.emit(&[0x5F]); }
    fn emit_add_rax_rcx(&mut self) { self.emit(&[0x48, 0x01, 0xC8]); }
    fn emit_sub_rax_rcx(&mut self) { self.emit(&[0x48, 0x29, 0xC8]); }
    fn emit_imul_rax_rcx(&mut self) { self.emit(&[0x48, 0x0F, 0xAF, 0xC1]); }
    fn emit_cqo(&mut self) { self.emit(&[0x48, 0x99]); }
    fn emit_idiv_rcx(&mut self) { self.emit(&[0x48, 0xF7, 0xF9]); }

What are these byte sequences?

Each method emits the raw x86_64 instruction encoding as bytes. For example, 0x50 is push rax, and 0x59 is pop rcx. The 0x48 prefix is the REX.W byte that marks 64-bit operand size.

The stack-based model means: push each value, pop two when you need to operate, push the result. The CPU's hardware stack does all the bookkeeping.

  • Complete the X86_64Backend with the remaining helpers and the Backend trait implementation:
    fn emit_mov_eax_imm32(&mut self, val: u32) {
        self.emit(&[0xB8]);
        self.emit(&val.to_le_bytes());
    }
    fn emit_syscall(&mut self) { self.emit(&[0x0F, 0x05]); }
}

impl Backend for X86_64Backend {
    fn compile(&mut self, ops: &[IrOp]) -> Vec<u8> {
        self.code.clear();
        for op in ops {
            match op {
                IrOp::PushInt(val) => { self.emit_mov_rax_imm64(*val); self.emit_push_rax(); }
                IrOp::Add => { self.emit_pop_rcx(); self.emit_pop_rax(); self.emit_add_rax_rcx(); self.emit_push_rax(); }
                IrOp::Sub => { self.emit_pop_rcx(); self.emit_pop_rax(); self.emit_sub_rax_rcx(); self.emit_push_rax(); }
                IrOp::Mul => { self.emit_pop_rcx(); self.emit_pop_rax(); self.emit_imul_rax_rcx(); self.emit_push_rax(); }
                IrOp::Div => { self.emit_pop_rcx(); self.emit_pop_rax(); self.emit_cqo(); self.emit_idiv_rcx(); self.emit_push_rax(); }
            }
        }
        self.emit_pop_rdi();
        self.emit_mov_eax_imm32(60);
        self.emit_syscall();
        self.code.clone()
    }
}

What does the epilogue do?

After all IR ops are compiled, the final value sits on top of the stack. The epilogue pops it into rdi (the first argument register), loads syscall number 60 (sys_exit) into eax, and executes syscall. The process exits with the computed value as its exit code.

  • Save src/codegen.rs.
  • Now open src/elf.rs and add the ELF configuration constants and struct:
const ELF_HEADER_SIZE: u64 = 64;
const PROGRAM_HEADER_SIZE: u64 = 56;
const TOTAL_HEADER_SIZE: u64 = ELF_HEADER_SIZE + PROGRAM_HEADER_SIZE;

pub struct ElfConfig {
    pub machine: u16,
    pub base_addr: u64,
}

impl ElfConfig {
    pub fn x86_64() -> Self {
        Self { machine: 0x3E, base_addr: 0x400000 }
    }
}

What are these ELF constants?

An ELF64 binary has a 64-byte file header and one or more 56-byte program headers. The Linux kernel reads the program header to map the binary into memory at base_addr (0x400000 is the traditional x86_64 load address). Machine type 0x3E identifies x86_64.

  • Below the config, add the write_elf function that assembles the raw binary:
pub fn write_elf(config: &ElfConfig, code: &[u8]) -> Vec<u8> {
    let file_size = TOTAL_HEADER_SIZE as usize + code.len();
    let entry_point = config.base_addr + TOTAL_HEADER_SIZE;
    let mut buf = Vec::with_capacity(file_size);
    buf.extend_from_slice(&[0x7F, b'E', b'L', b'F', 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
    buf.extend_from_slice(&2u16.to_le_bytes());
    buf.extend_from_slice(&config.machine.to_le_bytes());
    buf.extend_from_slice(&1u32.to_le_bytes());
    buf.extend_from_slice(&entry_point.to_le_bytes());
    buf.extend_from_slice(&ELF_HEADER_SIZE.to_le_bytes());
    buf.extend_from_slice(&0u64.to_le_bytes());
    buf.extend_from_slice(&0u32.to_le_bytes());
    buf.extend_from_slice(&(ELF_HEADER_SIZE as u16).to_le_bytes());
    buf.extend_from_slice(&(PROGRAM_HEADER_SIZE as u16).to_le_bytes());
    buf.extend_from_slice(&1u16.to_le_bytes());
    buf.extend_from_slice(&0u16.to_le_bytes());
    buf.extend_from_slice(&0u16.to_le_bytes());
    buf.extend_from_slice(&0u16.to_le_bytes());
    buf.extend_from_slice(&1u32.to_le_bytes());
    buf.extend_from_slice(&5u32.to_le_bytes());
    buf.extend_from_slice(&0u64.to_le_bytes());
    buf.extend_from_slice(&config.base_addr.to_le_bytes());
    buf.extend_from_slice(&config.base_addr.to_le_bytes());
    buf.extend_from_slice(&(file_size as u64).to_le_bytes());
    buf.extend_from_slice(&(file_size as u64).to_le_bytes());
    buf.extend_from_slice(&0x200000u64.to_le_bytes());
    buf.extend_from_slice(code);
    buf
}

What is happening in this function?

The function writes the ELF magic bytes (\x7FELF), then the 64-byte header fields (type, machine, entry point, program header offset), then a single 56-byte program header that tells Linux to load the entire file as readable and executable (PF_R | PF_X = 5).

The entry point is base_addr + 120 (64 + 56 bytes of headers), so execution starts at the first machine code byte immediately after the headers.

  • Save src/elf.rs.
  • Verify both new modules compile by running:
cargo build

You should see a clean build with no errors.

Getting type mismatch errors in codegen?

  • Verify the use crate::parser::{Expr, BinOp}; import at the top of src/codegen.rs matches the public types you defined in src/parser.rs.
  • Check that both Expr and BinOp have pub visibility in the parser module.

Help me debug a compilation error in my codegen or ELF module

Wire the pipeline and compile your first binary

All four modules are implemented. Now you need to replace the temporary tokenizer test in main.rs with the full compilation pipeline: read source, lex, parse, lower to IR, compile to machine code, write ELF, and mark executable.

  • Replace the entire contents of src/main.rs with the CLI argument handling and file reading:
mod lexer;
mod parser;
mod codegen;
mod elf;

use std::env;
use std::fs;
use std::os::unix::fs::PermissionsExt;
use std::process;

fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() < 4 || args[2] != "-o" {
        eprintln!("Usage: rustlet <input.rs> -o <output>");
        process::exit(1);
    }

    let input_path = &args[1];
    let output_path = &args[3];

    let source = fs::read(input_path).unwrap_or_else(|e| {
        eprintln!("Error reading {}: {}", input_path, e);
        process::exit(1);
    });

What does this code do?

The CLI expects the pattern rustlet <input.rs> -o <output>. It reads the source file as raw bytes (matching the lexer's &[u8] input type) and exits with a clear error message if anything is wrong.

  • Below the source reading code (still inside fn main()), add the full compilation pipeline and close the function:
    let mut lex = lexer::Lexer::new(&source);
    let tokens = lex.tokenize();

    let bump = bumpalo::Bump::new();
    let mut parser = parser::Parser::new(&tokens, &bump);
    let ast = parser.parse_program().unwrap_or_else(|e| {
        eprintln!("Parse error: {}", e);
        process::exit(1);
    });

    let ir = codegen::lower_to_ir(ast);

    let mut backend = codegen::X86_64Backend::new();
    let machine_code = codegen::Backend::compile(&mut backend, &ir);

    let config = elf::ElfConfig::x86_64();
    let binary = elf::write_elf(&config, &machine_code);

    fs::write(output_path, &binary).unwrap_or_else(|e| {
        eprintln!("Error writing {}: {}", output_path, e);
        process::exit(1);
    });

    let mut perms = fs::metadata(output_path).unwrap().permissions();
    perms.set_mode(0o755);
    fs::set_permissions(output_path, perms).unwrap();

    println!("Compiled: {}", output_path);
}

What does this pipeline do?

The pipeline flows in five stages: lex (bytes to tokens), parse (tokens to AST using a bumpalo arena), lower (AST to stack-machine IR), compile (IR to raw x86_64 bytes), and write (machine code wrapped in an ELF binary with executable permissions).

set_mode(0o755) marks the output file as executable so you can run it directly from the shell.

  • Save src/main.rs.
  • Create a test source file by running:
echo 'fn main() -> i64 { 3 + 5 }' > test.rs

Before you compile this, what exit code do you think the resulting binary will produce?

  • Compile the test file by running:
cargo run -- test.rs -o test_bin

You should see Compiled: test_bin printed to the terminal.

  • Execute the compiled binary and check its exit code by running:
./test_bin; echo $?

You should see 8 printed. That is the result of 3 + 5, computed by raw machine code your compiler just emitted. No assembler, no linker, no LLVM.

Seeing "Permission denied" or a segfault?

  • If you get Permission denied, the executable bit was not set. Run chmod +x test_bin manually and retry.
  • A segfault usually means the ELF entry point calculation is wrong. Verify that entry_point equals config.base_addr + TOTAL_HEADER_SIZE (should be 0x400078).
  • If the exit code is wrong, check that emit_pop_rdi uses byte 0x5F and the syscall number for sys_exit is 60.

Help me debug why my compiled binary crashes or returns the wrong exit code

✔️ Awesome, I've got everything!

Great. Double check you have saved all four source files.

ⓧ I'd like to double check the full code

Your project now has four source files. Scroll up and confirm each chunk is present in order:

  • src/parser.rs: imports, Expr/BinOp enums, Parser struct with new(), parse_program(), parse_expr(), parse_atom(), current(), peek_binop(), expect(), expect_ident().
  • src/codegen.rs: IrOp enum, lower_to_ir(), lower_expr(), Backend trait, X86_64Backend struct with all emit helpers, Backend impl.
  • src/elf.rs: constants, ElfConfig struct with x86_64(), write_elf().
  • src/main.rs: mod declarations, imports, CLI parsing, full pipeline (lex, parse, lower, compile, write ELF, set permissions).

You just went from source text to a running native binary in one shot. Next up, you will discover a subtle bug in how the parser handles operator precedence and fix it with the precedence climbing algorithm.

Fix Operator Precedence with Precedence Climbing

Your compiler produces running binaries, but does it evaluate math correctly? The expression 2 + 3 * 4 should evaluate to 14 (multiplication binds tighter than addition), not 20.

This is the fundamental correctness problem that precedence climbing solves. In this step, you will verify that your parser's precedence climbing logic produces the correct parse tree, then test parenthesized expressions that override precedence.

In this step, get ready to:
  • Test operator precedence with a mixed-operator expression.
  • Understand how precedence climbing builds the correct AST.
  • Verify parenthesized expressions override default precedence.
Test operator precedence with a mixed expression

A parser that treats all operators with equal precedence would evaluate 2 + 3 * 4 left-to-right as (2 + 3) * 4 = 20. The correct answer is 14, because multiplication binds tighter.

  • Create a test file called test2.rs in your rustlet project directory by running:
echo 'fn main() -> i64 { 2 + 3 * 4 }' > test2.rs
  • Before you compile, predict: will the exit code be 14 (correct precedence) or 20 (left-to-right)?
  • Compile and run the test by running:
cargo run -- test2.rs -o test2_bin
./test2_bin; echo $?

You should see 14 as the exit code. The parser correctly built the AST as 2 + (3 * 4) because multiplication has higher precedence than addition.

Seeing 20 instead of 14?

If the exit code is 20, your peek_binop function may be returning the same precedence for all operators. Check that Plus and Minus return precedence 1, while Star and Slash return precedence 2.

Help me debug why my parser gives wrong precedence for 2 + 3 * 4.

Understand how precedence climbing builds the correct tree

The precedence climbing algorithm in your parse_expr function uses a single parameter to control which operators it is allowed to consume.

  • Open src/parser.rs and find the parse_expr function:
fn parse_expr(&mut self, min_prec: u8) -> Result<&'ast Expr<'ast>, String> {
    let mut lhs = self.parse_atom()?;
    loop {
        let Some((op, prec)) = self.peek_binop() else { break; };
        if prec < min_prec { break; }
        self.pos += 1;
        let rhs = self.parse_expr(prec + 1)?;
        lhs = self.bump.alloc(Expr::BinOp { op, lhs, rhs });
    }
    Ok(lhs)
}

How does precedence climbing work?

Walk through 2 + 3 * 4 step by step. The initial call is parse_expr(0). It parses atom 2, then sees + with precedence 1. Since 1 >= 0, it consumes the operator and recurses with parse_expr(2).

The recursive call parses atom 3, then sees * with precedence 2. Since 2 >= 2, it consumes the operator and recurses again with parse_expr(3). That call parses 4 and sees no operator with precedence >= 3, so it returns.

The result is BinOp(+, 2, BinOp(*, 3, 4)). The prec + 1 recursion is the key. It forces higher-precedence operators to "climb" into tighter sub-expressions before returning to lower-precedence ones.

  • Now look at the peek_binop function that defines the precedence levels:
fn peek_binop(&self) -> Option<(BinOp, u8)> {
    match self.current().kind {
        TokenKind::Plus => Some((BinOp::Add, 1)),
        TokenKind::Minus => Some((BinOp::Sub, 1)),
        TokenKind::Star => Some((BinOp::Mul, 2)),
        TokenKind::Slash => Some((BinOp::Div, 2)),
        _ => None,
    }
}

Why is this equivalent to a Pratt parser?

Precedence climbing and Pratt parsing are mathematically equivalent. Each precedence level corresponds to a production rule in the grammar. Level 1 (add/sub) binds loosely. Level 2 (mul/div) binds tightly. The algorithm is O(n) in the number of tokens.

Verify parenthesized expressions override precedence

Parentheses let the programmer override default precedence. When parse_atom sees an LParen token, it calls parse_expr(0) recursively, resetting the minimum precedence back to zero.

  • Find the parse_atom function in src/parser.rs to see how parentheses are handled:
fn parse_atom(&mut self) -> Result<&'ast Expr<'ast>, String> {
    let tok = self.current();
    match tok.kind {
        TokenKind::Int(val) => {
            self.pos += 1;
            Ok(self.bump.alloc(Expr::Int(val)))
        }
        TokenKind::LParen => {
            self.pos += 1;
            let expr = self.parse_expr(0)?;
            self.expect(TokenKind::RParen)?;
            Ok(expr)
        }
        _ => Err(format!("Expected expression, got {:?}", tok.kind)),
    }
}

What does resetting to parse_expr(0) accomplish?

By calling parse_expr(0) inside parentheses, any operator (even low-precedence +) can appear inside the group. The RParen boundary naturally terminates the sub-expression because peek_binop returns None for a closing paren, breaking the loop.

  • Create a parenthesized test file and compile it by running:
echo 'fn main() -> i64 { (2 + 3) * 4 }' > test3.rs
cargo run -- test3.rs -o test3_bin
  • Before running the binary, predict the exit code. The parentheses force addition to happen first.
  • Run the binary and check the exit code:
./test3_bin; echo $?

You should see 20. The parentheses forced (2 + 3) to evaluate first, then the result was multiplied by 4.

Seeing a parse error?

If you see a parse error mentioning "Expected expression", make sure your parse_atom function has the TokenKind::LParen match arm that consumes the paren and calls parse_expr(0).

Help me debug why parenthesized expressions aren't parsing in my compiler.

✔️ Awesome, I've got everything!

Great. Confirm you have saved src/parser.rs and that both test expressions produce the correct exit codes.

ⓧ I'd like to double check the full code

Here is the full src/parser.rs for reference. Scroll up through your file and confirm each function matches.

  • The peek_binop function returns precedence 1 for Plus/Minus and precedence 2 for Star/Slash.
  • The parse_expr loop only consumes operators with prec >= min_prec, and recurses with prec + 1.
  • The parse_atom function handles LParen by calling parse_expr(0) and expecting RParen.

Your parser now handles operator precedence correctly, and parentheses let the programmer override it. Next up, you will decouple the frontend from the backend by introducing an IR layer and a Backend trait, making your compiler extensible to new CPU architectures.

Add the IR Layer and Backend Trait

Your compiler works end-to-end. But if you look at src/codegen.rs right now, you'll notice something important about how it's structured: the AST never touches x86_64 instructions directly.

Your code already has an intermediate representation (the IrOp enum) and a Backend trait separating the frontend from machine code generation. In this step, you'll understand why this architecture matters and how it makes your compiler extensible to any CPU target.

In this step, get ready to:
  • Understand how the IR decouples parsing from code generation.
  • Trace the full pipeline from source to binary through each layer.
  • Verify the architecture produces byte-identical output to confirm nothing was lost in the abstraction.
Understand the IR layer

Without an intermediate representation, the parser would emit x86_64 bytes directly. That locks the entire frontend to one CPU architecture.

  • Open src/codegen.rs in Zed and find the IrOp enum at the top of the file.
#[derive(Debug, Clone)]
pub enum IrOp {
    PushInt(i64),
    Add,
    Sub,
    Mul,
    Div,
}

What is this IR doing?

This is a stack-machine instruction set. Each variant maps to one logical operation: push a value, or combine the top two stack values with an arithmetic operation.

The IR knows nothing about registers, opcodes, or CPU architectures. It's a portable description of what the program does, not how the hardware does it.

  • Now find the lower_to_ir and lower_expr functions below the enum.
pub fn lower_to_ir(expr: &Expr) -> Vec<IrOp> {
    let mut ops = Vec::new();
    lower_expr(expr, &mut ops);
    ops
}

fn lower_expr(expr: &Expr, ops: &mut Vec<IrOp>) {
    match expr {
        Expr::Int(val) => ops.push(IrOp::PushInt(*val)),
        Expr::BinOp { op, lhs, rhs } => {
            lower_expr(lhs, ops);
            lower_expr(rhs, ops);
            match op {
                BinOp::Add => ops.push(IrOp::Add),
                BinOp::Sub => ops.push(IrOp::Sub),
                BinOp::Mul => ops.push(IrOp::Mul),
                BinOp::Div => ops.push(IrOp::Div),
            }
        }
    }
}

Why walk the AST into a flat Vec?

The recursive lower_expr walks the tree and emits IR ops in execution order. For 2 + 3 * 4, it produces: PushInt(2), PushInt(3), PushInt(4), Mul, Add.

This flattened sequence is what any backend consumes. The backend never needs to traverse a tree or understand precedence. It just processes ops left to right.

Understand the Backend trait

The IR is the contract between the frontend and any code generator. The Backend trait formalizes that contract.

  • Scroll down in src/codegen.rs to find the Backend trait definition.
pub trait Backend {
    fn compile(&mut self, ops: &[IrOp]) -> Vec<u8>;
}

Why a trait instead of a plain function?

A trait means any struct that implements Backend can slot into the pipeline. To add ARM64 support, you would create an Aarch64Backend struct, implement the single compile method, and the parser, lexer, and IR stay untouched.

Why this approach over direct AST codegen?

Without the IR and trait, adding a second target would mean duplicating every AST-walking function. With them, the compiler frontend is written once and works for every architecture.

This is the same separation that LLVM provides between its frontends (Clang, rustc) and backends (x86, ARM, RISC-V). Your version is smaller but follows the same principle.

Trace the full pipeline in main.rs

Every layer feeds the next in a clean chain. Each stage has a single responsibility.

  • Switch to src/main.rs and find the pipeline section after the argument parsing.
// Lex: &[u8] -> Vec<Token>
let mut lex = lexer::Lexer::new(&source);
let tokens = lex.tokenize();

// Parse: Vec<Token> -> &Expr (arena-allocated AST)
let bump = bumpalo::Bump::new();
let mut parser = parser::Parser::new(&tokens, &bump);
let ast = parser.parse_program().unwrap_or_else(|e| {
    eprintln!("Parse error: {}", e);
    process::exit(1);
});

// Lower: &Expr -> Vec<IrOp>
let ir = codegen::lower_to_ir(ast);

// Compile: Vec<IrOp> -> Vec<u8> (machine code)
let mut backend = codegen::X86_64Backend::new();
let machine_code = codegen::Backend::compile(&mut backend, &ir);

// Emit: Vec<u8> -> ELF binary file
let config = elf::ElfConfig::x86_64();
let binary = elf::write_elf(&config, &machine_code);

What does each stage produce?

  • Lexer: raw bytes to a flat token stream.
  • Parser: tokens to a tree (AST) in a bumpalo arena.
  • Lowering: tree to a flat stack-machine program (IR).
  • Backend: IR to raw x86_64 bytes.
  • ELF writer: raw bytes to a loadable executable.
  • Notice how ElfConfig::x86_64() parameterizes the binary format. Open src/elf.rs and find the ElfConfig struct.
pub struct ElfConfig {
    pub machine: u16,
    pub base_addr: u64,
}

impl ElfConfig {
    pub fn x86_64() -> Self {
        Self { machine: 0x3E, base_addr: 0x400000 }
    }
}

What do these fields control?

The machine field is the ELF e_machine value. For x86_64 it's 0x3E (62 decimal). For AArch64 it would be 0xB7 (183 decimal).

The base_addr is where the Linux kernel loads the program in virtual memory. The traditional x86_64 address is 0x400000. A future ARM64 backend would use a different convention.

Before you run the tests, think about whether this abstraction layer could have changed the output. The IR is a lossless encoding of the AST. The backend emits the exact same bytes for the same IR ops. Do you expect the exit codes to differ?

  • Verify your compiler still produces correct output by running:
cargo run -- test.rs -o test_bin && ./test_bin; echo $?

You should see 8 as the exit code.

  • Now test the precedence expression:
cargo run -- test2.rs -o test2_bin && ./test2_bin; echo $?

You should see 14. The output is byte-for-byte identical to what you had before. The abstraction costs nothing at runtime.

Getting a different exit code?

Make sure test.rs contains exactly fn main() -> i64 { 3 + 5 } and test2.rs contains fn main() -> i64 { 2 + 3 * 4 }. Extra whitespace is fine, but the expression must match.

help me debug why my compiler exit code is wrong

Extra for Experts: how would you add an ARM64 backend?

You would create a struct Aarch64Backend implementing Backend. Its compile method would emit ARM64 instructions (fixed-width 32-bit encodings) for each IrOp. Then you'd add an ElfConfig::aarch64() with machine: 0xB7. No changes to the lexer, parser, or IR lowering.

Your compiler now has a clean five-stage architecture: lex, parse, lower, compile, emit. Each stage has one job and one interface. Adding a new language feature touches the frontend. Adding a new CPU target touches only the backend. This is the foundation that makes compilers scale.

Secret mission

Unary Negation and Modulo

Your compiler handles addition, subtraction, multiplication, and division. But what about negating a value or computing a remainder? Extend every stage of the pipeline with unary negation and the modulo operator to prove your architecture scales.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files or delete them.

Resources you used:

  • The rustlet project folder on your Desktop (includes all source code, test files, and compiled binaries).

Keep everything running

No action needed. Choose this if you plan to keep extending your compiler with new language features or backend targets.

  • Your rustlet project stays on your Desktop, ready to build on.
  • Compiled test binaries (test_bin, etc.) remain in the project folder.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files sit on disk and consume no resources beyond storage.

  • Optionally remove compiled artifacts to save disk space by running this from inside the project folder:
cargo clean

This removes the target/ directory containing build outputs. Your source files remain untouched.

Delete - I don't want to use this again

Remove all project files and compiled binaries from your system.

  • Delete the entire project folder by running:
rm -rf ~/Desktop/rustlet
  • Confirm it is gone by running:
ls ~/Desktop/rustlet

You should see a "No such file or directory" message confirming the folder is removed.

Nice Work!

Nice Work!

You just built a from-scratch compiler that transforms Rust source code into a native x86_64 Linux binary. No assembler, no linker, no LLVM. Every byte in that executable came from your code.

You've learned how to:

  • Built a complete compiler pipeline from source text to native x86_64 ELF binary, hand-encoding machine instructions and ELF headers from first principles.
  • Implemented precedence climbing for correct operator precedence, and used bumpalo arena allocation for a zero-per-node-heap-allocation AST.
  • Designed an extensible architecture with an IR layer and Backend trait, decoupling the frontend from any specific CPU target so adding ARM64 or RISC-V is one trait implementation away.
  • Secret Mission: Extended every pipeline stage with unary negation and modulo, proving the architecture scales cleanly when new constructs touch all four modules.

Ready to quiz yourself?