Hacker News new | comments | show | ask | jobs | submit login

As a programmer who didn't take the compiler class in school, what's the best way to go about learning what it takes to write one? A book recommendation? Find a CS dept nearby and take the class?

Appel's _Modern Compiler Implementation in ML_ is a good overview. It uses SML, but I've only used OCaml and haven't had any problems following it.

_Essentials of Programming Languages_ (EoPL) is a great book about writing interpreters in Scheme, and the last chapter shows how to turn an interpreter into a continuation-based compiler. (It's in the first edition, I heard it was cut from the second and third as too advanced.)

Some people will recommend the Dragon book (_Compilers: Principles, Techniques, and Tools_ by Aho, et. al), which is great, if you want a dry book about writing a pre-modern language with clunky, old tools.

As a sweeping generalization, compiler books using Lisp, ML, and other languages with good support for symbolic computation get into more interesting material, because compiler books using e.g. C tend to spend a good chunk of the book on parsing and other issues that can be avoided entirely by working directly on trees in Lisp/ML/Prolog/etc.

Which is not to say you necessarily want to skip parsing forever, but you probably don't want to go through several chapters about it upfront.

Compilers is a huge topic. Think a topic the size of databases, with way less visibility.

The Dragon book is probably the best introductory text. The new version that came out a few years ago actually did improve the original text a fair bit. Although there is a lack of discussion about SSA in the text.

While most compiler books spend most of the text talking about the front-end of the compiler the crazy interesting stuff is in the backend. The new Dragon book greatly improves here over the old one, but I'd also recommend two other texts:

1) Morgan, Building an Optimizing Compiler -- some people love the writing style. Others hate it, but the material is solid. 2) Muchnick, Advanced Compiler Design and Implementation -- Great book. Must read if you're serious about optimizations.

I enjoyed Muchnick as well, That said, even good Computer Architecture books cover a quite a bit about the basic optimizations of a modern compiler.

Computer Architecture: A Quantitative Approach, 4th Edition by Hennessy and Patterson. the Patterson and Hennessy is a good book to start with, too.

My knowledge is way out of date, but I think even back in 2000 those books were a bit behind the times in terms of optimizations production compilers do. For instance, there was little in-depth treatment of hot-cold optimizations in the 2nd edition.

The tension between processor architects and compiler writers is a constant theme.

Hey, no fair citing a "must read" book which is $100+ on Amazon.com. :(

Citeseer is free. :)

Implementation: Engineering A Compiler. Heavily focused on optimizing compilers for register machines.

Theory: Essentials of Programming Languages.

A Good Start: Programming Languages Application and Interpretation (Free online :-)


This tutorial walks you through writing a compiler for a tiny subset of scheme (programs consisting entirely of a single integer) and incrementally grows that into a proper language. It's very good, and I highly recommend working your way through it:


The Unix Programming Environment by Brian Kernighan and Rob Pike has an excellent introduction to lex and yacc in it. Following along with this gave me an idea of how languages get parsed and turned into code, and you can work though the whole chapter in a day or two.

It's like 90% of the practical knowledge of what a compiler does that I've ever needed to know for day-to-day coding.

I liked Scott's Programming Language Pragmatics (http://www.cs.rochester.edu/~scott/pragmatics/) because it covers both programming language issues and compiler implementation, but you might find it boring if you already have a PL background.

Appel's series of Modern Compiler Implementation in * is easy enough to ready and apply, and some come with code (IIRC).

How do the Java and C versions compare to the ML version? I have (and really like!) that one, but Appel's an ML hacker, and I'd be surprised if it translated 100% to C / Java.

I took a course based on the Java version, and it felt very clunky to me - the sample project code was very verbose and used the Visitor pattern whenever it could possibly be wedged in, making it a bit of a nightmare to understand the flow of the code as a whole. A good IDE would probably clear up a lot of this confusion, but it always felt like we were fighting the language. Take this with a grain of salt, however, since I'm fairly certain my professor edited the projects quite a bit before handing them to the students; perhaps the original book material is less convoluted.

I have the C version, and I personally found it easier going than the Dragon Book. As with the other books in the series, the beginning chapters dealing with the lexer an the parser are very mathematical - but the parts actually dealing with emitting bytecode are quite practical in nature. I ended up using the lexx/yacc tutorials to give me a grounding in parsing, without worrying too much about the mathematical basis for it, and then used the Appel book for everything after having derived an AST.

Ok, thanks.

They call it the "Dragon Book". Compilers by Alfred Aho. It's supposedly THE standard for compiler design.

Eh, as someone who hacks on compilers (both my own, and JITs in PyPy and Unladen Swallow) I've been reading the dragon book, but I don't really care for it, it's a little too academic IMO.

As an introductory text, it reads more like a summary of journal articles.

However, I would recommend chapter 2, which builds a complete compiler for a very simple language (arithmetic expressions). In the first edition, that did it in C, and it's very simple and clear. In the second edition, they did it in Java, and making it object-oriented makes it much less clear. I therefore recommend the 1st ed (plus, the hand-drawn dragon on the cover looks much better than the purple cgi dragon on the 2nd ed.)

Note that there is more than one hand-drawn dragon book cover by Aho & Ullman. Principles of Compiler Design tends to precede "The Dragon Book" as commonly referred, although the material overlaps a lot. The newer editions are much less clear with regard to the trade-offs in parser design, e.g. I don't think the section on concrete and abstract syntax uses the phrase "scannerless" or "scanner" at all while I am pretty sure PoCD at least says "scanner" and explains why you might separate the scanner/lexer from the parser. The Java book is much less clear, even though it improves on the reasoning (IIRC, pg ~113 in the Java edition) for why you should keep the two separate (although I personally consider these reasons to be myths) -- it is the fact that they don't really build up to the idea that makes me wonder why they provide justifications in the first place. They don't really debate whether concrete syntax is that useful, etc.

I have to agree that the Java code is an academic object-oriented programming example. It's not "less clear" so much as "less practical". For comparison, see the ANTLR API reference and the interfaces provided there, which differ just enough to show practical consideration for the use cases one might want.

I wouldn't recommend the first edition. It says a lot about parsing, not so much about the actually interesting parts of compilers. The second edition is supposed to be better in this respect, though.

I like the book Trustworthy Compilers by Vladimir Safonov. Written by a guy who has been doing it for 40 years. Currently works on MSFT Phoenix.

The reason why I like this book is that it has a gentle slope for the reader but also discusses pragmatic ways for how you can increase confidence that (a) you implemented it correctly (b) the users of your compiler trust the code does what it says it does [such as good error messages essential to a compiler for an IDE]

I have lots of compiler books, too, including all editions of all Aho/Ullman books (going back to their pre-lex/yacc books that used the string processing language SNOBOL). This doesn't mean the others are bad or hard to read. On the contrary, you need to pick up skills over time from somewhere, and I usually pick them up from other books on compilers or LNCS's on compilers, etc.

http://www.freetechbooks.com/compiler-design-and-constructio... contains links to a bunch of open source books on the topic of compilers. Enjoy.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact