Skip to main content

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!


Unknown 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?
jjinux 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.
jjinux said…
Hmm, another option would be to actually *read* SICP and actually develop the Lisp and Prolog-like examples I watched in the videos.
Unknown 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!
jjinux said…
Interesting comments. Thanks, everyone!

"Programming Languages: Application and Interpretation" and "Complier Design in C" look particularly good.
jjinux said…
My buddy Stephen recommended Stanford CS143. It uses the Dragon Book and walks you through building a simple OO language.
Anonymous 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.
jjinux said…
Looks like there are a couple books on writing simple C like compilers.
jjinux said…
Someone showed me "Basics of Compiler Design" by Torben Ægidius Mogensen. It looks short, but sweet.
Anonymous 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.
jjinux 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.
jjinux said…
Regarding "Modern Compiler Implementation in ML", for those of us who like Haskell and don't know ML, see
jjinux 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.
Anonymous 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.
jjinux 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?

Popular posts from this blog

Drawing Sierpinski's Triangle in Minecraft Using Python

In his keynote at PyCon, Eben Upton, the Executive Director of the Rasberry Pi Foundation, mentioned that not only has Minecraft been ported to the Rasberry Pi, but you can even control it with Python. Since four of my kids are avid Minecraft fans, I figured this might be a good time to teach them to program using Python. So I started yesterday with the goal of programming something cool for Minecraft and then showing it off at the San Francisco Python Meetup in the evening.

The first problem that I faced was that I didn't have a Rasberry Pi. You can't hack Minecraft by just installing the Minecraft client. Speaking of which, I didn't have the Minecraft client installed either ;) My kids always play it on their Nexus 7s. I found an open source Minecraft server called Bukkit that "provides the means to extend the popular Minecraft multiplayer server." Then I found a plugin called RaspberryJuice that implements a subset of the Minecraft Pi modding API for Bukkit s…

Apple: iPad and Emacs

Someone asked my boss's buddy Art Medlar if he was going to buy an iPad. He said, "I figure as soon as it runs Emacs, that will be the sign to buy." I think he was just trying to be funny, but his statement is actually fairly profound.

It's well known that submitting iPhone and iPad applications for sale on Apple's store is a huge pain--even if they're free and open source. Apple is acting as a gatekeeper for what is and isn't allowed on your device. I heard that Apple would never allow a scripting language to be installed on your iPad because it would allow end users to run code that they hadn't verified. (I don't have a reference for this, but if you do, please post it below.) Emacs is mostly written in Emacs Lisp. Per Apple's policy, I don't think it'll ever be possible to run Emacs on the iPad.

Emacs was written by Richard Stallman, and it practically defines the Free Software movement (in a manner of speaking at least). Stal…

JavaScript: Porting from react-css-modules to babel-plugin-react-css-modules (with Less)

I recently found a bug in react-css-modules that prevented me from upgrading react-mobx which prevented us from upgrading to React 16. Then, I found out that react-css-modules is "no longer actively maintained". Hence, whether I wanted to or not, I was kind of forced into moving from react-css-modules to babel-plugin-react-css-modules. Doing the port is mostly straightforward. Once I switched libraries, the rest of the port was basically:
Get ESLint to pass now that react-css-modules is no longer available.Get babel-plugin-react-css-modules working with Less.Get my Karma tests to at least build.Get the Karma tests to pass.Test things thoroughly.Fight off merge conflicts from the rest of engineering every 10 minutes ;) There were a few things that resulted in difficult code changes. That's what the rest of this blog post is about. I don't think you can fix all of these things ahead of time. Just read through them and keep them in mind as you follow the approach above.…