Learning How Compilers Work, And Getting Stuck
Tags: typescript, javascript, computerscience
Published: 2019-06-11 14:22:03

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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:

{% twitter 1131020431052247043 %}

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_:

{% github danistefanovic/build-your-own-x %}

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

{% github jamiebuilds/the-super-tiny-compiler %}

Which came from that fantastic article by [@mattsparks](https://dev.to/mattsparks):

{% link https://dev.to/mattsparks/learn-5-github-repos-with-great-free-open-source-resources-38de %}

## 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 SammyIsra/the-super-tiny-compiler %}

The first two steps were not so bad:
1. The first step (the [Tokenizer](https://the-super-tiny-compiler.glitch.me/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](https://the-super-tiny-compiler.glitch.me/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](https://the-super-tiny-compiler.glitch.me/traverser) and the [Transformer](https://the-super-tiny-compiler.glitch.me/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