Learning to write a compiler

http://stackoverflow.com/questions/1669/learning-to-write-a-compiler

by siim • 16 years ago

128 40 16 years ago

mapleoin• 16 years ago

I'm upvoting this just to hopefully start a discussion and hear more about this topic from fellow HNers.

I hear the Dragon Book mentioned almost daily around here; I'm intrigued. Do you think this book could be read by someone who's not actually interested in writing a compiler? Does the book stand by itself? I'm interested in reading it, but I don't really think I have the motivation to start writing my own compiler (even a mock one).

petercooper• 16 years ago

Yes. I bought and read it out of interest rather than a desire to actually build a compiler. As long as you're OK with set theory and general math notation, it's not a particularly tricky read, and you get to learn a lot of cool stuff about automata/state machines in an applied, practical sense.

jhpriestley• 16 years ago

I had trouble getting through much of it, even though I tend to read technical books for fun. Lisp in Small Pieces or the Lambda Papers are more educational and easier to read. They will change the way you think about programming far more than the Dragon book.

The dragon book is okay as a comprehensive reference, but is bad at communicating the central idea of anything. You might want to skim it, looking for topics that interest you, then seek out several sources for those topics and see which clicks for you. If you start reading the Dragon book from page 1, you risk getting bogged down.

dlo6• 16 years ago

I definitely would not recommend starting from page 1. You can pick at it gradually. Personally, I've gravitated more toward the second half of the book where it gets far more interesting. (I have the 2nd edition, where coverage of the back-end is vastly improved.)

dekz• 16 years ago

If you're interested in language design also may I suggest, http://www.amazon.com/Language-Implementation-Patterns-Domai... and http://www.amazon.com/Language-Implementation-Patterns-Domai...

There are also some programmers around who are going through the process of designing and implementing their own languages, you can watch their progress and ideas. Here is 1(2?) examples, Magpie and Finch by munificent. http://bitbucket.org/munificent

It seems Magpie has started out using a C# compiler/interpreter but now uses Java?

silentOpen• 16 years ago

Do you want to build a compiler or design a programming language? The Dragon Book is pretty heavy on implementation details if you just want a taste without building one.

If you're just getting started in mechanical program transformation, I strongly recommend using something like Structure and Interpretation of Computer Programs and its meta-circular evaluator to get the basics without the grunge of parsing and generation.

dlo6• 16 years ago

It is possible to skip the first half of the Dragon Book if you are not interested in front-end stuff. (I am not.) Chapters 8 and onward are far more interesting IMO. You will encounters topics such as SSA, data-flow analysis, points-to analysis, binary-decision diagrams, call graphs, Datalog, etc.

pvg• 16 years ago

When did reading books become a purely utilitarian thing? Interested in reading it? Read it. It's a good book. You don't have to do the exercises.

jerf• 16 years ago

"When did reading books become a purely utilitarian thing?"

When the answer to the question "How do I learn to do X?" is "Read this book."

Nice sentiment, wrong place. "Read this book even though it won't help you learn X" translates directly to "Don't read this book." in this context.

Groxx• 16 years ago

When we started having to prioritize our time.

i.e., around high school, with a significant increase after college / marriage.

pbiggar2• 16 years ago

DO NOT READ THE DRAGON BOOK.

It's not a very good introduction to compilers. Read Engineering a Compiler by Cooper and Torczon. The Appel book is also very good, and contains some stuff about functional and logic languages that are generally missing from most compiler texts. If you're an enthusiast, but not in it to build a compiler, I really enjoy Programming Language Pragmatics. For more advanced material, use the Muchnick book, or the Compiler Design Handbook (both editions have different materials). They also provide excellent pointers to literature, but aren't great for beginners.

I get the impression that most people who recommend the Dragon book haven't read it. When I was doing my PhD I had five or six books on my shelf, and was constantly unimpressed with the Dragon Book, but always impressed with Cooper/Torczon, Muchnick and Appel.

kingkilr• 16 years ago

Couldn't agree more, I hack on compilers a fair bit (one of my own, plus the JITs in PyPy and Unladen Swallow) and the Dragon Book was impossible for me to get anything out of.

dlo6• 16 years ago

I started picking at Muchnick. From the look of it, it is almost all back-end stuff.

mouth waters

ahn• 16 years ago

>I get the impression that most people who recommend the Dragon book haven't read it.

These days you can usually tell that they haven't read it if they refer to it as "the Dragon book" and don't say anything about the edition. The same thing goes for "Knuth", "the Appel book", etc.

haberman2• 16 years ago

> Read Engineering a Compiler by Cooper and Torczon.

That book has an error in it which I have reported to the authors twice but never heard anything back. This leaves a bad taste in my mouth.

Here's what I wrote to them:

Subject: Errata for "Engineering a Compiler" Date: Sat, May 26, 2007 at 8:12 PM

Hello,

I noticed that your section on DFA minimization is labeled "Hopcroft's Algorithm," but doesn't seem to describe the algorithm explained by Hopcroft in his 1971 paper [0]. Your algorithm appears to be n^2, where Hopcroft's is n log n. David Gries gave a somewhat more digestible presentation of the same algorithm in a follow-up paper in 1972 [1].

Hope this information is useful!

Sincerely, <me>

[0] John E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. Technical Report: CS-TR-71-190, 1971. Available online at ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf

[1] David Gries. Describing an algorithm by Hopcroft. Acta Informatica, 2(2):97-109. Online reference: http://www.springerlink.com/content/r5631549671g6251/

b3b0p• 16 years ago

I agree with this. I was told this was the so called bible of compiler development and must have. I cannot recommend it.

So, I bought it (cheapest copies used were over $100), tried to read it, and got nothing out of it. I gave up about half way through. It's been a few years, but it read like no other technical CS book I can remember. If I recall, it like a theoretical explanation, a long lecture on paper.

Edit: Grammar

ww520• 16 years ago

The Dragon Book is quite readable. The best approach is to read each chapter by itself rather than going from beginning to end. If there's a topic interested you, jump to that chapter. You can jump to the regular expression chapter, which can be read by itself, jump to the code generation and program layout, or jump to the optimization chapter, which can be read by itself. The lex and parser topics sort of go together.

mfukar2• 16 years ago

I think the Dragon book is pretty approachable for someone with basic CS background. It's also quite extensive in its coverage of compiler implementation techniques. However, as others have already pointed out, certain aspects are not covered in full and implementation details are not always provided.

My suggestion? Read it. True to its title, "Principles, Techniques and Tools", it delivers just that. I don't think you'll find its contents impenetrable, but perhaps it will seem too abstract in case you're looking for implementation guidelines.

Some things that might bug you about the Dragon Book: 1) extensive coverage of lexical analysis and related techniques, 2) it's not suited for a more pragmatic course - this is better left to books like Muchnick's "Advanced Compiler Design and Implementation" and friends 3) it omits certain important advances in the field, such as the work of Pager, A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249-268., 1977 (in all fairness to the book authors, all work after yacc was out in 1973 has apparently gone unnoticed by all).

Disclaimer: I've only read the Pearson International Edition, which according to what I hear, is identical to the first edition. I don't know to what extent this is true. Maybe someone can confirm/refute this?

tonfa2• 16 years ago

> It's also quite extensive in its coverage of compiler implementation techniques.

With only two pages about SSA ? (which is the internal representation used by most compilers this days)

Someone• 16 years ago

"could be read?" Of course. whether you would enjoy it is another issue. Compare;

  "Do you think I could take piano lessons if I am not actually interested in playing a piano?"

    "Do you think I could study architecture if I am not actually interested in designing buildings?"

The former is not popular, the latter is, but AFAIK few people study the grunt work of architecture for fun. It all depends on where your interests are. What part of compiler writing intrigues you?

domgblackwell• 16 years ago

You might study architecture if you want to be able to understand the buildings you see in places you travel to. Just as not everyone who studies the history of art wants to be a painter...

okmjuhb• 16 years ago

The interesting thing about compiler writing is the drastic reduction in complexity that's happened. There are essentially off-the-shelf tools that can be used to handle everything before semantic analysis and everything after conversion to a reasonably high-level IR. This has dramatically reduced the cost of language experimentation; it's now feasible to bang out a new language in a day or two (assuming you're familiar with yacc, LLVM, etc.), and generate efficient code on a number of target architectures.

These tools mean that "learning to write a compiler" can take several different paths; on the one hand, we could learn about how each of these tools work (e.g. "how to write a parser generator", "machine-independent optimizations", "code generation", etc.). This is the approach taken by the dragon book. This gives the background theory and mathematics behind compiler-writing (and will likely be something people need to know if they want to write for instance an LLVM optimization pass). The problem with this is that, because of the trends mentioned above, it has little to do with the day-to-day of actual compiler writing and language experimentation (this is only somewhat true, since most "real" compilers will have a custom-written frontend and at least a little bit of knowledge about the target architecture).

The other approach is to use pre-written tools, to focus on language design decisions and applications. To be honest I'm not familiar with any resources that do this particularly well. This is the approach taken by most of the "we're going to build a compiler!" websites mentioned on the Stack Overflow post. This approach is probably more useful for most of the people who want to "write a compiler", but it leaves people with a very shallow knowledge of what's happening beneath the surface of the APIs they use.

I don't mean to imply that one of these approaches is "better" than the other (and indeed, the second requires a little bit of the first - it's difficult to debug an automatically generated parser without knowing at least a little bit of the theory), but it's important to know which approach you're aiming for, and trying to optimize based on that goal. Going to the Dragon book as a "how-to" is a disaster waiting to happen.

pjscott• 16 years ago

I think that combining this short compiler tutorial with LLVM would be a very effective way for someone to get comfortable with basic compiler writing:

http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

Afterward, learning how to do lexing and parsing would be a good addition. The tutorial covers a subset of scheme, which is trivially simple to parse, especially if you're writing the compiler in scheme as well.

wingo• 16 years ago

The top comment has a remarkably good list of references. I like the nanopass and incremental papers a lot, RTT is a classic, and there were several good-looking references I had never seen. Almost makes me feel some jealousy at the pleasant vertigo the original poster must feel :)

Hoff• 16 years ago

Here is an earlier incarnation of the "writing a compiler" thread:

http://news.ycombinator.com/item?id=1608129

silentbicycle3• 16 years ago

Oops, I downvoted you when I meant to upvote. There is probably another incarnation or three before the one you linked, too.

I'd recommend Appel's "Modern Compiler Implementation in ML" over the dragon book.

mitjak• 16 years ago

I noticed there are a few versions, including for Java and C. Any reason why the ML version is better (not against ML; just don't know it well enough (at all actually)).

Learning to write a compiler

Related Stories