Brownie
Brownie

Reputation: 7738

General Purpose Language to build a compiler for

Inspired by Eric Sink's interview on the stackoverflow podcast I would like to build a full compiler in my spare time for the learning experience. My initial thought was to build a C compiler but I'm not sure whether it would take too much time.

I am wondering if there is a smaller general purpose language that would be more appropriate to implement as a first compiler effort? Or is a C implementation doable on a reasonable timescale (200 hrs)?

It is my intention to target the CLR.

Upvotes: 12

Views: 2169

Answers (13)

None
None

Reputation: 3943

I'd recommend writing a brainf**k compiler. It is a very simple and good for a first compiler. And timescale would be more like 1 and a half hours. Some other good languages are Forth, Logo, and Lisp.

Upvotes: 0

Matt H
Matt H

Reputation: 7389

In a compiler course, we wrote compilers for a subset of C (I liked to think of it as C--). It wasn't that difficult since you knew where your boundaries were. You can always refactor and add more features later.

Upvotes: 1

S.Lott
S.Lott

Reputation: 392010

You'll be happiest writing compilers for older, smaller languages. Pascal, for example, were designed as learning tools. The Pascal language is small and elegant; the compiler can be written fairly simply.

Even an Oberon or Modula-2 compiler is similar in complexity to Pascal; their design was driven by the same person, Niklaus Wirth.

Languages like C, which evolved organically, are too full of quirks to be good learning experiences.

Upvotes: 13

Bill the Lizard
Bill the Lizard

Reputation: 406055

Whatever language you choose, remember you can define your own set of supported features to customize it to fit your learning goals. If you want to learn about compilers (which it sounds like you do), then you could write a C compiler but just drop support for some random feature, like pointers for example, or only implement a subset of the keywords, just to make it more manageable.

Of course, if your goal is to get really intimate with a particular language, you'll want to fully implement a compiler for that language.

Upvotes: 2

Darius Bacon
Darius Bacon

Reputation: 15134

Another point in favor of Scheme: it's practical for a beginner to write a self-hosting compiler for it, like Kragen Sitaker's Ur-Scheme, his first compiler. There are few other 'tutorial' compilers powerful enough to compile themselves (though there are some pointers at the link). This brings more realism and interest to the problem.

Upvotes: 3

bendin
bendin

Reputation: 9574

If you want a compact tutorial, why not consider Wirth's Compiler Construction (pdf). The source language (Oberon-0) is simple enough to keep the compiler comprehensible. The implementation language (Oberon) should be readable to anyone who has done some programming.

As to which language to use to implement the compiler. Use something you are familiar with. When in doubt, choose a language that will not unnecessarily complicate the attempt: Something with garbage collection. Something that makes it easy to print or otherwise dump internal data structures for inspection. Python, Scheme and Lua all come to mind.

The final consideration is what to target with your compiler. The virtual machines JVM and CLR have been metioned, I'm sure. You could go that route. It might be easier, for a first attempt to use a simulator for a stripped-down RISC processor as your target. (Wirth's compiler book does this.)

I wouldn't recommend targeting x86 for your first compiler as it's hideous beyond words. I also wouldn't target a high(er) level language like C because you'll miss out on a lot of the interesting details, like how to implement short-circuit semantics for boolean operators and such like.

Upvotes: 4

joel.neely
joel.neely

Reputation: 30963

Pascal has already been mentioned, but I'd like to add that Niklaus Wirth's book Algorithms + Data Structures = Programs contains a complete implementation of a small Pascal-like language using recursive descent. If you're looking for a theory-intensive discussion of parsing, look elsewhere; but if you want straightforward code that lets you learn by doing, then I'd recommend A + DP = P.

Upvotes: 2

Cheery
Cheery

Reputation: 25463

Write a brainfuck or forth compiler. BASIC is perhaps also such language not too rich in features. I think C would be moderately hard. Do not envy about the target arch. Use whatever you have.

If you don't want to implement an assembler then put your compiler output assembly code and push it to gas or nasm.

Upvotes: 0

Adam Hawes
Adam Hawes

Reputation: 5449

I can't think of any one language that is simple enough to use as a first compiler-writing exercise. I don't think I'd try C for a first cut. Why not invent your own language? Maybe it'll be a real hit.

Upvotes: 1

SmacL
SmacL

Reputation: 22932

In terms of simplicity, FORTH is going to be one of the easier languages to develop. It's threaded interpretive rather than truly compiled, but you'll still be dealing with parsing, variable storage, etc..

For a compiler, I'd go with C or Pascal, both of which are quite compact and have source for compilers available.

Upvotes: 0

Tom Grove
Tom Grove

Reputation: 81

Whichever language you choose, you could consider compiling to intermediate language ( IL ) to target the Common Language Runtime ( CLR ). I presume targetting the Java Virtual Machine ( JVM ) would be similar for non-Windows, or prehaps the CLR implementation of in Mono? This would probably greatly simiplify the job and would let you have something that performed well from the off. You later re-target a specific architecture if you wanted to go further.

Upvotes: 1

Serafina Brocious
Serafina Brocious

Reputation: 30619

My suggestion is to pick your favorite language. The knowledge you have going into it will outweigh the difficulty of writing a compiler for it, typically.

Upvotes: 8

squadette
squadette

Reputation: 8306

Write a Scheme compiler.

See: An incremental approach to compiler construction

Upvotes: 9

Related Questions