Fundamentals of Compilers
2025-12-29
Just passing this on, I haven’t read it and can’t vouch for it. Some more free books on building compilers. A version in Racket and a version in Python (scroll down).
My take is that just about everything I’ve seen on compiler-building is too complicated. It’s been incrementally tweaked by decades of improvement.
From my perspective, the most important thing to understand about compiler-building is text-to-text transpilation (HLL -> ASM). All of the other stuff consists of nuances and algorithms that make this specific kind of t2t “better”. “ASTs” are just a data structure that makes thinking about parsing easier. BNF is just a DSL for parsing.
Even type-checking is just another “tool” (a hoary algorithm that should use Prolog or some other relational programming language) glued onto the side of the basic t2t process.
One of the easiest-to-understand articles I saw on building a compiler (a subset of C) is Ron Cain’s SmallC (page 176 in the original, 189 in the archive). It parses by using brute force string matching and emits simply by printing strings.
On the interpreter-building front, some of the simpler things I’ve seen are:
Frits van der Wateren’s Lisp (includes a full-blown Garbage Collector, albeit written in (simple) assembler)
The Smalltalk Blue Book (Part Four) - Part Four was unpublished, and reissued as the Purple Book. The removed section, Part Four of the Blue Book, contains a Smalltalk interpreter written in Smalltalk (a subset) along with code for a generational GC. Several decades later, the Blue Book was again made available to a wider audience.
The Most Beautiful Program Ever Written (not an interpreter per se, but a walk-through of Eval)
See Also
Email: ptcomputingsimplicity@gmail.com
Substack: paultarvydas.substack.com
Videos: https://www.youtube.com/@programmingsimplicity2980
Discord: https://discord.gg/65YZUh6Jpq
Leanpub: [WIP] https://leanpub.com/u/paul-tarvydas
Twitter: @paul_tarvydas
Bluesky: @paultarvydas.bsky.social
Mastodon: @paultarvydas
(earlier) Blog: guitarvydas.github.io
References: https://guitarvydas.github.io/2024/01/06/References.html