Does the source language matter for your first (few) compilers? [closed]

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.