Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Learning to write a compiler

stackoverflow.com

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Learning to write a compiler

#31

Post by mfukar »

tonfa wrote: post #29
mfukar wrote: post #27

Earlier quoted context omitted.

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 y…

> 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)

Yes.

The omission of SSA (which, remember, gained in popularity after the publication of R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph., ACM Transactions on Programming Languages and Systems, 13(4):451-490, in October 1991) is in fact one of the many advances that fall in the (3) category I mentioned. I assumed I wouldn't have to enumerate every single one of them. Also, remember the edition I'm referring to. I have no idea if the latest edition (2007, iirc) covers SSA, and to what extent.

Nevertheless, the book is still extensive and thorough in the concepts it covers.

Re: Learning to write a compiler

#32

Post by tonfa »

mfukar wrote: post #31
tonfa wrote: post #29

Earlier quoted context omitted.

> 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)

Yes. The omission of SSA (which, remember, gained in popularity after the publication of R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. , ACM Transactions on Programming Languages and Systems, 13(4):451-490, in October 1991) is in fact one of the many advances that fall in the (3) category I mentioned. I assumed I would…

I was referring to the 2007 edition (the first edition obviously doesn't mention it). It's a bit sad to see they didn't even think it deserved a chapter...

You can look at the new stuff from the 2nd edition here: http://www.pearsonhighered.com/educator/academic/product/0,1...

Re: Learning to write a compiler

#33

Post by Someone »

mapleoin wrote: post #2

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…

"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?

Re: Learning to write a compiler

#34

Post by silentbicycle »

mitjak wrote: post #23
silentbicycle wrote: post #13

Earlier quoted context omitted.

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.

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)).

A very large part of compiler operations involve analyzing and transforming tree/graph data structures (once you've parsed to an AST), so you want a language with good native support for those structures. Pattern matching and garbage collection help immensely, as do ML's inferred static types. Working with complex data structures is really where ML shines.

It's not just ML, though - using a language where you can work directly with native tree structures (ML and Haskell's type constructors, Lisp sexps, Prolog functors, Lua tables, or even JSON) means that you can postpone learning syntax/parsing and start with the language's semantics. You can save the syntax details for when you have the language design worked out. Compiler books based on C (such as the dragon book) spend such a long time on parsing upfront because they don't have much choice.

Also, Andrew Appel works on SML/NJ, and the C and Java books are translated from the ML version. I've looked at the C version (which uses lex and yacc instead of ml-lex and ml-yacc, mallocs but doesn't free until later in the book, etc.), and while it's still a good compiler overview book, I'd strongly suggest getting the ML version instead. The ML version uses Standard ML (SML), but I've only used OCaml and didn't have trouble following it and making the minor adaptations along the way. (I haven't looked at the Java version. Whatever.)

Re: Learning to write a compiler

#35

Post by barrkel »

carterschonwald wrote: post #26
dlo wrote: post #20

Earlier quoted context omitted.

IMO, the format of this book makes sense for the context it was intended for: Stanford's course on optimizations and program analysis, where the problem sets and reading provide theoretical knowledge and the projects -- hacking on the joeq VM/compiler-infrastructure -- provide implementation experience. These distinct experiences make for a well-rounded education in advanced compiling techniques. (Disclaimer: I have…

I think there more obvious problems with the dragon book: in particular, ~300+ pages are spent focusing on techniques for doing parsing and lexing. Now if I want to write a baby yacc [sic], this might be useful. But in this modern era, parsing is a very well understood problem, with lots of easy to use tool. Yes in a production compiler helpful syntax and type error messages are key, but when you're learning the comp…

Even if you are writing a production compiler, you will likely not be using a tool, nor writing a tool, to generate the parser. Most production commercial compilers in practice use hand-written recursive descent with a hand-written lexer, which itself potentially uses feedback from the parser (very handy for parsing C or C++). Recursive descent usually gives context for error recovery that matches the way most programmers think about language syntax; and with it being written by hand, the recovery can be tweaked to be as smart as necessary.

Also, IDE / editor support like intellisense can greatly benefit from integration with a recursive descent parser. If you encode the cursor's position as a special token, the parser can handle that token and do a deep return (throw an exception, longjmp, whatever) with relevant context, active scopes, etc.

Re: Learning to write a compiler

#36

Post by haberman »

pbiggar wrote: post #15
mapleoin wrote: post #2

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…

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…

> 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,

[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/

Re: Learning to write a compiler

#37

Post by b3b0p »

pbiggar wrote: post #15
mapleoin wrote: post #2

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…

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…

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

Re: Learning to write a compiler

#38

Post by haberman »

carterschonwald wrote: post #26
dlo wrote: post #20

Earlier quoted context omitted.

IMO, the format of this book makes sense for the context it was intended for: Stanford's course on optimizations and program analysis, where the problem sets and reading provide theoretical knowledge and the projects -- hacking on the joeq VM/compiler-infrastructure -- provide implementation experience. These distinct experiences make for a well-rounded education in advanced compiling techniques. (Disclaimer: I have…

I think there more obvious problems with the dragon book: in particular, ~300+ pages are spent focusing on techniques for doing parsing and lexing. Now if I want to write a baby yacc [sic], this might be useful. But in this modern era, parsing is a very well understood problem, with lots of easy to use tool. Yes in a production compiler helpful syntax and type error messages are key, but when you're learning the comp…

> Now if I want to write a baby yacc [sic], this might be useful. But in this modern era, parsing is a very well understood problem, with lots of easy to use tool.

I certainly don't begrudge you using the existing tools, but speaking as someone writing a "baby yacc", I don't think parsing is quite the solved problem you make it out to be.

Yes there is TONS of literature on the subject, but new techniques and algorithms are being discovered all the time. ANTLR's LL(*) parsing hasn't been published yet (though I believe he's working on it) and only three years ago Frost, Hafiz and Callaghan published an algorithm for generalized top-down parsing in polynomial time. There's also the idea of PEG, published by Bryan Ford in 2004, a guy at UPenn who is carving out a set of languages between regular and push-down languages (http://www.cis.upenn.edu/~alur/nw.html).

All of this is to say; we're still discovering things about parsing. It's not a settled subject.

Re: Learning to write a compiler

#39

Post by [deleted] »

ahn wrote: post #25
pbiggar wrote: post #15

Earlier quoted context omitted.

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…

>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.

[deleted]

Re: Learning to write a compiler

#40

Post by silentbicycle »

haberman wrote: post #38
carterschonwald wrote: post #26

Earlier quoted context omitted.

I think there more obvious problems with the dragon book: in particular, ~300+ pages are spent focusing on techniques for doing parsing and lexing. Now if I want to write a baby yacc [sic], this might be useful. But in this modern era, parsing is a very well understood problem, with lots of easy to use tool. Yes in a production compiler helpful syntax and type error messages are key, but when you're learning the comp…

> Now if I want to write a baby yacc [sic], this might be useful. But in this modern era, parsing is a very well understood problem, with lots of easy to use tool. I certainly don't begrudge you using the existing tools, but speaking as someone writing a "baby yacc", I don't think parsing is quite the solved problem you make it out to be. Yes there is TONS of literature on the subject, but new techniques and algorith…

Ierusalimschy's LPEG (a PEG parser for Lua[1]) also has some new developments. IIRC, he found a way to greatly improve the space performance of PEGs. I've used it a lot (it's a nice middle ground between REs and a full parsing framework, and Lua is one of my favorite languages), but I'm not familiar enough with Ford's PEG implementation to be more specific.

Also, here's a good blog post[2] in which the author discovered how using parsing tools to syntax-highlight text as it's being modified quickly led him to the frontiers of parsing research.

[1]: http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html

[2]: http://www.codekana.com/blog/2009/04/02/on-the-speed-of-ligh...

Post reply on HN