A couple months ago I finished translating a simple generational garbage collector from MIPS[1] to x86-64 assembly[2], so that programms emitted by my toy compiler[3] run on the actual hardware instead of a MIPS emulator.
And sure enough, I had introduced a few bugs along the way. Here is a part of just one commit message:
> NoLeak-InsertionSort.cool exposed a problem where we make a copy of a prototype object
to pass it as `this` to the constructor. But while evaluating all the other constructor
parameters the copy gets promoted to Old Area. As a result any assignments the constructor
makes end up recorded in the assignment stack. So that the referenced objects survive the
next minor collection whereas they shouldn't have otherwise.
There is a class `ParameterizedAutoFactoryFactoryFactory`[1] in one of my pet projects.
The name does correctly reflect the purpose of this class. Although I could of course have come up with another one, the temptation of `Factory`x3 was just too strong to resist.
- Crafting Interpreters[2]. Compilers and interpreters have a lot in common and the book is exceptionally beginner-friendly. Basically, this is the perfect one to get started with.
- Introduction to Compilers and Language Design[3]. Doesn’t assume any preexisting compilers knowledge, and teaches all the basics necessary to build a compiler using a hands-down approach. The examples are in C.
Ignore the classics textbooks like the Dragon Book or "Modern Compiler Implementation" for the time. You can always come back to them later if you want to.
## Source code
Explore the sources of
- 8cc[4]. A compiler for the C programming language. It's intended to support all C11 language features while keeping the code as small and simple as possible.
- chibicc[5]. The successor of 8cc from the same author.
If you want a bit of background on these two compilers, check out the author's blog post "How I wrote a self-hosting C compiler in 40 days"[6]. Personally, I find it to be quite a fascinating read.
# Input language
Don’t try to come up with your own language just yet. Go with an existing educational language instead, and focus on learning about compilers. ChocoPy[7] is specifically designed for classroom use in compiler courses and by extension is great for a hobby compiler project.
# Target language
Many educational compilers emit MIPS assembly. Although it's possible to run it using an emulator, running a native executable produced by your own compiler feels much more rewarding. So I'd suggest your compiler emits x86-64 assembly.
For educational purposes, I'd avoid targeting languages such as LLVM IR or C. Emitting assembly helps understand many important concepts better:
The project was purely for fun and to other people it's, honestly, just another toy compiler.
But there are a couple things that should set it apart.
1) It compiles down to x86-64 assembly. Then invokes GNU as and ld to produce a native executable. To me personally, this is much more rewarding than emitting MIPS asm and using an emulator to run it.
I also prefer emitting asm to emitting, for example, C -- at the very least, it forces the developer to figure out converting expressions into asm. That really drives home the point how much work high level langs do for us.
2) The lang is simple but not too simple. A lot of mini-compilers have languages with functions, primitive values and pretty much nothing else. Whereas this project's lang has classes, inheritance, virtual dispatch, and even a very simple form of pattern matching.
3) The write-up describing the project. Final sections contain a number of links to awesome compiler-learning resources. Every major topics is covered only by one or two links. Obviously, I had to make these sections opinionated, but give it a chance, it might click for you too.
Other well-known languages that have hand-written parsers are Rust and D.
And here are a couple quotes from compiler developers explaining their reasons for going with hand-crafted parsers.
Someone from the C# compiler’s team gave the following reasons [1]:
>Hello, I work on the C# compiler and we use a handwritten recursive-descent parser. Here are a few of the more important reasons for doing so:
>Incremental re-parsing. If a user in the IDE changes the document, we need to reparse the file, but we want to do this while using as little memory as possible. To this end, we re-use AST nodes from previous parses.
>Better error reporting. Parser generators are known for producing terrible errors. While you can hack around this, by using recursive-descent, you can get information from further "up" the tree to make it more relevant to the context in which the error occurred.
>Resilient parsing. This is the big one! If you give our parser a string that is illegal according to the grammar, our parser will still give you a syntax tree! (We'll also spit errors out). But getting a syntax tree regardless of the actual validity of the program being passed in means that the IDE can give autocomplete and report type-checking error messages. As an example, the code ` var x = velocity.` is invalid C#. However, in order to give autocomplete on `velocity. `, that code needs to be parsed into an AST, and then typechecked, and then we can extract the members on the type in order to provide a good user experience.
GCC actually used Bison for a long time but eventually switched to a hand-written parser, the team gives some reasons in the changelog [2]
>A hand-written recursive-descent C++ parser has replaced the YACC-derived C++ parser from previous GCC releases. The new parser contains much improved infrastructure needed for better parsing of C++ source codes, handling of extensions, and clean separation (where possible) between proper semantics analysis and parsing.
Some people argue coding parsers by hand is prone to errors. This line of reasoning certainly makes a lot of sense to me, but it's not that simple in practice for non-trivial grammars. For instance, ANTLR 4 emits a so called parse tree which you would like to convert to AST, if you have a somewhat complex grammar. This conversion takes quite a bit of code written manually, see AstBuilder.java [3] to get an idea (I'm not affiliated with the project). So, there's still plenty of opportunities for having errors in that amount of code. To be fair, creating AST-s is an explicit non-goal for ANTLR 4 [4].
Not sure if it counts, but I made two Roslyn analyzers for C# code. A Roslyn analyzer is basically a C# compiler plugin which can emit additional diagnostics if it encounters a certain pattern in the code being compiled.
One of them lets a developer mark a C# method such that the method must be invoked with named args [1], calling it with positional args is a compile time error then.
And the other makes it a compile time error to discard a marked method's return value [2]. Kind of like it is in functional languages.
Was learning/practicing F# along the way, so the code is probably not so good. But it works :)
You might find [CS 6120: Advanced Compilers: The Self-Guided Online Course][1] interesting. I'm slowly working through it, but basically its focus is intermediate representations, optimizations, etc. A link to the course was on the first page of HN some time ago.
If you want to know more about LLVM IR specifically, check this [talk from 2019 EuroLLVM Developers’ Meeting][2]
Also -- and you knew it was coming -- I've written [a toy-compiler of a Scala subset][3] myself :)
I'm new to F# and writing compilers, so I'm sure the code is full of rookie mistakes. Still, it works and does generate assembly and executables for Linux and Windows.
And sure enough, I had introduced a few bugs along the way. Here is a part of just one commit message:
> NoLeak-InsertionSort.cool exposed a problem where we make a copy of a prototype object to pass it as `this` to the constructor. But while evaluating all the other constructor parameters the copy gets promoted to Old Area. As a result any assignments the constructor makes end up recorded in the assignment stack. So that the referenced objects survive the next minor collection whereas they shouldn't have otherwise.
[1]: https://theory.stanford.edu/~aiken/software/cooldist/lib/tra...
[2]: https://github.com/mykolav/coollang-2020-fs/blob/master/src/...
[3]: https://github.com/mykolav/coollang-2020-fs