Choosing a Small Rust Subset

I wrote about the compiler books and the years of curiosity behind this project in the introduction. The first practical decision is what our compiler should accept.

I want to be able to check our compiler's examples with another compiler. That's the reason for choosing Rust syntax. A teaching language with print, perhaps begin and end, would give us more freedom, but we'd have to define everything ourselves, even what an expression like 1 + 2 * 3 means.

MicroRust will accept a small subset of Rust. We can feed the examples to rustc from the start, then gradually teach our compiler to handle them too. Having that reference is useful: we can compare the results while watching how much work our little implementation leaves out.

Why this phase matters

Before writing the lexer, we need to agree on what counts as valid input. Which Rust features will we support? What behavior should readers expect from an accepted program? Lifetimes can wait; even our few arithmetic operators need consistent rules.

Production compilers work within a language specification and a long history of compatibility decisions. Our contract can be much smaller, but it still needs to be clear. Otherwise, we end up with a parser that builds nodes the type checker can't handle, or a backend asked to compile a feature we never intended to support. Defining the subset now saves us from making a different decision in every phase.

What we are building here

MicroRust will compile a narrow subset of Rust:

• integer literals
• identifiers
• let bindings with explicit i32 annotations
• fn definitions
• function calls
• block expressions, including an optional final value
• return
• arithmetic operators: +, -, *, /
• the type i32
• a main function
• the exact output form println!("{}", value), recognised specially and lowered to a runtime helper

This gives us enough to follow a program through the whole compiler. We'll use this one throughout the series:

fn add(a: i32, b: i32) -> i32 {
    return a + b;
}

fn main() {
    let x: i32 = 5 + 3;
    let y: i32 = x * 2;
    let result: i32 = add(x, y);
    println!("{}", result);
}

Save this as golden.mrs inside the microrust folder described below. It is short enough to follow through each phase without losing track of the source. The .mrs suffix tells us that this is input for MicroRust; our compiler's own Rust code will stay in main.rs.

The suffix doesn't change the language. From the folder containing golden.mrs, run rustc -C overflow-checks=yes --crate-name golden golden.mrs -o golden-rust, then ./golden-rust. It should print 24. The explicit crate name keeps that choice independent of the input filename. We won't need to rename the input to compare the two compilers.

The awkward part is println!. In Rust, println! is a macro, not a normal function, and we're leaving macro expansion out of MicroRust. We'll recognize this particular output form in the frontend and discuss a runtime helper when we reach the backend. That keeps the example valid Rust without requiring a macro implementation before we can print an integer.

Building one compiler

Create one folder called microrust and keep working in it through the series. The compiler will grow in main.rs, and we'll build it with rustc main.rs -o microrustc. The name microrustc belongs to the executable we are building. rustc builds that executable for us.

The lexer chapter starts the file. The parser chapter keeps the lexer and adds a tree and the code that constructs it. Name resolution will walk that same tree, and type checking will use the bindings we found. Lowering then takes the checked program into IR; optimization and code generation continue from there. We'll keep those components in inline Rust modules within main.rs, so their boundaries are visible without making the reader assemble a collection of separate projects.

Each implementation chapter, from the lexer through linking, ends with a complete version of this one file. Replace the old main.rs with the next listing, or work through the additions yourself and use the full listing to check your work. Keep your input files beside it. A short example.mrs helps us inspect the lexer and parser; from name resolution onward it holds our canonical program. You can keep golden.mrs as an unchanged copy for comparison.

Early versions of microrustc will only show tokens or an AST. As we add phases, the driver will pass their results forward until it can generate native code. The assembler and linker will finish that build with a small C runtime. We won't write an assembler inside main.rs.

There is also a separate, modular companion implementation used to check the short excerpts in these articles. Its files such as src/syntax.rs are authoring references, not extra files the reader needs to create. The complete listings contain those components as inline modules. The final version also carries its C runtime as a string, so there is no separate runtime source file to collect.

Why Rust, but smaller

Rust is getting a lot of attention, and that made it an appealing choice for this exercise. We could just as well have started with a small subset of C, Java or another established language. I want to use the series to understand the work a compiler does between reading a source file and producing an executable.

Designing a new language would give us another set of questions to settle before we got to that work. We'd have to choose the syntax and define what each construct means. With Rust, we can borrow those decisions and concentrate on implementing them. There's also a working compiler to compare with when our own results look wrong.

Implementing all of Rust would be far beyond this series. Our few integer expressions, bindings and function calls still need to pass through every stage of the compiler we're building. Keeping the language small lets us inspect those stages in detail, then return to rustc with more specific questions about the parts we've left out.

Compilation steps

Our compiler will have the usual pipeline, but each stage will be built small enough to fit in your head.

Source text becomes tokens. Tokens become an abstract syntax tree. The tree is checked for names and types. The checked tree lowers into an intermediate representation, or IR, which is a simpler compiler-owned language. The IR gets cleaned up by a few optimization passes. Then code generation turns it into actual x86-64 assembly. After that we discuss object files, relocation, and linking, because "the compiler produced assembly" is not the same as "the operating system can run it."

That rough shape appears in many compilers. A C compiler, a Java compiler, a JavaScript engine, a Python bytecode compiler, and rustc all make different choices, but they all need to cross the gap between human-facing syntax and machine-facing execution.

The diagram below shows where those stages belong. Everything inside the dashed boundary is part of the microrustc we're building in main.rs. Each phase passes its result to the next. The assembler and linker are tools our driver will call after it has produced assembly.

The runtime.o input is the small C runtime we'll write later. It supplies the printing helper that our generated code calls.

rustc has considerably more between these steps: macro expansion, name resolution across modules and crates, HIR, type inference, trait solving, borrow checking, MIR, monomorphization, LLVM IR, and extensive diagnostic machinery. We'll return to those in the final post. By then, the comparison with rustc should be easier to make in terms of specific implementation problems.

The implementation style

We'll write a hand-written scanner and a recursive descent parser for items and statements, using Pratt parsing for expressions. The parser follows the grammar's structure, with precedence guiding arithmetic and calls. Later phases will work on an AST rather than a full parse tree. A symbol table and scope stack will handle names; type checking starts with i32 and function signatures. For IR, we'll use three-address code with temporaries and simple instructions. These choices keep the implementation small enough to follow directly.

One choice is to compile all the way to native code. An interpreter could evaluate 5 + 3 by walking the AST and adding the numbers in Rust. Here we'll preserve the expression's meaning through several representations until we can emit machine instructions for it.

Following the same program makes those changes easier to track. Tokens become a tree, name resolution identifies bindings, and type checking annotates expressions. Lowering then flattens the syntax into temporaries, which eventually occupy stack slots or registers. By the time the linker finishes, the original add(x, y) has passed through symbol references and relocations to become a call instruction with a target. Keeping the source familiar lets us concentrate on what each transformation does.

Limitations

The aim is for successful MicroRust programs to be valid Rust. MicroRust may reject almost all valid Rust, but it should not accept fake Rust just because it is convenient.

We'll explain special cases such as println! where we introduce them, so you can tell which behavior comes from Rust and which is a shortcut in our implementation.

It also helps to explain why each phase needs its data structures and rules. The scope rules matter as much as the dictionary in a symbol table. Relocations and calling conventions become necessary when separately compiled code has to agree on addresses and argument locations.

There are a few practical boundaries to record. Identifiers are ASCII, comments use //, and decimal integer literals are unsuffixed and lie between zero and 2147483647. Negative values can be computed with subtraction; unary minus is outside the parser. Each function takes at most six i32 parameters. Locals are immutable, though a new binding may shadow an old one. A block's final expression supplies its value, while a semicolon discards that value.

Arithmetic is checked: overflow, division by zero, and i32::MIN / -1 stop execution. We compare successful runs with rustc -C overflow-checks=yes. Our runtime does not reproduce Rust's panic machinery or exact diagnostics, and our frontend does not implement all of Rust's constant-arithmetic lints. A literal overflow example may therefore be rejected earlier by rustc. This is a useful limit to keep visible, rather than treating syntax compatibility as a promise of identical behaviour in every case.

The native target is x86-64 System V. The emitter supports Linux's ELF conventions and macOS's x86-64 Mach-O conventions; on Apple Silicon, native execution needs Rosetta. The portable IR runner needs neither. We compile one source file at a time and link a C runtime, not separate MicroRust modules.

The subset also keeps the work manageable. Adding if would bring in booleans and comparisons; while would make control flow and return checking more involved. Strings need runtime support and a layout, while structs need field access and memory layout. Ownership would expand the project considerably. We'll discuss those features where they explain a design choice, but keep them outside the implementation in this series.

What we can do now

We haven't compiled anything yet. We have a language boundary and a sample program to test against, including an explicit decision about the output macro. Most of Rust remains the responsibility of rustc.

The next step starts with the source file. We need to turn its text into tokens, distinguishing return the keyword from result the identifier and keeping track of where each occurred. We'll write that scanner in the tokenizer chapter.