5 ms·

"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

by Jabbles 15y ago

"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 http://news.ycombinator.com/item?id=2846799

perlgeek 15y ago
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.
- narag 15y ago
  IIRC there was a version of the code for x86.
  - telemachos 15y ago
    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/ http://blog.spacesocket.com/2011/06/24/lets-build-a-compiler... [2] http://www.stack.nl/~marcov/compiler.pdf http://www.stack.nl/~marcov/compiler.pdf [3] https://github.com/samsonjs/compiler https://github.com/samsonjs/compiler
onan_barbarian 15y ago
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.
- timtadh 15y ago
  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).
silentbicycle 15y ago
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 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/CompilerConstruction/CBE.pdf 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 http://news.ycombinator.com/item?id=1922002
- chollida1 15y ago
  > 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.
  - aroberge 15y ago
    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"?
iskander 15y ago
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.

by Jabbles 15y ago

perlgeek 15y ago

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.

narag 15y ago
IIRC there was a version of the code for x86.
- telemachos 15y ago
  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/ http://blog.spacesocket.com/2011/06/24/lets-build-a-compiler... [2] http://www.stack.nl/~marcov/compiler.pdf http://www.stack.nl/~marcov/compiler.pdf [3] https://github.com/samsonjs/compiler https://github.com/samsonjs/compiler

onan_barbarian 15y ago

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.

timtadh 15y ago
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).

silentbicycle 15y ago

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 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/CompilerConstruction/CBE.pdf 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 http://news.ycombinator.com/item?id=1922002

chollida1 15y ago
> 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.
- aroberge 15y ago
  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"?

iskander 15y ago

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.