My Experience in Compiler Design Learning

One of the most interesting computer science topics for me is programming languages. Sometimes I find myself just researching different languages' capabilities: their type systems, syntax, and toolchains. I enjoyed almost everything: pure functional languages like Haskell, F#, or Idris; classic OOP languages like C# or C++; or procedural ones like C or Go.

Every language brings us a new software design philosophy: some embrace strong immutability as a core feature, some propagate explicit and understandable control flow, and some aim for simplicity and developer ergonomics over abstraction.

But languages by themselves can't do anything on their own: all of them require software that translates programmers' intentions into an instruction set that is understandable to machines. Compilers and interpreters are examples of this software, and their implementation became the next stage of my interest in programming languages.

I started reading a lot of materials and watching videos about this topic with the goal of writing a simple compiler. I made many attempts to write compilers for different languages, and all of them failed.

But then I found an interesting book on the Internet: Writing a C Compiler: Build a Real Programming Language from Scratch by Nora Sandler. This book's material finally gave me a good understanding of the practical implementation of compilers. Thanks to this book, I implemented a simple compiler for a subset of the C language: ATCC.

This compiler is still a work in progress, but at least now I have an understanding of the direction in which people who want to learn compilers should move.

In this article, I will focus suggestion for newcomers like me.

Choice of programming language, that should be compiled

The worst idea is trying to design your own language, because compiler design and programming language design are two different disciplines. When you design a new language, you have to take many factors into account, such as the type system and parsing. As a newcomer, you usually don’t yet have enough knowledge to design a good language. The second reason is the temptation to adopt a dangerous mindset: when the compiler returns an unexpected result, nothing stops you from treating new behavior as a feature rather than a bug. After all, this is your language. Your language has no explicit, accurate specification, so you have no reference compiler to compare your results against.

The second bad idea is to choose so-called "toy languages" like Pinky or COOL. Although they have some specification, documentation for these languages is extremely limited. If you don't know how a program should behave in some edge case, you may need to inspect the implementation of their reference compiler.

The best languages to write a compiler for are those that have a production-ready compiler, a strong community, and good documentation. In her book, Nora Sandler suggests C, and this choice is very good: C is quite simple, has a ton of related materials, and has multiple mature compilers.

You can pick any language: if it is too complex, you can just pick a subset. For example, if you like Zig, you can cut features like compile-time code evaluation, type parameters, SIMD types like @Vector and other hard things.

Correct Development Order

Most compiler theory educators present material in a specific order:

Lexing
Parsing
Semantic analysis
Three-address code
Optimization
Assembly/binary code generation

Although this order looks natural (it reflects the compilation pipeline at runtime), this is not the order in which you should develop your compiler modules.

When I developed a compiler for the COOL language, I gave up at the TAC generation step because it was too complex and unintuitive. Although the COOL language is quite small, its parse tree became complex enough that when I tried to move to the next TAC generation step, I did not know where to start. The problem is that each previous step produces output that is too complex to be processed easily by the next step.

The book I mentioned above suggests a different perspective: you should shift your mindset from compilation pipeline stages to language features.

You start with a minimal language that can only return numeric values and nothing more, but you still write the entire compilation pipeline for this language (it is fine if your code is not perfect):

int main() {
    return 126;
}

Next, you add unary operators to your language:

int main() {
    return -53;
}

The next step is to add support for binary operators (with proper precedence):

int main() {
    return -126 + 21;
}

Your steps become smaller, but after each step you can refine your codebase through refactoring. It is easier to test your code because you better understand what you changed during the current step. This approach is also more friendly to version control systems, because you can work in pair with friend, if both of you work with different features of same compiler.

Tests, tests, tests

Always test your code! You should have strict acceptance criteria for each feature. Many language features have non-obvious behavior.

Did you know that this C code is valid?

int main() {
    int x = 2;

    switch (4) {
        int x = 3;

        case 3: {
            case 1:
                return 23;

            for (int i = -3; i < 5; i++) {
                default:
                    return 42;
            }
        }
        case 2: {
            return 21;
        }
    }

    return 0;
}

So, try to find an existing test suite for your language, or write your own tests, and cover as many edge cases of each feature as you can.

Compiler backends

Try to write your own compiler backend instead of using existing solutions like LLVM or GCC. Although these solutions are very solid, production-ready, and battle-tested, using them as a newcomer may cause you to skip very important areas of compiler construction, such as TAC optimization and assembly code generation.

Use Git branches

Let every new feature have its own branch in your repository. For example, in ATCC, besides my primary master branch, I also have branches like book/01_minimal_compiler, book/02_unary_operators, etc. This allows me to see the development process and use the differences between branches as a guide for feature implementation. Every major refactoring step also has a separate branch.

I also started using a CHANGELOG.md file to document changes in the project.

Conclusion

Compiler construction is complex and demanding work. It is very easy to get stuck because of a lack of ideas about how to achieve expected behavior, make tests pass, or even organize code. Following the rules above made my entry into the field of compiler construction drastically easier.