5

I'm thinking of writing a compiler in haskell, and just to gain some knowledge and experience, I will try to implement compilers for existing languages. Could someone give me a list of languages which are suitable for this?

Thanks in advance

Improve this question
5
  • 2
    For an easy start, you could begin with math terms (with multiple variables inside). Commented Dec 19, 2010 at 18:06
  • 1
    For added fun, make your compiler output bytecode for a virtual machine, like Java's or Python's. Commented Dec 19, 2010 at 18:19
  • Lua is not quite compileable, it's too dynamic. Of course it's still possible to compile it efficiently, but that will involve some advanced techniques. Commented Dec 20, 2010 at 10:50
  • @khachik: ASM does not get compiled, it is assembled. Commented Feb 20, 2012 at 7:28
  • @J.M.Becker: A compiler is a program that translates a program in language X into a semantically equivalent program in language Y. An assembler most certainly does exactly that, so an assembler is a compiler, and assembling is compiling. It's just that an assembler is not a very interesting compiler, since assembler is designed to map 1:1 to object code, so an assembler is more or less a simple lookup table. Commented Jun 16, 2019 at 15:59

7 Answers 7

Reset to default
8

Pascal could be a good start - you can compile it in a single pass. A subset of Lisp might be useful in order to grasp the idea of the lambda lifting. ML or even a subset of Haskell might help you in understanding the type inference. Consider using LLVM as your back-end, it will save you some time on implementing boring stuff.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Niklaus Wirth was proud of the fact that while each of Pascal's successor languages fixed some problems with the predecessors, was more expressive, safer, and in some sense "more powerful", it was also simpler. So, Pascal's successors (Modula-2, Oberon, the latest one being Component Pascal) might be even better languages to write a compiler for than Pascal.
"Consider using LLVM as your back-end, it will save you some time on implementing boring stuff" - I find the backend the most interesting :)
@xilpex, by boring stuff I mean the very end of the back-end - instruction selection, instruction scheduling, etc. Of course you can spend few years (I did...) implementing your own equivalent of the TableGen infrastructure, but in general it's a solved problem anyway and should be maintained by the hardware vendors, not compiler developers. You cannot possibly follow all the microarchitecture details on your own.
You implemented your own full backend!?
@xilpex yes, because I had to target a custom (and very peculiar) ISA.
7

Scheme is often used for this. There's even a tutorial called Write Yourself a Scheme in 48 hours for Haskell.

Improve this answer

Comments

4

The simplest languages to write compilers for are existing "esoteric languages", like brainfuck, because they have the smallest instruction set and the simplest grammar. You can try your hand at a more complex language, but it's better to get the fundamentals down with something simple before moving any further.

Improve this answer

Comments

3

The world always needs another c compiler :)

Improve this answer

2 Comments

I'd agree with this except for the fact that C has all the K&R legacy support that hardly anyone uses. Because of that, I'd recommend looking elsewhere. Remember, C was designed to make the compiler easy to write, which is why you have 3 ways to add 1 to an integer.
Ya, it was intended as humor. But it's not that unreasonable. You could use the Small C compiler. It's small enough to be able to implement, and you can use existing implementations as a basis for unit tests.
3

Oberon-2. Like Lua has short context-free grammar.

P.S. Here you can find Oberon-2 compiler written in Objective Caml.

Improve this answer

Comments

2

PL/0 is a simple language that was created to teach compiler construction. Samuel Williams wrote a compiler for it in Python (along with a virtual machine) for the benefit of students: http://www.oriontransfer.co.nz/learn/pl0-language-tools/index

Improve this answer

Comments

1

As far as I know one of the easiest languages to compile is Forth. I think it's quite achievable to write a compiler for Forth in Forth even for a relative novice.

Improve this answer

1 Comment

Forth should be implemented in Forth. It's not that interesting to write a Forth compiler in Haskell - in this case something like Cat or Joy would be more appropriate.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.