5

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")?

4
  • 3
    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.
    Commented Jul 11, 2011 at 8:37
  • 1
    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
    Commented Jul 11, 2011 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. Commented Jul 11, 2011 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. Commented Sep 24, 2012 at 19:26

7 Answers 7

3

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.

1
  • thanks Jerry for answering my question by using my example.
    – Jetti
    Commented Jul 11, 2011 at 12:58
5

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.

1
  • 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
    Commented Jul 11, 2011 at 1:53
4

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.

5
  • 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/… Commented Jul 10, 2011 at 22:01
  • @Gabriel simonpj is one of the ghc authors, correct? Commented Jul 10, 2011 at 22:02
  • I am not sure if exactly ghc, but definetely Haskell and I think he did some work on F# too. Commented Jul 10, 2011 at 22:05
  • 1
    @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.
    – user8709
    Commented Jul 10, 2011 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. Commented Apr 5, 2014 at 14:44
3

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.

1
  • The second paragraph is one of the reasons why I chose BF as the source language. Thank you for your answer
    – Jetti
    Commented Jul 11, 2011 at 2:00
2

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.

5
  • 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 Commented Jul 10, 2011 at 22:02
  • 1
    @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. Commented Jul 10, 2011 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 Commented Jul 10, 2011 at 22:15
  • Okay, fair point. I'll edit my answer. Commented Jul 10, 2011 at 22:27
  • 1
    @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.
    – user8709
    Commented Jul 10, 2011 at 23:35
1

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.

0

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.

4
  • I forgot to mention, that I do have the dragon book (the 1st edition though).
    – Jetti
    Commented Jul 10, 2011 at 22:15
  • @Jetti: then just read and proceed, the book is quite good:) Commented Jul 10, 2011 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
    Commented Jul 11, 2011 at 2:11
  • @Jetti: you can find scanned and ocr'ed version in the world of torrents;) Commented Jul 11, 2011 at 9:46

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