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:
Expressionis aSum(addition and subtraction)Sumis a list ofProduct(multiplication and division)Productis a list ofUnary(negation)Unaryis eitherPrimaryor, when there is an operator, anotherUnaryUnaryoperations can be stacked:----1=1Primaryis either aNumberor a groupedExpression
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, 2Same 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
qbeexecutable to produce a raw assembly file
-
Cc: compiling the assemibly into an executable. Since I implemented everything in Zig, it was natural to just invokezig cc -
Run: running the executable and outputting the result.
From start to finish it was just:
$ oc "2 + 2 * 2"
6I 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,"",@progbitsThere 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,"",@progbitsClosing 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 zigThe 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.
I write, words and code, by hand.
0 Comments
Log in to join the conversation.No comments yet. Be the first to share your thoughts.