Comment by silentbicycle | Hacker News Reader

Comment by silentbicycle | Hacker News Reader

Parent Full thread

Yes. I've read them both, they're worth your time. The thing with most compiler texts is that they bog you down with a lot of stuff upfront about automata, parsing algorithms, etc., and by the time they get to the good stuff, it's hard to see how it all fits together. Crenshaw dives right in, and you quickly get a simple compiler running. You can look into all the alternative parsing algorithms, etc. later.

Also, run-don't-walk to Ghuloum's "An Incremental Approach to Compiler Construction" (http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf). I'd suggest that before the Nanopass paper, really.

After those, I recommend Niklaus Wirth's _Compiler Construction_ (http://www.inf.ethz.ch/personal/wirth/books/CompilerConstruc...) and Andrew Appel's _Modern Compiler Implementation in ML_ for follow-up, in that order. Wirth's book is a quick read, about on par with Crenshaw's. Appel's is more in-depth.

Another comment, linking several HN compiler threads: http://news.ycombinator.com/item?id=1922002

> The thing with most compiler texts is that they bog you down with a lot of stuff upfront about automata, parsing algorithms, etc., and by the time they get to the good stuff, it's hard to see how it all fits together. Crenshaw dives right in, and you quickly get a simple compiler running. You can look into all the alternative parsing algorithms, etc. later.

I find this to be very true.

I've worked on commercial compilers and written a two of my own and I've come to believe that compiler writing is best done in stages.

- Learn a parser toolkit

- build your first AST

- learn why and how to transform the AST

- write an interpreter backend for your AST

- cross compile to another language

- write a backend for your compiler.

- optionally learn about intermediate forms and optimization, though this is seldom done on it's own.

If you learn compilers using Lisp / ML / etc., you can skip learning about parsing upfront and just use Lisp expressions. That's one of the reasons why the Lispers and MLers have so much cool compiler literature. If you're writing a compiler in C, you're stuck doing parsing and tree manipulation manually.

Nowadays, you could also use JSON, Python dicts, etc. for data literals. Either way - worry about syntax later.

While I agree with your point about starting, I think that parsing is a rather beautiful part of compiler construction by itself, with a nice theory behind it all, too.

Furthermore, if you are using Wirth style compilers, syntax-directed compilation comes rather naturally (at least to me). So I heartily second (and in fact have done so a number of times on HN) your initial recommendation for Wirth's "Compiler Construction", which is IMHO the canonical text to get somebody started. Instead of Appel's book, I find Cooper and Torczon's "Engineering a Compiler" much more comprehensive and illustrative (particularly the instruction selection and instruction scheduling parts.) Other interesting texts in the area are: Michael Scott's excellent "Programming Language Pragmatics" and Grune, Bal, Jacobs and Langendoen's "Modern Compiler Design" (both of which have a nice treatment of functional and logic programming languages [the latter one being more comprehensive])

I agree with you (and I've been researching Earley parsing and Pratt top-down operator precedence parsers lately), but: one thing at a time. While learning, it may be more helpful to experiment with AST transformations in Lisp and get immediate results, and wait on parsing until they get to the syntax design.

Also, too many toy interpreters/compilers mess around with syntax but have really conventional semantics. I suspect if people don't sink so much time into parsing etc. first, they may be more likely to focus on semantics instead.

I'm not so sure about that. People chance the sytax because that's an unfront difference between their language and others. Changing the semantics requires a leap for what can be perceive as little benefit (e.g. people will say "isn't this just C++ but with garbage collection?").

Eh. As far as I'm concerned, if the only difference is the syntax, what's the point? But I'm comfortable with the Erlang, K, Lisp, C, and Forth syntax, so "I grafted Ruby syntax on X" is pretty underwhelming.

Nice summary. Would you have any recommendation for good, easy to read, online resources on "learn why and how to transform the AST" and "write an interpreter backend for your AST"?

In particular, I suggest _Essentials of Programming_ Languages (http://eopl3.com/, AKA "EoPL"). Also, check out the _first_ edition - there's a really cool final chapter about compiling via continuation passing style (CPS, e.g. http://matt.might.net/articles/cps-conversion/) that got cut in later editions.

More generally - learn Lisp and/or ML, and go through any book that has you writing simple interpreters. EoPL, SICP, Appel's _Modern Compiler Implementation in ML_, "The Art of the Interpreter" (http://library.readscheme.org/page1.html), etc.

The most important book to avoid is the Dragon book. I know it's a classic, but it's outdated and incomplete. Appel's book is as close to a standard text as you're going to get.

Not to mention badly written and laid out. Makes for inefficient reading.

Reply on news.ycombinator.com