An Incremental Approach to Compiler Construction(scheme2006.cs.uchicago.edu)
scheme2006.cs.uchicago.edu
An Incremental Approach to Compiler Construction
http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
8 comments
There is a "port" of the same articles to Forth/x86:
http://home.iae.nl/users/mhx/crenshaw/tiny.html
http://home.iae.nl/users/mhx/crenshaw/tiny.html
That paper is epic. It's actually a tutorial for undergrads on compiler construction, however, Ghuloum does nothing but code generation. From start to finish.
It is one of my favorite papers, and a gateway to a wealth of information available for hack/self-study.
It does have the insidious aspect though that if you get something halfway working and you like it, you will spend thousands of hours making it perfect. It seems an OK bargain, though...
It does have the insidious aspect though that if you get something halfway working and you like it, you will spend thousands of hours making it perfect. It seems an OK bargain, though...
As someone who knows very little about compilers, is there any good place to read up on the very basic terminology and such (what a parser is, what they mean by code generation, and get a rough outline how code goes from language to something the processor can understand) that is on a slightly more abstract level than this paper?
here is what you are looking for. http://www1.idc.ac.il/tecs/
With this I built not only a compiler but a virtual machine, an assembler AND the machine it all runs on!
It's the most awesome book I ever came across. You will come away from this so much more confident in your knowledge of how computers really work. I can't recommend it highly enough especially if you don't have a computer science background as I don't.
Can anyone second this opinion? I've had this book on my list for some time now.
I do have a CS background, but always appreciate deeper insight into things I might have missed.
I do have a CS background, but always appreciate deeper insight into things I might have missed.
Yes, I highly recommend this book. I have a bachelor and master in Computer Science. I worked through this book after finishing my bachelor. I would complete a project a week or so, by just spending a few hours on it in the weekend. The supporting software is really top-notch. Each project comes with extensive tests, and you can be pretty confident in your work if it passes them all. So it's ideal for self-study.
This book is really fun, and it's a great way to step back from your CS education, and get a perspective on all the abstractions upon which software is built.
You'll learn about combinatorial & sequential logic, ALU & memory chips, CPU & von Neumann architecture, machine & assembly language, assemblers, virtual machines, parsing and code generation. The hardware part is built using a freely provided Hardware Simulator and the software part can be tackled in any programming language(s) you choose. You can get started right now by going to the book's website, http://www1.idc.ac.il/tecs/plan.html, which has some sample chapters and all the tools (like the Hardware Simulator) you'll need to complete these wonderful projects. Each project comes with extensive test cases, giving you immediate feedback on your progress.
So, yes. This is a really enjoyable hands-on book. I wish there were more like it!
This book is really fun, and it's a great way to step back from your CS education, and get a perspective on all the abstractions upon which software is built.
You'll learn about combinatorial & sequential logic, ALU & memory chips, CPU & von Neumann architecture, machine & assembly language, assemblers, virtual machines, parsing and code generation. The hardware part is built using a freely provided Hardware Simulator and the software part can be tackled in any programming language(s) you choose. You can get started right now by going to the book's website, http://www1.idc.ac.il/tecs/plan.html, which has some sample chapters and all the tools (like the Hardware Simulator) you'll need to complete these wonderful projects. Each project comes with extensive test cases, giving you immediate feedback on your progress.
So, yes. This is a really enjoyable hands-on book. I wish there were more like it!
"I wish there were more like it!"
Me too. having read TECS and gotten through it despite setbacks it's given me the confidence to feel like I can develop a more comprehensive understanding of specific areas of CS as long as I have a good course to follow. 2 other books interest me because they have accompanying software. One is the Tannenbaum/Minix combo and the other is Jeanna Matthews book Computer Networking which also has supporting software. I recently got the latter but I haven't started it yet. It has good reviews on Amazon so I'm hoping for another TECS experience! The Tannenbaum book has more mixed reviews and it is a bit pricey so I'm holding off on that for awhile
Me too. having read TECS and gotten through it despite setbacks it's given me the confidence to feel like I can develop a more comprehensive understanding of specific areas of CS as long as I have a good course to follow. 2 other books interest me because they have accompanying software. One is the Tannenbaum/Minix combo and the other is Jeanna Matthews book Computer Networking which also has supporting software. I recently got the latter but I haven't started it yet. It has good reviews on Amazon so I'm hoping for another TECS experience! The Tannenbaum book has more mixed reviews and it is a bit pricey so I'm holding off on that for awhile
Cool, the Jeanna Matthews' book also looks pretty hands-on. I'll check it out (yay! I found it in my country's library network :-).
Otherwise, I know quite a few books that have good and interesting code (say, Norvig's PAIP, but a good list can be found in answer to this SO question: http://stackoverflow.com/questions/282470/which-books-have-r...). But these books are more passive by nature. You just read and understand the code. While TECS is really all about the projects (there is not much point to the book otherwise).
I also had a good experience with Building Problem Solvers, but I think it's because I used with a particular idea in mind (applying the truth-maintenance systems of the book to debugging metabolic networks; see biohacker.googlecode.com). So I also took a very hands-on approach: not only understanding the code, but running it, fixing it, extending it, etc.
Otherwise, I know quite a few books that have good and interesting code (say, Norvig's PAIP, but a good list can be found in answer to this SO question: http://stackoverflow.com/questions/282470/which-books-have-r...). But these books are more passive by nature. You just read and understand the code. While TECS is really all about the projects (there is not much point to the book otherwise).
I also had a good experience with Building Problem Solvers, but I think it's because I used with a particular idea in mind (applying the truth-maintenance systems of the book to debugging metabolic networks; see biohacker.googlecode.com). So I also took a very hands-on approach: not only understanding the code, but running it, fixing it, extending it, etc.
biohacker looks very interesting (also same Joyce quote on the website as in the TECS book!)
[deleted]
[deleted]
I'm assuming most compilers don't ship nasm/masm/whatever with them. How do compilers do actual "assembly to executable" step?
Historically, C compilers really did run an assembler in a separate process and communicate with it via pipes or files. gcc still ships with gas. gas is more oriented to the needs of a compiler than to human writers of assembly code.
Some compilers emit machine code from their own low-level intermediate representation, though. The trade-offs are similar to any other build/buy technical decision: full-custom gives you more control, while forcing you to reinvent the wheel.
Some compilers emit machine code from their own low-level intermediate representation, though. The trade-offs are similar to any other build/buy technical decision: full-custom gives you more control, while forcing you to reinvent the wheel.
One can assemble directly in your language of choice. See http://code.weinholt.se/industria/ for a particularly terse example: 1300 lines for an x86 assembler.
Link to source: http://bazaar.launchpad.net/~weinholt/scheme-libraries/indus...
Link to source: http://bazaar.launchpad.net/~weinholt/scheme-libraries/indus...
Here's something similar, more tutorial-like in Ruby:
http://www.hokstad.com/compiler
At least as of ~four years ago or so, this is how the compiler construction course was taught at IU, according to one of my co-Ph.D. students who went there. He loved the course and its debuggable-at-each-step architecture.
Similarly in Haskell, EHC: http://lambda-the-ultimate.org/node/366
This is a great paper. It was one of my biggest inspirations for writing Ur-Scheme.
http://compilers.iecc.com/crenshaw/
He spends a bunch of time on parsing, since it isn't Lisp.