HN Explorer

Ask HN: Suggestions for writing a new compiler?

11 points by chm ↗ HN
I am a chemistry grad student and will be attending a graduate course in CS at my university in the coming weeks. The course is called "Programming languages and compilers" and its goal is to teach students about compilers by making them write one.

As I have never ventured into the world of compilers, I'm a bit lost as to where to start. I'm familiar with C, Python, HTML, Mathematica, FORTRAN 77, all of which I've used at different times and for different purposes, but haven't mastered any of them.

We (teams of 2) have the choice of either adding functionality to an existing compiler (suggestions include Gambit-C, Pascal-S, Tiny C, Small C) or write our own for any language or a subset thereof. If we choose to write our own compiler, it has to be written in Scheme, unless it can compile itself, in which case we can write it in any language. Coincidentally, I have begun reading Practical Common Lisp [0] last month and enjoy it.

The suggested textbook is "A. Appel, Modern compiler implementation in Java/ML/C". Other suggested readings are by Paul Graham.

Now my questions are:

1) Should I write my own compiler or extend an existing one?

2) Should I write a self-compiling compiler?

3) What language should I try to compile?

4) What books/resources will be helpful?

I'm asking these questions because I want to get the most out of this class. I think it's a great opportunity but that I could easily get lost. Almost everything written in the course plan I had heard of or read somewhere, so I am not completely out of the game.

Thanks in advance.

[0]http://gigamonkeys.com/book/

9 comments

[ 4.6 ms ] story [ 34.4 ms ] thread
inetsee
I don't know whether this would qualify for your class, but the Racket documentation includes an implementation of Algol-60 "http://docs.racket-lang.org/algol60/". You might be able to use this as the starting point of an implementation of another language, maybe a subset of Algol-68, or Simula.

Algol-60 was the first programming I learned, and I've always been fascinated by Algol and the languages derived from it.

marktangotango
That's really interesting, given your Chemistry focus, what has motivated you to undertake this course? The requirement to write it in Scheme seems a bit onerous to someone who's never used Scheme. Given that, it would probably still be easier than extending an existing compler. I think you'd spend A LOT of time learning some ones design and coding practices.

I always point people at this article. It's a nice short synapsis similar to Crenshaws "Let's Build a Compiler" series only much shorter in length. Plus it's Python, so may give you some ideas for Scheme:

http://www.jroller.com/languages/entry/python_writing_a_comp...

chm
I (try my best to) do research in molecular electronics. I need to write software to perform calculations. The reason I chose this particular course is simple: I have no other choice. Either I already have taken the other available classes or they aren't given in winter. My department doesn't offer many graduate computational chemistry courses. Thanks!
[dead] TempleOSV2
I am the highest skill level assembly language programmer with 5 years asm work experience on 6 different instructionsets and I started in 1983 with a 6502.

If you know assembly language you can probably write a compiler. If you don't know assembly language it will be really shitty.

I have 5 assembly language courses on my transcripts.

http://www.templeos.org/files/ASU_Transcripts.pdf

CSC226 CSC326 CSE421 CSE422 CSE523

----

I have been paid to program in the following asm instruction sets : VAX, 8051, x86, 68000, PIC, and Atmel AVR.

You are not me. You cannot be me even if you try. I have 20,000 hours of asm experience. I am an expert.

----

Yes, I have a compiler course I took. I wrote Ticketmaster's report generator expression byte-code compiler.

I made SimStructure, a C interpretor in 2000-2001

http://www.templeos.org/files/SimStrSetUp.zip

----

Go to internet archive http://www.simstructure.hare.com and get May 27 2004, HOPPY download. It has my compiler in turboassembly before it compiled itself.

----

This is why I am the best asm programmer on the planet:

http://www.templeos.org/Wb/Demo/Lectures/64BitAsmQuiz.html

AnimalMuppet
It seems to me that "can compile itself" is going to be extra work. That is: You specify a language. You write a compiler for that language in that language. But you can't compile the compiler, since you don't have the compiler yet. So you have to write the compiler in some other language that already has a compiler.

Note that this does not apply if you are writing something like a C compiler, because there are already C compilers out there.

Turing_Machine
If you decide to go with something in the Lisp/Scheme spectrum, you might find the book Lisp in Small Pieces to be helpful.

If you decide to go with a non-Lisp language: are you allowed to use tools like bison/yacc and lex/flex (or analogs for non-C languages)? Those can cut down the amount of work by a lot. Making it self-hosting over the course of semester is still going to be challenging, I think, especially if you have no previous background in compilers and/or low-level code (there are a lot of other issues there, such as the need to write or otherwise obtain an I/O library).

If it were me, starting from ground zero, I'd either go with extending an existing compiler or writing something in Scheme.

soegaard
"Lisp in Small Pieces" is very well-written. It will teach you a lot about how to compile (subsets) of Scheme.

If you decide to compile a Pascal-like language, I can't recommend "Brinch Hansen on Pascal Compilers" enough. If I remember correctly the Pascal compiler described in the book can compile itself.

porlw
Regarding 3, I would consider compiling a simple lisp - if you're coding in scheme that will take care of the parsing, so you can concentrate on the code generation side.