News for hackers. Stuff that matters.
Re:Want to Write a Compiler? Just Read These Two Papers. by Jabbles on Friday August 26, 2011 @05:05AM (#2927888)
"Just"? I make the first one 94,000 words. Has anyone actually read the papers to make sure that the OP has recommended something worthwhile? "Reading" and then coding alongside would probably take a full week's worth of time (I'd be interested to know if different).

It's a genuine question. People are recommended to read SICP all the time, by many influential people, but when a proper discussion of whether it's actually worthwhile comes up, we found a considerable range of opinions.

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

Re:Want to Write a Compiler? Just Read These Two Papers. by silentbicycle on Friday August 26, 2011 @08:53AM (#2928292)
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

Re:Want to Write a Compiler? Just Read These Two Papers. by chollida1 on Friday August 26, 2011 @09:59AM (#2928484)
> 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.

Re:Want to Write a Compiler? Just Read These Two Papers. by silentbicycle on Friday August 26, 2011 @02:21PM (#2929363)
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.

Re:Want to Write a Compiler? Just Read These Two Papers. by sb on Friday August 26, 2011 @04:12PM (#2929806)
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])

Re:Want to Write a Compiler? Just Read These Two Papers. by silentbicycle on Saturday August 27, 2011 @11:00AM (#2931607)
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.

Re:Want to Write a Compiler? Just Read These Two Papers. by true_religion on Saturday August 27, 2011 @11:56AM (#2931741)
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?").
Re:Want to Write a Compiler? Just Read These Two Papers. by silentbicycle on Sunday August 28, 2011 @02:09PM (#2934534)
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.
Re:Want to Write a Compiler? Just Read These Two Papers. by aroberge on Friday August 26, 2011 @02:03PM (#2929297)
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"?
Re:Want to Write a Compiler? Just Read These Two Papers. by silentbicycle on Friday August 26, 2011 @02:18PM (#2929350)
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.

Re:Want to Write a Compiler? Just Read These Two Papers. by Locke1689 on Friday August 26, 2011 @11:28AM (#2928759)
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.
Re:Want to Write a Compiler? Just Read These Two Papers. by AnthonBerg on Saturday August 27, 2011 @06:36AM (#2931251)
Not to mention badly written and laid out. Makes for inefficient reading.
Re:Want to Write a Compiler? Just Read These Two Papers. by onan_barbarian on Friday August 26, 2011 @05:26AM (#2927913)
Good point; this topic has been discussed previously and a number of alternatives have been plausibly mentioned - Appel's book has a lot of fans.

The original article is very vague as to what the alternatives to reading a 'just' reading 94K words + a contentious paper on pass structure might be. One suspects heavyweight contenders like the Dragon Book, Muchnick, and Cooper and Torczon are being set up as strawmen.

There are a lot of compiler books which aren't suitable for the task; there is way too much in those last three books for someone who is just looking to 'bang out a compiler as quick as possible'.

Building a compiler by yourself is a noble goal, but the definition of success is pretty fluid.

Person A might build a heck of a compiler for a 'little language' by bolting an ANTLR frontend to an LLVM backend and learn a lot. Person B might hand-build a recursive descent parser and spit out a simple stack-based IR which she runs in an hand-crafted interpreter. Both would have learned a lot, in radically different directions.

Re:Want to Write a Compiler? Just Read These Two Papers. by timtadh on Friday August 26, 2011 @10:10AM (#2928514)
I am not sure anyone would think you could learn how to write a compiler from scratch from Muchnick's book. It is a fantastic book, easily one of the best CS books I have ever read. However, the author makes it pretty clear from the get go that it isn't a book to learn to write a compiler. You should already know how to do that. It is a book to learn to write a really good production optimizing compiler. He expects a lot from his readers, and if you don't have the background you will quickly give up (as I did the first time I tried to read it).

I learned to write a compiler from the Dragon Book. I taught myself how to do it. It took me several years to become good at it. However, I consider that experience invaluable. While, the original article advocated just diving in to the compiler without a lot of background on lexing and parsing. I personally wasn't happy until I had written my own parser generator and fast regex engine (which I learn how to do from Russ Cox's excellent articles on the subject).

Re:Want to Write a Compiler? Just Read These Two Papers. by iskander on Friday August 26, 2011 @10:07AM (#2928507)
I'm doing compiler research and I think reading both papers was a good use of my time. Compilation is a field full of poorly organized information, the authors are rare gems of clear thought.
Re:Want to Write a Compiler? Just Read These Two Papers. by perlgeek on Friday August 26, 2011 @05:22AM (#2927907)
I have read Crenshaw's series (the first one that is recommended), and found it eye-opening how easy it is to write simple parsers and compilers.

That said he does use some obscure assembly of which I hadn't heard before, so I'd really love to see an update to a more mainstream platform.

Re:Want to Write a Compiler? Just Read These Two Papers. by narag on Friday August 26, 2011 @06:03AM (#2927977)
IIRC there was a version of the code for x86.
Re:Want to Write a Compiler? Just Read These Two Papers. by telemachos on Friday August 26, 2011 @07:02AM (#2928067)
A bit of Googling found this blog post[1] which lists a number of Crenshaw-based variants.

Two other quick finds: a more readable pdf version of the Crenshaw tutorial itself[2], and "an x86 compiler written in Ruby"[3] made by following along in the Crenshaw tutorial.

[1] http://blog.spacesocket.com/2011/06/24/lets-build-a-compiler...

[2] http://www.stack.nl/~marcov/compiler.pdf

[3] https://github.com/samsonjs/compiler