Archive | December 2015

Compiler From Simple Language to x86 in Erlang

GitHub Link for Project.

Recently I decided to learn both Erlang and x86 assembly. I needed both technologies for a thing unrelated to the project in this post.

I decided that a cool thing to do was to make a compiler from a toy programming language to x86. I like compilers, and writing a compiler in Erlang proved to be a simple task. Simpler then other projects I’ve made in C and C++.

The Compiled Language

I didn’t really put much effort into coming up with any original language. I just needed a simple language that allowed me to make some calculations. Because this project wasn’t focus on compiler design but rather in learning Erlang and x86, I decided that the language would only have one data type, integers, and very few other features. The final result is a language that looks like this:

# Initialize the numbers to calculate the sequence
n1 = 1;
n2 = 1;
i = 0;

while i < 10 [
    # Display the value of n2
    n2;

    # Get next number
    t = n1;
    n1 = n2;
    n2 = n2 + t;

    i = i + 1;
]

That is the implementation for the Fibonacci sequence. The first few lines initialize the two variables to calculate the numbers in the sequence and a index i.

Inside the cycle, the value of n2 will be displayed, the next number is calculated, and i is incremented.

In this language functions look like this:

# A function is identified by its name and arguments number
def f(x): x*2;
def f(x, y): x*y;

f(10);
f(10, 20);

def f(x): x*5; # Redefines f with 1 argument

f(10);

They are identified by their name and the number of arguments, so f(x) and f(x, y) are different. Functions can also be redefined, like in the example, f(x) is redefined.

The language is simple, and I changed it a lot as I developed this compiler. But like I said, the objective was simply to have something to develop a compiler for.

Erlang

I have a lot of experience with the lesser known Prolog. Prolog is an amazing language for many things, but not really used in many places. On the other hand, I actually know a lot a Haskell, but I don’t really like it for many reasons (which I won’t discuss now).

For me, Erlang is like taking the best of Prolog and the best of Haskell and joining those things into one language. Because of that, learning Erlang was not only easy but also enjoyable.

A great things about Erlang is its parallel computing capabilities. Sadly, this project doesn’t take advantage of any of that, so I won’t discuss it further.

x86

While in college I learned the MIPS instruction set. I’ve developed a few considerable projects in MIPS that run in the Mars simulator. I’ve also studied the pipeline implementation for some MIPS processors, and developed a compiler that compiled to MIPS (from a language that was more complex then the one in this project).

Learning x86 didn’t take long because of my previous knowledge of MIPS. The instructions change, the registers also change, but many conventions are the same, or they follow similar ideas.

The Compiler

This project is just a small personal project. As such I didn’t really was much time in testing, documenting, distribution, etc. But I got it working fine.

The implementation uses two Erlang tools to build the scanner and parser. They are leex and yeec, respectively. They are similar to Flex and Bison for C. The rest is just Erlang.