Tomek Wałkuski

For many who want to understand how compilers work, Crafting Interpreters by Robert Nystrom<br>and Writing An Interpreter In Go (plus Writing A Compiler In Go)<br>by Thorsten Ball are the go-to resources. I worked through both of them. I learned how tokenization works,<br>what language grammars and EBNF notation are about.<br>I built my first recursive descent parser and then brought the code to life<br>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.<br>QBE fosters language innovation by offering a compact user-friendly and performant backend. The size limit constrains QBE to focus<br>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.<br>Inventing yet another programming language would have been counterproductive. I would have spent my time fighting design decisions instead of<br>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.<br>The grammar told me what tokens I should expect and how to handle precedence rules. For example: multiplication and division should be performed<br>before addition and subtraction.

I ended up with this:

Expression = Sum;<br>Sum = Product , { ( "+" | "-" ) , Product };<br>Product = Unary , { ( "*" | "/" ) , Unary };<br>Unary = ( ( "-" | "+" ) , Unary ) | Primary;<br>Primary = Number | "(" , Expression , ")";<br>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.<br>I took inspiration from a real Zig tokenizer.

With a list of token tags:

pub const Tag = enum {<br>invalid,<br>eof,

left_paren,<br>right_paren,

plus,<br>minus,<br>star,<br>slash,

number,<br>};<br>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 {<br>start,<br>number,<br>};

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

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

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

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

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

return result;<br>(see: full source code).

Parser

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

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

const UnaryOp = enum {<br>neg,<br>};

pub const AstNode = union(enum) {<br>binary: struct {<br>lhs: *AstNode,<br>op: BinaryOp,<br>rhs: *AstNode,<br>},<br>unary: struct {<br>op: UnaryOp,<br>rhs: *AstNode,<br>},<br>number: i64,<br>};<br>(see: full source code).

Interpreter

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

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

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

Emitter

It was time for the...