Hey, I'm Tomek! 👋

For many who want to understand how compilers work, Crafting Interpreters by Robert Nystrom and Writing An Interpreter In Go (plus Writing A Compiler In Go) by Thorsten Ball are the go-to resources. I worked through both of them. I learned how tokenization works, what language grammars and EBNF notation are about. I built my first recursive descent parser and then brought the code to life by interpreting it directly (slow) and by implementing a bytecode compiler and a virtual machine (faster).

What these two books didn't teach me was how to translate source code to native machine code. Enter: QBE.

QBE is a compiler backend that aims to provide 70% of the performance of industrial optimizing compilers in 10% of the code. QBE fosters language innovation by offering a compact user-friendly and performant backend. The size limit constrains QBE to focus on the essential and prevents embarking on a never-ending path of diminishing returns.

I came up with a small project demonstrating how to go through all the steps necessary to transform source code into a native executable. Inventing yet another programming language would have been counterproductive. I would have spent my time fighting design decisions instead of focusing on what was important for me: code generation.

Arithmetic expressions were an obvious and simple problem to solve. But how to turn 2 + 2 * 2 into 6 instead of 8? I started by defining a grammar. The grammar told me what tokens I should expect and how to handle precedence rules. For example: multiplication and division should be performed before addition and subtraction.

I ended up with this:

Expression = Sum;
Sum = Product , { ( "+" | "-" ) , Product };
Product = Unary , { ( "*" | "/" ) , Unary };
Unary = ( ( "-" | "+" ) , Unary ) | Primary;
Primary = Number | "(" , Expression , ")";

What does it mean?

• the tokens are: numbers, operators (+, -, *, /) and parentheses to group expressions

• the precedence rules result from following the grammar rules top to bottom, from the loosest one to the tightest one:

  • Expression is a Sum (addition and subtraction)
  • Sum is a list of Product (multiplication and division)
  • Product is a list of Unary (negation)
  • Unary is either Primary or, when there is an operator, another Unary
  • Unary operations can be stacked: ----1 = 1
  • Primary is either a Number or a grouped Expression

Tokenizer

Based on the grammar, I implemented a tokenizer in Zig. I took inspiration from a real Zig tokenizer.

With a list of token tags:

pub const Tag = enum {
    invalid,
    eof,

    left_paren,
    right_paren,

    plus,
    minus,
    star,
    slash,

    number,
};

Note: invalid and eof are meta tags to know when to stop, either on invalid token or end of input.

The tokenizer became a simple state machine:

const TokenizerState = enum {
    start,
    number,
};

pub fn nextToken(self: *Tokenizer) Token {
    var result: Token = .{ .tag = .eof, .start = self.current_position, .end = undefined };

    state: switch (TokenizerState.start) {
        .start => switch (self.input[self.current_position]) {
            0 => {},
            ' ', '\t', '\n', '\r' => {
                self.current_position += 1;
                result.start = self.current_position;

                continue :state .start;
            },
            '0'...'9' => {
                result.tag = .number;
                self.current_position += 1;

                continue :state .number;
            },
            '+' => {
                result.tag = .plus;
                self.current_position += 1;
            },
            '-' => {
                result.tag = .minus;
                self.current_position += 1;
            },
            '*' => {
                result.tag = .star;
                self.current_position += 1;
            },
            '/' => {
                result.tag = .slash;
                self.current_position += 1;
            },
            '(' => {
                result.tag = .left_paren;
                self.current_position += 1;
            },
            ')' => {
                result.tag = .right_paren;
                self.current_position += 1;
            },
            else => {
                result.tag = .invalid;
                self.current_position += 1;
            },
        },
        .number => switch (self.input[self.current_position]) {
            '0'...'9' => {
                self.current_position += 1;

                continue :state .number;
            },
            else => {},
        },
    }
    result.end = self.current_position;

    return result;
}

(see: full source code).

Parser

Then, I created a parser to build the Abstract Syntax Tree from the list of tokens. The Sum, Product and Unary from the grammar became binary and unary operations:

const BinaryOp = enum {
    add,
    sub,
    mul,
    div,
};

const UnaryOp = enum {
    neg,
};

pub const AstNode = union(enum) {
    binary: struct {
        lhs: *AstNode,
        op: BinaryOp,
        rhs: *AstNode,
    },
    unary: struct {
        op: UnaryOp,
        rhs: *AstNode,
    },
    number: i64,
};

(see: full source code).

Interpreter

After reading the books, interpreting the AST directly was straightforward:

pub const Interpreter = struct {
    pub fn interpret(ast: Ast) !i64 {
        return eval(ast.root);
    }

    fn eval(node: *const AstNode) !i64 {
        return switch (node.*) {
            .binary => |b| switch (b.op) {
                .add => try eval(b.lhs) + try eval(b.rhs),
                .sub => try eval(b.lhs) - try eval(b.rhs),
                .mul => try eval(b.lhs) * try eval(b.rhs),
                .div => try std.math.divTrunc(i64, try eval(b.lhs), try eval(b.rhs)),
            },
            .unary => |b| switch (b.op) {
                .neg => -try eval(b.rhs),
            },
            .number => |value| value,
        };
    }
};

(see: full source code).

Emitter

It was time for the fun part. First, I built a QBE intermediate language code emitter. The official documentation was an invaluable resource. My add, sub, mul, div and neg operations mapped directly to QBE instructions:

# add 64-bit 2 to 2 and store the result in a temporary %result
%result =l add 2, 2

Same applied to all other instructions.

In QBE, the intermediate language is in static single-assignment form. That meant I needed to emit a QBE instruction for all my binary and unary operations and stack them together. There was no point in emitting an instruction for, for example, +4 as it was the same as 4.

For a 2 + 2 * 2 expression that was:

# ld means: as long integer
data $fmt = { b "%ld\n", b 0 }
export function w $main() {
@start
    %.0 =l mul 2, 2
    %.1 =l add 2, %.0
    # call C printf function, needs linking with libc, to print the result
    call $printf(l $fmt, ..., l %.1)
    ret 0
}

For -2 + 2 * (4 / 2) that was:

data $fmt = { b "%ld\n", b 0 }
export function w $main() {
@start
    %.0 =l neg 2
    %.1 =l div 4, 2
    %.2 =l mul 2, %.1
    %.3 =l add %.0, %.2
    call $printf(l $fmt, ..., l %.3)
    ret 0
}

(see: full source code).

Compiler

The last piece needed was tying everything together and generating a native executable. I decided to divide the compiler into three stages:

• Qbe:

  • tokenizing
  • parsing
  • emitting QBE SSA
  • using qbe executable to produce a raw assembly file

• Cc: compiling the assemibly into an executable. Since I implemented everything in Zig, it was natural to just invoke zig cc

• Run: running the executable and outputting the result.

From start to finish it was just:

$ oc "2 + 2 * 2"
6

I decided to leave all build artifacts for manual inspection.

target/result.ssa contains the QBE IL:

data $fmt = { b "%ld\n", b 0 }
export function w $main() {
@start
    %.0 =l mul 2, 2
    %.1 =l add 2, %.0
    call $printf(l $fmt, ..., l %.1)
    ret 0
}

target/result.s contains the assemply generated by qbe -o result.s result.ssa:

.data
.balign 8
fmt:
        .ascii "%ld\n"
        .byte 0
/* end data */

.text
.balign 16
.globl main
main:
        endbr64
        pushq %rbp
        movq %rsp, %rbp
        movl $6, %esi
        leaq fmt(%rip), %rdi
        movl $0, %eax
        callq printf
        movl $0, %eax
        leave
        ret
.type main, @function
.size main, .-main
/* end function main */

.section .note.GNU-stack,"",@progbits

There was one interesting thing I have observed. As QBE is an optimizing compiler backend, it folded all the constants and returned the result directly: movl $6, %esi.

With division present (-2 + 2 * (4 / 2)), it didn't happen, though:

.data
.balign 8
fmt:
        .ascii "%ld\n"
        .byte 0
/* end data */

.text
.balign 16
.globl main
main:
        endbr64
        pushq %rbp
        movq %rsp, %rbp
        movl $2, %ecx
        movl $4, %eax
        cqto
        idivq %rcx
        imulq $2, %rax, %rax
        movq %rax, %rsi
        addq $-2, %rsi
        leaq fmt(%rip), %rdi
        movl $0, %eax
        callq printf
        movl $0, %eax
        leave
        ret
.type main, @function
.size main, .-main
/* end function main */

.section .note.GNU-stack,"",@progbits

Closing thoughts

The full source code is available here. qbe and zig packages are needed to build and run it. On Alpine Linux it's as easy as:

$ apk add qbe zig

The project is in a fairly complete state. It may be rough around the edges: more tests would be nice and better error handling, especially around overflows and division by 0.