The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
TechInterview.org
CityDesk
FogBugz
Fog Creek Copilot


The Old Forum


Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

Good book on compiler design / theory

Just out of academic interest I'd like to read up on compiler design. Are there any recommended benchmark texts on this topic?

Cheers.
J
Thursday, February 02, 2006
 
 
KR Send private email
Thursday, February 02, 2006
 
 
What a coincidence, I bought a book on this the other week :-)

One of the definitive texts and the one I'm reading at the moment is, the red dragon book called "Compilers Principles, Techniques, and Tools" by Alfred V.Aho, Ravi Sethi, and Jeffrey D.Ullman. The book was reissued last year and has additional chapters you can download.

A pretty good read.
Stephen Haunts Send private email
Thursday, February 02, 2006
 
 
This book is also pretty good 'Build Your Own .Net Language and Compiler'

http://www.amazon.co.uk/exec/obidos/ASIN/1590591348/qid%3D1138881654/203-8687125-0675116

But if you only get one book, get the dragon book :)
Stephen Haunts Send private email
Thursday, February 02, 2006
 
 
"Compiler design in C" by Allen Holub is a nice way to see the theory in The Dragon Book put to practice.

Anyway, my best advice to really understand it would be to (almost first) read thoroughly and understand the code to a recursive descent parser which generates code for a stack-based virtual machine, + the virtual machine. Read only as much theory as you need to understand that. Then, after you really grasp that & could code the thing from scratch, you can delve in the deeper details.

This means, you need not understand LALR parsing before you can really implement a compiler.

Do _not_ do everything with lex & yacc (or flex and bison, their modern names). Holub's book puts too much focus on that for my taste, although at least he develops a clone of those tools.

I have some articles in my site & blog on writing a compiler of the type I describe above, they may help together with the other sources.
J Send private email
Thursday, February 02, 2006
 
 
Ah, and don't forget to also disregard regular expressions for lexical scanning before writing your first compiler, they aren't necessary either.

So, to sum up: learn to write a compiler from the ground up w/o regexps and parser generators, or any complex parsing techniques for that matter. Simplify for the sake of understanding: use hand-coded lexical scanning, a recursive descent parser, and generate code for a stack machine. Read just the minimum theory to thoroughly grok this.

After that, you can go deeper in all the areas, and learn the rest of the stuff.
J Send private email
Thursday, February 02, 2006
 
 
Cool, I'll check out that book.  Thanks for the tip!

This may be of interest for achedemics:

http://www.amazon.com/gp/product/0672306557/103-1092387-9683046?v=glance&n=283155


I purchased this book way back when it came out.  It's not so much on compiler design but it does have a free C compiler and the book ties the compiler in on how to build an operating system.
Eric (another ISV guy with his company)
Thursday, February 02, 2006
 
 
If you are going to experiment with languages and compilers: pick the right languages, as the source language, as the implementation language and as the target language.

More specifically, if you are just experimenting and are free to make these choices: some languages are almost impossible to parse, no matter what tools you use along the way. Writing a compiler for such a language is no great fun.

Pascal is an excellent choice for a number of reasons: simple syntax, productions can almost always be recognised on their first keyword (important for recursive descent and LL(1)), code generation is simpler because all mutables and immutables are explicitly defined *and* typed and *before* use.

Getting the scanner and the parser is the easy part, the real hard part is the formantic analysis in between.

Choice of implementation language, source language and target language can influence each other:

http://www.hello.nl/2005Q1/20050203PickinganImplemen.html
Karel Thönissen Send private email
Thursday, February 02, 2006
 
 
Oops: formantic analysis is done between parsing and target code generation, not between scanning and parsing.
Karel Thönissen Send private email
Thursday, February 02, 2006
 
 
Thanks for the pointers all. On the Dragon book, what do people make of this review snippet from Amazon:?

"The dragon book is now twenty years old and it shows its age. Written in 1986, it predates RISC CPUs, pipelines and bubbles, out-of-order execution, object oriented languages, and twenty years of advances in optimization and type theory. Perhaps most damning is its minimial coverage of the compiler's back end: dependency analysis, optimization, instruction selection and scheduling, register allocation, and code generation. It was inadequate in 1986 and it's downright dysfunctional today."
J
Thursday, February 02, 2006
 
 
""The dragon book is now twenty years old and it shows its age. Written in 1986, it predates RISC CPUs, pipelines and bubbles, out-of-order execution, object oriented languages, and twenty years of advances in optimization and type theory. Perhaps most damning is its minimial coverage of the compiler's back end: dependency analysis, optimization, instruction selection and scheduling, register allocation, and code generation. It was inadequate in 1986 and it's downright dysfunctional today."

It does show its age, although the reviewer's ultimate conclusion is over the top, I think.

I personally don't think it's very suitable as a textbook for an introductory compiler course. Its coverage of the front-end portions of a compiler are extensive to a fault: it'll show you how three different ways of how to build the back-end to lex. This is all very interesting stuff, but it's the wrong emphasis for someone who hasn't written a compiler before.

Also, as the reviewer correctly points out, the coverage of the back-end (especially optimization in a modern context) is quite lacking and spends too much time on the wrong things for someone who hasn't written a compiler before.

My personal favorite book on this stuff is Andrew Appel's Modern Compiler Implementation in (C|ML|Java). (I suggest you get the C or ML version.) It covers the standard topics (such as parsing and lexing) in sufficient depth to let you understand how e.g. lex could be implemented, but without being encyclopedic in its treatment (which is a good thing). Also, more than half of the book is dedicated to "advanced" topics that deal with: functional languages, object-oriented languages, garbage collection, and a heap of optimization-related topics.

BTW, the way I originally learned to build a simple compiler was to read Jack Crenshaw's Let's Build a Compiler series of articles. They still hold up today, I think. Check them out:

http://compilers.iecc.com/crenshaw/
Per Vognsen Send private email
Thursday, February 02, 2006
 
 
I've found the "Essence of Compilers" by Robin Hunter an easier read than the "Dragon" book.
IanH. Send private email
Thursday, February 02, 2006
 
 
Go to a library to borrow the dragon book.

And buy Andrew Appel's Modern Compiler Implementation in (C|ML|Java).
Rick Tang Send private email
Thursday, February 02, 2006
 
 
I've been reading about compilers as well, I haven't looked at the Dragon book because Aho and others were supposed to have a new version of the book out earlier this year (it's title was something like "21st Century Compilers").  Amazon informed me that the book was no longer available...not sure what happened.

Any way, the best compiler book I have read is "Modern Compiler Design" by Dick Grune.  I found it to be better than Appel's books (I have two versions: C and ML).  Grune's book is the thickes of all my compiler books, but that is because he explains, in as simple terms as possible, the theory and the practice of compilers.

He also spends at least a chapter describing object oriented languages, functional languages and even logic languages.  He sometimes explains concepts such as continuations and co-routines using very simple pseudo C code.  Those four or five lines of code explain complex concepts better than pages of textual descriptions.  It is too bad this book is not more popular.

If you would like to go further and get an introduction to type theory, there is no better book than Ben Pierce's "Types and Programming Languages."
Falcon Send private email
Thursday, February 02, 2006
 
 
You might try "Engineering a Compiler" ( http://www.amazon.com/gp/product/155860698X ). It covers not just scanning and parsing (which the dragon book spends almost all its time on), but also type systems, memory management, Static Single Assignment form, dead code elimination, redundancy elimination, instruction scheduling and the harder-than-you-think problem of register allocation.

(Disclosure: I took classes at Rice University from the authors)
Different nickname this time Send private email
Thursday, February 02, 2006
 
 
Avoid Andrew Appel's book if you want to get started working on a compiler.

Allen Holub's book on building a C compiler is worth way more. And so is case with Crenshaw's essays.
Add the red dragon book for learning the theory and you can start engineering your own compiler in a week.

Again, avoid Andrew Appel. It glazes over the surface and doesnt touch anything regarding practical compiler construction. Speaking from experience here. You could learn a lot more from reading other books but that.
Vineet Reynolds Send private email
Friday, February 03, 2006
 
 
Personally I like the Appel book (I liked in Java), but I agree with the posts saying it's a bit academic. It's also, as someone mentioned, not encyclopediac, but it has an excellent set of further reading materials at the end of each chapter, so it's not the case that buying it won't teach you much.
R. C. James Harlow Send private email
Friday, February 03, 2006
 
 
Yup - the Dragon Book is old. I doubt very much, though, that someone just starting out is going to move beyond it quickly. I would suggest adding a more practical text, though. Like Holub.
A. Nonymous
Friday, February 03, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz