Learning How Compilers Work, And Getting Stuck

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:

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:

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