Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've been very interested in writing compilers but have been scared off by the complexity of it. I've finally took the plunge and started writing my first compiler and the language I picked is Brainf*ck as I think that it would relatively easy to implement and I could implement the full language.

This brings me to a question: does the source language matter? Should I be using a "real-world" language and just use a subset of the language (such as a subset of C/Java/etc.)? Is there any benefit to starting with a non-real world language (aka "esoteric")?

share|improve this question

closed as primarily opinion-based by Ixrec, durron597, MichaelT, GlenH7, Snowman May 21 at 16:35

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

I suggest you write a couple interpreters before writing your first compiler. There is a major overlap of the set of problems but you are safe from some of the gory OS details. –  SF. Jul 11 '11 at 8:37
Another intermediate step is to build your own VM (in e.g. C++), and a compiler targetting that. That too shuffles the gory OS details to the commercial compiler. –  MSalters Jul 11 '11 at 10:29
@SF. you can also use an existing backend, like gcc or llvm, as long as you write the compiler in C++. I guess there are backends for other languages too. –  Matthieu M. Jul 11 '11 at 18:15
Brainfuck is indeed very easy to implement. You don't even need to have notions about how compilers work. What you could do is create a language and compile it down to brainfuck. That actually would be a good challenge. –  marco-fiset Sep 24 '12 at 19:26

7 Answers 7

up vote 2 down vote accepted

Yes, the language matters. Brainfuck (to use your example) is so trivial, it barely qualifies as a language. In particular, each significant character of input is (almost) a complete command in itself. Since you don't have "statements" (at least in the normal sense of the word) an implementation doesn't need (or have any use for) a parser.

Given that the parser is pretty much the core of a typical compiler or interpreter, implementing a language that doesn't need/use a parser doesn't teach you much about implementing a more conventional language for which a parser is/will be necessary.

share|improve this answer
thanks Jerry for answering my question by using my example. –  Jetti Jul 11 '11 at 12:58

Judging by Jon Skeet's Hello World Language, I'm pretty sure some languages are easier to implement than others.

On a more serious note, I would not go for something incredibly complex right off the back. It is possible to create your own language or do a subset of one. Doing, for example, C++, is suicide, whereas something like a lisp-dialect is more manageable due to the lack of a complicated syntax.

share|improve this answer
There are also various resources for writing your own LISP interpreter, there is also a nice book about writing compilers for lazy functional programming languages research.microsoft.com/en-us/um/people/simonpj/papers/… –  Gabriel Ščerbák Jul 10 '11 at 22:01
@Gabriel simonpj is one of the ghc authors, correct? –  alternative Jul 10 '11 at 22:02
I am not sure if exactly ghc, but definetely Haskell and I think he did some work on F# too. –  Gabriel Ščerbák Jul 10 '11 at 22:05
@mathepic - Yes, Simon Peyton-Jones is one of the GHC authors, and has been deeply involved in the development of Haskell since (I think) its inception. Certainly the early days of Haskell, anyway. –  Steve314 Jul 10 '11 at 23:55
As far as I know, Walter Bright is the only person to ever successfully implement C++ on his own, without a large team. So, C++ is probably not a good choice for your first (or really any) compiler. –  Jörg W Mittag Apr 5 '14 at 14:44

Yes, the syntax definitively matters. But you don't have to write a compiler for an existing language, you can design your own language and make it as complex as you wish.

Start with a simple grammar for assignments, expressions, if, while, read and print, then continually add to it. You don't even need functions at the beginning.

share|improve this answer
that is not a good idea - it is very easy to come up with something which is not that easy to implement - langauge design takes experience –  Gabriel Ščerbák Jul 10 '11 at 22:02
@Gabriel: I don't see a problem in that. If a feature is too hard to implement, he doesn't have to. Starting from an easy basic language and adding features, he has a nice slow increase in difficulty. –  Otto Allmendinger Jul 10 '11 at 22:08
ok, as a beginner he might easily come up with a grammar which is not easily parseable and because he might not be familiar with formal languages, he would struggle to find out what is wrong and how to solve it - it is imho demotivating to dive deep into parsing theory to write your first compiler –  Gabriel Ščerbák Jul 10 '11 at 22:15
Okay, fair point. I'll edit my answer. –  Otto Allmendinger Jul 10 '11 at 22:27
@Gabriel - does that matter? The first language will certainly be a throwaway learning exercise anyway. It should certainly help to have books on theory etc, but it's amazing how many real-world compilers use minor variations on recursive descent, so some experience with that improvised parsing style is probably valuable anyway. –  Steve314 Jul 10 '11 at 23:35

I'd say that it does matter what the source language is. The type of parsing and lexing you'll have to do can vary enormously, from ultra-ambiguous, multi-pass (C++), to LALR(1) with feedback from parser to lexer (C), to LL(1) (Pascal).

You should decide up-front what you want to learn: language design, lexing, parsing, intermediate representation, code generation, assembly, object file formats. All are legitimate objects of study. But if you don't care to learn about parsing, you're best sticking with a source language that's LL(1), and using RDP (http://www.cs.rhul.ac.uk/research/languages/projects/rdp.html) or some other system, to generate the parser code.

You should also decide when your project should end. Something like: "the assembler is done when it can be substituted for GNU as when I compile source code blahblah". Without that kind of marker, you can go on for ever polishing your code and never learning anything new.

share|improve this answer
Thank you, I didn't even stop to think about the constant polishing with no learning...chances are I would've fallen in that trap (I'll have to make a conscious effort not to do so). –  Jetti Jul 11 '11 at 1:53

I would recommend the famous dragon book http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools. There is also a similar book, but with complete sources in Java.

share|improve this answer
I forgot to mention, that I do have the dragon book (the 1st edition though). –  Jetti Jul 10 '11 at 22:15
@Jetti: then just read and proceed, the book is quite good:) –  Gabriel Ščerbák Jul 10 '11 at 22:17
I wish they made it for ebook! I don't have much time to read physical books (that aren't textbooks). I've thought of getting Writing Compilers And Interpreters: A Software Engineering Approach –  Jetti Jul 11 '11 at 2:11
@Jetti: you can find scanned and ocr'ed version in the world of torrents;) –  Gabriel Ščerbák Jul 11 '11 at 9:46

Compiling a real-world language will help. For one, you have access to many programs that you can use to test, prove correctness and benchmark your compiler. If you narrow down to one target OS, one target platform, one host OS, one host platform, many complexities should be gone.

If the language you choose is small, yet Turing complete, your learning exercise or your experience of writing your first compiler will teach you something at each phase of compilation from lexical analysis, to, code generation and perhaps code optimization. This way, you will get a chance to discover which part of compiler you like so much and focus more on it in future.

share|improve this answer
The second paragraph is one of the reasons why I chose BF as the source language. Thank you for your answer –  Jetti Jul 11 '11 at 2:00

The tools available now to help you write a compiler are very good, so it isn't really that difficult. Tools to help with scanning and parsing are particularly obvious. There are some tools to help with AST handling (treecc, for example, is a simple AST-nodes-with-multiple-dispatch-operations tool).

Perhaps more importantly, there's back-ends like LLVM.

If you look at the LLVM tutorial (http://llvm.org/docs/tutorial/) you'll find it starts with a simple pure functional language, then adds mutability etc later. The reasons relate to the Static Single Assignment form which is, I believe, quite widely used in compilers - not just in LLVM. Though I'm no expert, so I could easily be wrong.

So it probably does make a difference which kind of language you start with for reasons of intermediate-code handling, as well as the parsing issues that other answers have already mentioned. The easiest first steps probably depend on what kind of intermediate code you generate, and the abstract machine model it's based on. And starting with a pure functional language is probably a good idea in general.

BTW - "pure functional" here doesn't necessarily imply first-class functions, higher-order functions etc. Evaluating arithmetic/logic expressions may be all you need before you start adding imperative stuff.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.