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

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

ERNOS: Erlang Networked Operating System

I've been reading Dreaming in Code lately, and I really like it. If you're not a dreamer, you may safely skip the rest of this post ;) In Chapter 10, "Engineers and Artists", Alan Kay, John Backus, and Jaron Lanier really got me thinking. I've also been thinking a lot about Minix 3 , Erlang , and the original Lisp machine . The ideas are beginning to synthesize into something cohesive--more than just the sum of their parts. Now, I'm sure that many of these ideas have already been envisioned within Tunes.org , LLVM , Microsoft's Singularity project, or in some other place that I haven't managed to discover or fully read, but I'm going to blog them anyway. Rather than wax philosophical, let me just dump out some ideas: Start with Minix 3. It's a new microkernel, and it's meant for real use, unlike the original Minix. "This new OS is extremely small, with the part that runs in kernel mode under 4000 lines of executable code.&quo

Haskell or Erlang?

I've coded in both Erlang and Haskell. Erlang is practical, efficient, and useful. It's got a wonderful niche in the distributed world, and it has some real success stories such as CouchDB and jabber.org. Haskell is elegant and beautiful. It's been successful in various programming language competitions. I have some experience in both, but I'm thinking it's time to really commit to learning one of them on a professional level. They both have good books out now, and it's probably time I read one of those books cover to cover. My question is which? Back in 2000, Perl had established a real niche for systems administration, CGI, and text processing. The syntax wasn't exactly beautiful (unless you're into that sort of thing), but it was popular and mature. Python hadn't really become popular, nor did it really have a strong niche (at least as far as I could see). I went with Python because of its elegance, but since then, I've coded both p