loading...

Learning How Compilers Work, And Getting Stuck

sammyisa profile image Sammy Israwi Updated on ・4 min read

Notes:

  • This article is less of an instructional one, like previous articles, and more of a question + fun narration of my struggles with compilers so far. More instructional articles will come later on.
  • This is about compilers only, not about Interpreters. I have no idea how interpreters work yet.

The Background

Out of all the classes one takes as a CS student in university, some useless and some not so much, it might come to you as a surprise that I actually enjoyed the classes about programming languages and system software - it was certainly a surprise to me because I had no idea I had an interest in them!

Particularly, I was interested in learning how languages worked. All I knew beforehand is that programming languages are translated to machine code so that the computer understands what to do, because the computer doesn't understand JSFuck. However, I had no idea how we go from human-readable programming language to machine-language, I thought of it for a while as translating Spanish to English. After I learned that was not the case, I simply thought of it being a black box of computer science magic and didn't push the subject.

The Systems Software class at my university taught us a bit more about what was inside the black-box, they had us build a compiler for a simplified version of language called PL/0. It was the second time I took the class when it actually clicked for me and started being interesting, I can thank the professor for that. It was in said class where I learned about the steps of compiling a language (parser, analyzer, all that jazz) what an Abstract Syntax Tree (AST) was and how it was an intermediary step of compiling and a very powerful tool when understanding how a language works, and how a computer can understand it.

All that backstory to bring you to this Tweet:

Which came right at a time when I wanted to delve deeper into developer experience tools. At the same time, as if by divine timing, my brother shared with me this repo about learning to build your own anything:

Which links to this repo about building your own compiler in JavaScript:

GitHub logo jamiebuilds / the-super-tiny-compiler

⛄ Possibly the smallest compiler ever

The Super Tiny Compiler

Welcome to The Super Tiny Compiler!

This is an ultra-simplified example of all the major pieces of a modern compiler written in easy to read JavaScript.

Reading through the guided code will help you learn about how most compilers work from end to end.

Want to jump into the code? Click here

You can also check it out on Glitch


Why should I care?

That's fair, most people don't really have to think about compilers in their day jobs. However, compilers are all around you, tons of the tools you use are based on concepts borrowed from compilers.

But compilers are scary!

Yes, they are. But that's our fault (the people who write compilers), we've taken something that is reasonably straightforward and made it so scary that most think of it as this totally unapproachable thing that only the nerdiest of the nerds are able to understand.

Okay so where

Which came from that fantastic article by @mattsparks:

The Current Situation

So, I started going over the Super Tiny Compiler to understand how it works, and converting it to TypeScript to prove to myself that I understand what is happening in the different stages of the compiler.

I have been doing just that in a repository is a fork of the previously mentioned one, and you can find it here:

GitHub logo SammyIsra / the-super-tiny-compiler

⛄ Possibly the smallest compiler ever

My first attempt (out of school) to learn how compilers work, and what tf an AST is

This version will be in TypeScript mostly because that is a good way for me to properly understand how it works

Original README below this line

The Super Tiny Compiler

Welcome to The Super Tiny Compiler!

This is an ultra-simplified example of all the major pieces of a modern compiler written in easy to read JavaScript.

Reading through the guided code will help you learn about how most compilers work from end to end.

Want to jump into the code? Click here

You can also check it out on Glitch


Why should I care?

That's fair, most people don't really have to think about compilers in their day jobs. However, compilers are all around you, tons of the tools you use are based on concepts borrowed from compilers.

But compilers are scary!

Yes, they are. But that's…

The first two steps were not so bad:

  1. The first step (the Tokenizer) turns the input string in the starting language to a series of tokens, each token identified as a Parenthesis, Number, String, or Name.
  2. The second step (the Parser) navigates the token list and creates a simple AST by analyzing the token list and determining what kind of node each token is and if the following ones are children nodes.

I'll go into a deeper discussion on the matter in more instructional articles, and they will come with drawings since that is how I first understood these topics.

The Blocker

Steps #3 and #4 (the Traverser and the Transformer) is where I am currently stuck at. These steps seem to live together in the sense that they perform the next step in the compiling process.

However, I am at a loss when trying to understand how we get the simple AST from step 2 and turn it into the more complicated one that the Code Generation step can use to create the compiler output, and how to turn that knowledge into the Types created by said steps.

The way I understand this section of the compiler is that the Transformer takes in the Traverser and the Simple AST, creates a "visitor" which dictates what happens when finding a node of a specific type in the Simple AST, and it outputs the New AST (as is referred to in the code), which is the input the Code Generation step uses to create the output code.

So this is where I lay my question and my request for help, the Traverser and the Transformer steps of the compiler are not the clearest subjects for me, so if you have any knowledge about them or if you have a similar experience to mine, I'd love to hear about it.


Quick note. After writing this article, I have since found this video from the same author: https://www.youtube.com/watch?v=Tar4WgAfMr4

Discussion

pic
Editor guide