Build a Toy Compiler in Rust: Lexer, Parser, and Bytecode VM

What you'll build / learn

A working compiler pipeline for a tiny language — let bindings, integer arithmetic, print — written in about 300 lines of dependency-free Rust. You'll tokenize source text, parse it into an AST with a Pratt-style expression parser, compile that to bytecode, and execute it on a stack-based VM you write yourself.

Prerequisites

• Rust stable 1.97.1 (what this tutorial was built and tested against). Anything ≥ 1.85 works, since the project uses edition 2024. Install via rustup: curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh, or rustup update stable if you already have it.
• Any OS — the code is pure std, no crates, no platform-specific calls. Verified on macOS (arm64); Linux and Windows behave identically.
• Comfort reading Rust enums, pattern matching, and Result.

1. Scaffold the project

cargo new tinylang
cd tinylang
mkdir examples

cargo new on a current toolchain generates edition = "2024" in Cargo.toml — leave it as is. Create the program we'll be compiling, examples/demo.tiny:

// tinylang demo
let width = 12;
let height = 7 + 3;
print width * height;
print (width - 2) / 5;
print -width + 100;

2. Lexer: source text to tokens

The lexer flattens raw characters into a Vec<Token> so the parser never deals with whitespace, comments, or multi-digit numbers. Create src/lexer.rs:

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    Number(i64),
    Ident(String),
    Let,
    Print,
    Plus,
    Minus,
    Star,
    Slash,
    Equals,
    LParen,
    RParen,
    Semi,
}

pub fn lex(src: &str) -> Result<Vec<Token>, String> {
    let mut tokens = Vec::new();
    let mut chars = src.chars().peekable();
    while let Some(&c) = chars.peek() {
        match c {
            c if c.is_whitespace() => {
                chars.next();
            }
            '0'..='9' => {
                let mut n = 0i64;
                while let Some(d) = chars.peek().and_then(|d| d.to_digit(10)) {
                    n = n * 10 + d as i64;
                    chars.next();
                }
                tokens.push(Token::Number(n));
            }
            c if c.is_ascii_alphabetic() || c == '_' => {
                let mut word = String::new();
                while let Some(&d) = chars.peek() {
                    if d.is_ascii_alphanumeric() || d == '_' {
                        word.push(d);
                        chars.next();
                    } else {
                        break;
                    }
                }
                tokens.push(match word.as_str() {
                    "let" => Token::Let,
                    "print" => Token::Print,
                    _ => Token::Ident(word),
                });
            }
            '/' => {
                chars.next();
                if chars.peek() == Some(&'/') {
                    // line comment: skip to end of line
                    while chars.peek().is_some_and(|&d| d != '\n') {
                        chars.next();
                    }
                } else {
                    tokens.push(Token::Slash);
                }
            }
            _ => {
                chars.next();
                tokens.push(match c {
                    '+' => Token::Plus,
                    '-' => Token::Minus,
                    '*' => Token::Star,
                    '=' => Token::Equals,
                    '(' => Token::LParen,
                    ')' => Token::RParen,
                    ';' => Token::Semi,
                    _ => return Err(format!("unexpected character '{c}'")),
                });
            }
        }
    }
    Ok(tokens)
}

The only subtlety is /, which is either division or the start of a // comment — one peek disambiguates.

3. Parser: tokens to AST

Statements are trivial (they start with a keyword), so plain recursive descent handles them. Expressions need operator precedence, and the cleanest tool for that is Pratt-style precedence climbing: each operator gets a binding power, and a recursive expression(min_bp) only folds operators that bind at least that tightly. Create src/parser.rs:

use crate::lexer::Token;

#[derive(Debug)]
pub enum Expr {
    Number(i64),
    Var(String),
    Neg(Box<Expr>),
    Binary(char, Box<Expr>, Box<Expr>),
}

#[derive(Debug)]
pub enum Stmt {
    Let(String, Expr),
    Print(Expr),
}

pub fn parse(tokens: &[Token]) -> Result<Vec<Stmt>, String> {
    let mut parser = Parser { tokens, pos: 0 };
    let mut program = Vec::new();
    while parser.peek().is_some() {
        program.push(parser.statement()?);
    }
    Ok(program)
}

struct Parser<'a> {
    tokens: &'a [Token],
    pos: usize,
}

impl Parser<'_> {
    fn peek(&self) -> Option<&Token> {
        self.tokens.get(self.pos)
    }

    // Returns an owned Token so match arms can move its data (like the
    // ident String) straight into AST nodes without borrow juggling.
    fn next(&mut self) -> Option<Token> {
        let tok = self.tokens.get(self.pos).cloned();
        self.pos += 1;
        tok
    }

    fn expect(&mut self, want: Token) -> Result<(), String> {
        match self.next() {
            Some(tok) if tok == want => Ok(()),
            other => Err(format!("expected {want:?}, found {other:?}")),
        }
    }

    fn statement(&mut self) -> Result<Stmt, String> {
        match self.next() {
            Some(Token::Let) => {
                let name = match self.next() {
                    Some(Token::Ident(name)) => name,
                    other => return Err(format!("expected name after 'let', found {other:?}")),
                };
                self.expect(Token::Equals)?;
                let value = self.expression(0)?;
                self.expect(Token::Semi)?;
                Ok(Stmt::Let(name, value))
            }
            Some(Token::Print) => {
                let value = self.expression(0)?;
                self.expect(Token::Semi)?;
                Ok(Stmt::Print(value))
            }
            other => Err(format!("expected statement, found {other:?}")),
        }
    }

    // Pratt-style precedence climbing: only fold operators that bind
    // at least as tightly as `min_bp`.
    fn expression(&mut self, min_bp: u8) -> Result<Expr, String> {
        let mut lhs = match self.next() {
            Some(Token::Number(n)) => Expr::Number(n),
            Some(Token::Ident(name)) => Expr::Var(name),
            Some(Token::Minus) => Expr::Neg(Box::new(self.expression(5)?)),
            Some(Token::LParen) => {
                let inner = self.expression(0)?;
                self.expect(Token::RParen)?;
                inner
            }
            other => return Err(format!("expected expression, found {other:?}")),
        };
        loop {
            let (op, bp) = match self.peek() {
                Some(Token::Plus) => ('+', 1),
                Some(Token::Minus) => ('-', 1),
                Some(Token::Star) => ('*', 3),
                Some(Token::Slash) => ('/', 3),
                _ => break,
            };
            if bp < min_bp {
                break;
            }
            self.next();
            let rhs = self.expression(bp + 1)?; // +1 makes ops left-associative
            lhs = Expr::Binary(op, Box::new(lhs), Box::new(rhs));
        }
        Ok(lhs)
    }
}

* and / get binding power 3 versus 1 for + and -, so 7 + 3 * 2 parses as 7 + (3 * 2): after consuming 7, the loop folds + and recurses with min_bp = 2, which happily consumes 3 * 2 before returning. Unary minus recurses with power 5, binding tighter than everything. This single function replaces the grammar-per-precedence-level cascade (expr → term → factor) you may know from textbook recursive descent, and it scales to new operators by adding one line to the table.

4. Compiler: AST to bytecode

A post-order walk of the AST emits stack-machine code: compile the operands, then the operator. This works because the stack lines up naturally with expression nesting — 7 + 3 becomes Const(7), Const(3), Add: the two pushes leave operands on the stack, and Add pops both and pushes 10. Nested expressions compose for free; no registers to allocate.

Numbers go into a constant pool (real VMs do this to keep instructions small and to dedupe literals); variables get numbered global slots. Create src/compiler.rs:

use crate::parser::{Expr, Stmt};
use std::collections::HashMap;

#[derive(Debug, Clone, Copy)]
pub enum Op {
    Const(usize), // push consts[i]
    Load(usize),  // push globals[i]
    Store(usize), // pop into globals[i]
    Add,
    Sub,
    Mul,
    Div,
    Neg,
    Print,
}

pub struct Chunk {
    pub code: Vec<Op>,
    pub consts: Vec<i64>,
    pub num_globals: usize,
}

pub fn compile(program: &[Stmt]) -> Result<Chunk, String> {
    let mut c = Compiler {
        code: Vec::new(),
        consts: Vec::new(),
        globals: HashMap::new(),
    };
    for stmt in program {
        c.stmt(stmt)?;
    }
    Ok(Chunk {
        code: c.code,
        consts: c.consts,
        num_globals: c.globals.len(),
    })
}

struct Compiler {
    code: Vec<Op>,
    consts: Vec<i64>,
    globals: HashMap<String, usize>,
}

impl Compiler {
    fn stmt(&mut self, stmt: &Stmt) -> Result<(), String> {
        match stmt {
            Stmt::Let(name, value) => {
                self.expr(value)?;
                let next_slot = self.globals.len();
                let slot = *self.globals.entry(name.clone()).or_insert(next_slot);
                self.code.push(Op::Store(slot));
            }
            Stmt::Print(value) => {
                self.expr(value)?;
                self.code.push(Op::Print);
            }
        }
        Ok(())
    }

    fn expr(&mut self, expr: &Expr) -> Result<(), String> {
        match expr {
            Expr::Number(n) => {
                self.consts.push(*n);
                self.code.push(Op::Const(self.consts.len() - 1));
            }
            Expr::Var(name) => match self.globals.get(name) {
                Some(&slot) => self.code.push(Op::Load(slot)),
                None => return Err(format!("undefined variable '{name}'")),
            },
            Expr::Neg(inner) => {
                self.expr(inner)?;
                self.code.push(Op::Neg);
            }
            Expr::Binary(op, lhs, rhs) => {
                self.expr(lhs)?;
                self.expr(rhs)?;
                self.code.push(match op {
                    '+' => Op::Add,
                    '-' => Op::Sub,
                    '*' => Op::Mul,
                    _ => Op::Div,
                });
            }
        }
        Ok(())
    }
}

Resolving names to slot indices at compile time means the VM never touches a hash map — a real-world bytecode trick, and why this beats tree-walking interpretation.

5. VM: a stack machine

The VM is the classic fetch-decode-execute loop in miniature: ip (instruction pointer) indexes into the code, each op is decoded by a match, and all data flows through a value stack plus a flat globals array. Create src/vm.rs:

use crate::compiler::{Chunk, Op};

pub fn run(chunk: &Chunk) -> Result<(), String> {
    let mut stack: Vec<i64> = Vec::new();
    let mut globals = vec![0i64; chunk.num_globals];
    let mut ip = 0;
    while ip < chunk.code.len() {
        let op = chunk.code[ip];
        ip += 1;
        match op {
            Op::Const(i) => stack.push(chunk.consts[i]),
            Op::Load(slot) => stack.push(globals[slot]),
            Op::Store(slot) => globals[slot] = pop(&mut stack)?,
            Op::Neg => {
                let v = pop(&mut stack)?;
                stack.push(-v);
            }
            Op::Add | Op::Sub | Op::Mul | Op::Div => {
                let b = pop(&mut stack)?;
                let a = pop(&mut stack)?;
                stack.push(match op {
                    Op::Add => a.wrapping_add(b),
                    Op::Sub => a.wrapping_sub(b),
                    Op::Mul => a.wrapping_mul(b),
                    _ => {
                        if b == 0 {
                            return Err("division by zero".into());
                        }
                        a / b
                    }
                });
            }
            Op::Print => println!("{}", pop(&mut stack)?),
        }
    }
    Ok(())
}

fn pop(stack: &mut Vec<i64>) -> Result<i64, String> {
    stack.pop().ok_or_else(|| "stack underflow".into())
}

Wrapping arithmetic keeps overflow from panicking in debug builds; division by zero becomes a proper runtime error instead of a panic.

6. Wire up the driver

Replace src/main.rs — it chains the three phases and adds a --dump flag to inspect bytecode:

mod compiler;
mod lexer;
mod parser;
mod vm;

use std::{env, fs, process};

fn main() {
    let args: Vec<String> = env::args().collect();
    let Some(path) = args.get(1) else {
        eprintln!("usage: tinylang <file.tiny> [--dump]");
        process::exit(64);
    };
    let src = fs::read_to_string(path).unwrap_or_else(|e| {
        eprintln!("error reading {path}: {e}");
        process::exit(66);
    });
    let result = lexer::lex(&src)
        .and_then(|tokens| parser::parse(&tokens))
        .and_then(|ast| compiler::compile(&ast));
    let chunk = result.unwrap_or_else(|e| {
        eprintln!("compile error: {e}");
        process::exit(65);
    });
    if args.iter().any(|a| a == "--dump") {
        for (i, op) in chunk.code.iter().enumerate() {
            println!("{i:04} {op:?}");
        }
        return;
    }
    if let Err(e) = vm::run(&chunk) {
        eprintln!("runtime error: {e}");
        process::exit(70);
    }
}

Verify it works

cargo run --quiet -- examples/demo.tiny

Expected output:

120
2
88

Now look at what your compiler actually emitted:

cargo run --quiet -- examples/demo.tiny --dump

The first six ops (of 21) show let width = 12; and let height = 7 + 3; compiled down:

0000 Const(0)
0001 Store(0)
0002 Const(1)
0003 Const(2)
0004 Add
0005 Store(1)

If your numbers match, you've got a working compiler and VM.

Troubleshooting

• feature 'edition2024' is required when building — full text: error: failed to parse manifest at .../Cargo.toml … The package requires the Cargo feature called 'edition2024', but that feature is not stabilized in this version of Cargo. Your toolchain predates 1.85. Run rustup update stable, then rebuild.
• compile error: expected Semi, found None — a statement is missing its trailing ; (at end of file; mid-file you'll see the offending token instead, e.g. found Some(Print)). Every let and print needs a semicolon.
• compile error: undefined variable 'x' — you used a name before its let. Name resolution happens at compile time in Compiler::expr, so this is caught before the VM ever runs.
• runtime error: division by zero (exit code 70) — unlike the errors above, this one only surfaces at execution, because the divisor's value isn't known until the VM computes it. That split — resolve what you can at compile time, check the rest at runtime — is the same line every real language draws.

Next steps

Add booleans and comparison ops, then a Jump/JumpIfFalse pair — that's all if and while need, and it forces you into backpatching, the first genuinely tricky compiler technique. For the theory behind the expression parser, read Simple but Powerful Pratt Parsing. For the full journey — closures, GC, an object model — work through Crafting Interpreters, whose clox VM is the grown-up version of what you just built. And when you outgrow bytecode, Cranelift is the Rust-native path to emitting real machine code.