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!

Comments

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?
http://www.antlr.org/wiki/display/CS652/CS652+Home

I would also search the archives at lambda-the-ultimate.org for tips.

Hope this helps.

Carlos
Anonymous said…
Check out http://www.lulu.com/content/808232

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

Eddie
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 (http://tinyurl.com/5fts49), 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 ( http://tinyurl.com/5uwn8o )
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.

http://www.cs.sjsu.edu/~louden/cmptext/
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 http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg02168.html.
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 B

Ubuntu 20.04 on a 2015 15" MacBook Pro

I decided to give Ubuntu 20.04 a try on my 2015 15" MacBook Pro. I didn't actually install it; I just live booted from a USB thumb drive which was enough to try out everything I wanted. In summary, it's not perfect, and issues with my camera would prevent me from switching, but given the right hardware, I think it's a really viable option. The first thing I wanted to try was what would happen if I plugged in a non-HiDPI screen given that my laptop has a HiDPI screen. Without sub-pixel scaling, whatever scale rate I picked for one screen would apply to the other. However, once I turned on sub-pixel scaling, I was able to pick different scale rates for the internal and external displays. That looked ok. I tried plugging in and unplugging multiple times, and it didn't crash. I doubt it'd work with my Thunderbolt display at work, but it worked fine for my HDMI displays at home. I even plugged it into my TV, and it stuck to the 100% scaling I picked for the othe

Creating Windows 10 Boot Media for a Lenovo Thinkpad T410 Using Only a Mac and a Linux Machine

TL;DR: Giovanni and I struggled trying to get Windows 10 installed on the Lenovo Thinkpad T410. We struggled a lot trying to create the installation media because we only had a Mac and a Linux machine to work with. Everytime we tried to boot the USB thumb drive, it just showed us a blinking cursor. At the end, we finally realized that Windows 10 wasn't supported on this laptop :-/ I've heard that it took Thomas Edison 100 tries to figure out the right material to use as a lightbulb filament. Well, I'm no Thomas Edison, but I thought it might be noteworthy to document our attempts at getting it to boot off a USB thumb drive: Download the ISO. Attempt 1: Use Etcher. Etcher says it doesn't work for Windows. Attempt 2: Use Boot Camp Assistant. It doesn't have that feature anymore. Attempt 3: Use Disk Utility on a Mac. Erase a USB thumb drive: Format: ExFAT Scheme: GUID Partition Map Mount the ISO. Copy everything from