RusTiny: I’m Writing a Compiler! March 12, 2015
Writing a compiler is pretty cool. People even recommend that every programmer should at least try that. However, though I wanted to write a compiler for quite some time now, I just didn’t know where to start. But after finishing my last article on the fictional Tiny architecture, it felt the next step after writing an assembler and a virtual machine is a compiler that targets the Tiny architecture. In other words: I’m writing a compiler now!
Divide et Impera
Compilers are very complex stuff, but they can be split up into manageable parts. There also are single-pass compilers which usually don’t have an IR and combine all steps into one pass.In general, these are:
- Parse the source file into an Abstract Syntax Tree
- Validate the AST (e.g. type checking)
- Transform the AST into an Intermediate Representation
- Optimize the IR
- Transform the IR into machine code
For my compiler I’ve decided to follow the micro-pass approach where each step is made up of several compiler passes. I hope this will allow me to keep the complexity on a manageable level. Will it work out on the first try? That only time will show.
For the source language, I’ve made up RusTiny. It’s based on Rust, but very slimmed down. To simplify matters, RusTiny’s only datatypes are
bools. There are no structs, no modules, no concept of ownership and mutability and no type inference. Once I’ve got this simplified version done, I might add some of the missing features.
As mentioned before, the will emit Tiny assembler. I’m not sure whether Tiny is powerful enough to support RusTiny, but if it fails I’ll propably fall back to simple x86 assembler.
Watch it grow
If you want to have a look at my compiler, check out its GitHub project. I’m trying to keep the source lovingly commented so you don’t need a background in compiler writing to understand it. If you have questions or feedback about it, feel free to open an issue.
These resources helped me getting started with my compiler:
- Programmers Stack Exchange: How to write a very basic compiler: A great overview how to write a compiler along with several helpful tips.
- Torben Ægidius Mogensen: Basics of Compiler Design: A textbook for an undergraduate compilers course. Presents the topics in a clear and succinct way.