Thursday, July 31, 2008

Computer Science: How to Implement Compilers and Interpreters

I'm stuck.

I just finished watching the SICP lectures. They were really good. (Thanks Mike Cheponis!) I've written partial implementations of Lisp in Python (thanks to PLY and some creativity) and Haskell (thanks to Write Yourself a Scheme in 48 Hours). I'd like to get a lot more serious about implementing languages, but I'm stuck.

I know that EOPL is a really good book. So is the dragon book. I've started both of them at separate times and gotten discouraged. One main problem is that I can only work on this stuff between 12-3AM because of work and kids, so I don't have enough time or enough mental energy. Currently, I think my options are:
  • Give up until I magically have more time one day.
  • Start working on EOPL and plan on it taking several years.
Is there a more approachable book that will still teach me what I need?

One thing I'm really afraid of is that I'm always at risk for burnout, and I'm really afraid EOPL will send me over the edge. On the other hand, I really haven't given up on the dream of being a decent language implementor, and EOPL is the most direct route to making that happen.

With my constraints in mind, can you lend me some advice? Thanks!


CharlesMerriam said...

Go ahead, but recognize that its just for learning. Barne Stroustrop talked about the horror of finding himself with a language that about five people used. Just enough to trap him into working on it and not enough to hire someone else to implement.

Right now, most languages are converging in the third generation space. You might have more impact looking at the killer replacement language to existing css/javascript/flash/http/html crud.

That said, have you made a simple recursive descent parser?

Shannon -jj Behrens said...

> Go ahead, but recognize that its just for learning.

> You might have more impact looking at the killer replacement language to existing css/javascript/flash/http/html crud.

You're probably right.

> That said, have you made a simple recursive descent parser?

No, but I understand the theory well enough. I always use parsing tools since I figure parsing is a relatively solved problem.

Shannon -jj Behrens said...

Hmm, another option would be to actually *read* SICP and actually develop the Lisp and Prolog-like examples I watched in the videos.

Carlos said...

Have you looked at Terence Parr course?

I would also search the archives at for tips.

Hope this helps.


Anonymous said...

Check out

Note the free PDF if you don't want to buy.
I've started it and think it will be easier than EoPL.


Mikeyp said...

I'm definitely not an expert, but I dabbled in this stuff in the past learning about parallelizing compilers.

I have always leaned towards practical books that include code, so I like Allen Holubs's Complier Design in C (, which is now out of print. It's more digestable than the Dragon book, and much more hands on. Holub also wrote a Unix shell for MS-DOS, and published a book on it called 'On command'. Not a compiler book pre se, but again a practical, code intensive book.

For a different take on interpreters, try to dig up a copy of Loeliger's 'Threaded Interpretive Languages', which deals with building stack oriented, Forth like languages ( )

Anonymous said...

Hi. I know everybody hates the dragon book and I do understand why. But a while ago I was able to turn those parsing algorithms into a real python parser. It was actually pretty easy from the code "examples" as long as you ignore all the irrelevant stuff. Regards!

Shannon -jj Behrens said...

Interesting comments. Thanks, everyone!

"Programming Languages: Application and Interpretation" and "Complier Design in C" look particularly good.

Shannon -jj Behrens said...

My buddy Stephen recommended Stanford CS143. It uses the Dragon Book and walks you through building a simple OO language.

Barce said...

If you're looking for something really practical and something that can be learned in two semesters, approximately 9 - 10 months, then I totally recommend Louden's Compiler Construction.

Shannon -jj Behrens said...

Looks like there are a couple books on writing simple C like compilers.

Shannon -jj Behrens said...

Someone showed me "Basics of Compiler Design" by Torben Ægidius Mogensen. It looks short, but sweet.

Jeff Younker said...

I'd suggest taking a look at "Modern Compiler Implementation in ML" by Andrew W. Appel. I found it quite informative, but people seem to either love it or hate it.

Shannon -jj Behrens said...

There are a lot of books suggested, and I like them for different reasons. That's really helpful. I think I see light at the end of the tunnel.

Shannon -jj Behrens said...

Regarding "Modern Compiler Implementation in ML", for those of us who like Haskell and don't know ML, see

Shannon -jj Behrens said...

Wow, reading the comments, "Modern Compiler Implementation in ML" is actually exactly the sort of thing that would not work for me, unfortunately, given my constraints.

Sam Rushing said...

Implementing languages can be divided into two pieces easily. First, play with parsing. Once you grok that, transition to VM/compilation/etc.

A quick and easy intro to parsing (that also happens to be one of the best overall solutions in python) is to combine Plex with a hand-written recursive-descent parser. In almost all cases, SLR/LALR/etc is overkill and really more of a distraction than anything. Look at the Pyrex's parser and marvel at its speed and simplicity.

After parsing, you can pick up EOPL... if the size of the book is what frightens you, the third edition just came out and is probably half the size of the first edition.

Most standard compiler books are not going to cover the issues that are interesting to you. I'm assuming you don't want to write a C or Java compiler.

Shannon -jj Behrens said...

Excellent hints. Thanks, Sam.

Noah Gift said...

It is interesting when thoughts of impending death and daily time constraints mix with ambition.
We have a very short period on earth, and every second counts. How can we do the most with our lives?