Compilers are magic. This is probably one of the most repeated statements to beginners who are just starting to learn. You take your 1kB C-File, run something along the lines of gcc hello_world.c -o hello_world.exe, and whoosh, you get a several hundred kB large executable file that runs just like that on your computer. Or you have it even easier, you write your program in an IDE, click the run button, and don't ever have to look at any executable at all! Don't get me wrong, the fact that programming is this accessible to beginners nowadays is nothing short of amazing. Imagine if we all still had to manually compile and link our React frontends or Django backends. We would all still be using internet explorer! But, I believe taking a step back and examing what is going on under hood, and maybe even dabbling in it yourself, can be an extremely beneficial challenge for almost every programmer.

I was one of those people that classified compilers as fancy space magic for the longest time. Especially because I was used to those fancy IDEs that did all the work for me. This changed when I became interested in reverse engineering & assembly. The reason for this was this video:

A very dedicated member of the "Guitar Hero" community reverse engineers the game to fix a particularly annoying bug. The way he effortlessly navigates through the assembly code to map out the entire game's codebase was incredibly fascinating to me. He uses a tool called "IDA64" to disassemble the game, as well as a debugger to step through the code. As is common when you first try to learn a new skill, you immediately jump into the deep end and try to run when you can't even walk yet, making it that you end up learning nothing at all and just being frustrated. After trying a couple CTF reverse-engineer challenges I was entirely lost, didn't know what I was doing and quit. But that initial fascination was still there.

After some time, I discovered a CTF website called "CTFLearn", which seemed to be specifically aimed at beginners. Perfect! And there I found the ultimate introduction to reverse engineering, a series of CTFs created by a user called "kcbowhunter". It starts off with some simple assembly coding but quickly transitions to tricky reverse engineering problems. Long story short, I learned assembly. Cool. Now what? Well, I had understood a major part of how programs actually work. This would be extremely useful later.

The actual inspiration for writing my own compiler came during my time at university, where we – well – wrote our own compiler. It was a relatively simple one, written in Java for a small subset of the C language. It was actually one of six projects in that course, and you had three weeks to finish it (!). I learned what a lexer, a parser and a code emitter are and what they do. I was actually one of the few people that managed to complete the project in its entirety, which I am still quite proud of. And I believe that is in large part because I was already familiar with assembly beforehand. But, wait a minute, 3 weeks? That's basically nothing in the programming world. Not only that, but this was not a group project. Turns out, a lot of steps in writing a compiler are surprisingly intuitive.

In the beginning, your program is just a string of text, with no meaning at all.

The lexer, the first component of basically every compiler, takes this text and splits it into a list of tokens. Each language has their own tokens, but they roughly overlap. A program like "int main() { return 0; }" would be split into the tokens TYPE[int], IDENTIFIER[main], LP[(], RP[)], LC[{], RETURN[return], NUMBER[0], SC[;], RC[}], EOF[EOF]. But how does the lexer differentiate, say, a type name and an identifier or a keyword? Well, our language has a list of reserved words, such as "if" and "return", that the lexer tries to match any character sequence with. If it fails, it tries to match an identifier. If that also fails, it matches a type name, and so on, until it runs out and throws an error. The lexer in my programming language "lowercase" is only around 300 lines long. Most lexers also operate in a very similar way, so finding resources is incredibly easy.

The parser, the second component, takes the list of tokens our lexer generated and turns them into a structure called an "abstract syntax tree" (AST). You can imagine this tree as follows: The very top of the tree is the root, basically our entire program. One level below that are our top-level definitions, such as global variables, types, and functions. Let's just use functions for simplicity. A function declaration has a return type, a name, a list of parameters and a body. This body is a list of statements, each of which can then also have statements and expressions within them. The parser creates this tree by reading a token and then and then checking if the following tokens make sense. For instance, in lowercase, if I have the token "TYPE[TYPE]", the parser expects the next token to be an identifier that names this type. The "abstract" in AST comes from the fact that the parser removes the "literal" tokens, such as "TYPE" and "IDENTIFIER", and replaces them with nodes that represent the meaning of these tokens.

The code emitter, the third and final component, takes the AST and turns it into machine code. This is the most complex part of the compiler, but also the most rewarding. The code emitter has to take the AST and turn it into a list of instructions that the CPU can execute. This is done by traversing the AST and emitting instructions for each node. For instance, if we have a node that represents a function call, the code emitter has to emit the instructions to put the arguments on the stack, call the function, and then clean up the stack. This is a very simplified example, but you get the idea. Each expression/statement has its own method that emits the instructions for it. But again, most of them are surprisingly easy to understand and actually quite short.

So in conclusion, compilers are easier to understand than you might think. Once you get the theory and the steps that are involved, the practical implementation can be done by virtually any programmer. And the benefits are clear: You gain an intuition of what actually happens under the hood when you write & compile your code every day. I don't like working with black boxes, or tools that I don't understand. So lifting the veil on compilers is a very rewarding experience. You should try it too!