41

Possible Duplicate:
How could the first C++ compiler be written in C++?

I know my question goes to the underground galaxy cave where languages are born and involves some lambda math and light-years of google-studying. But what kind of knowledge is necessary to create a language?

marked as duplicate by Matthieu, Dipan Mehta, Caleb, Jarrod Roberson, vartec Mar 26 '12 at 16:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 22
    Possible duplicate: "Chickens come from eggs but eggs come from chickens, how is this possible?" :) – George Duckett Mar 26 '12 at 15:48
  • 1
    1st appear: "the CREATOR", 2nd to get in: "the egg." 3rd and last "the chicken" . Learned from this guys, they are very funny! – H_7 Mar 26 '12 at 16:09
  • 2
    Unless you are from the Star Wars universe (where parsecs are apparently units for measuring time and not distance), you could change that to "years of google studying" :-) – Francesco Mar 26 '12 at 16:35
  • 1
    @Francesco I am from Star Wars universe, nice to meet you. – H_7 Mar 26 '12 at 22:00
  • 1
    Vote to reopen, the best answer in the other question seems fairly C++ specific. C != C++. Also, the question here seems like it might be a tad more general. – Doug T. Mar 27 '12 at 21:45
77

Look up "bootstrapping".

Basically you start with a very minimal process/set of functions that can be used to compile the code that defines a slightly more functional compiler. This creates your next compiler which then can then be used to build code that can do even more. You repeat this process until you have a full blown compiler that can compile all the language features.

The other alternative is to write the first version of the compiler in a different language and then write the next version in your target language.

  • 3
    I've always been baffled by the idea of a compiler being able to compile itself, but that cleared it up quite a bit. Thanks! – Andy Hunt Mar 26 '12 at 15:07
  • 1
    The very first compiler may be written in another language too, and then rewritten as soon the new compiler has enough features. – marcus Mar 26 '12 at 15:10
  • 4
    It would be really interesting to see a list of self-compiling languages, as well as the languages they were originally written in. – Plutor Mar 26 '12 at 15:23
  • 3
    @mcmcc That would be the scenario described in Reflections on Trusting Trust, written by Ken Thompson. Whether or not anyone's actually snuck code like that into a mainstream compiler is questionable. – Tacroy Mar 26 '12 at 15:53
  • 7
    When two compilers love each other very much... – Joe Mar 26 '12 at 22:41
22

ChrisF's answer is excellent, but I wanted to add this example that always stuck by me after my computer science course on bootstrapping.

Suppose you have a basic C compiler that does not support escape codes for strings yet, and you wanted to add that. You could add a snippet of code similar to this:

if( str[i] == 0x5c ) {       // ASCII code for backslash
   switch( str[i+1] ) {
      case 'n': return 0x0a; // ASCII code for new line
      case 't': return 0x09; // ASCII code for tab
      // ...                 // more ASCII code for other escapes
      default: return str[i+1];
   }
}

After you have added this to the compiler, and generated a new compiler binary, you could then rewrite this into:

if( str[i] == '\\' ) { 
   switch( str[i+1] ) {
      case 'n': return '\n';
      case 't': return '\t';
      // ...
      default: return str[i+1];
   }
}

That would remove any knowledge about ASCII codes from the compiler source code, but the compiler would still magically generate the correct codes.

18

Bootstrapping is definitely the standard way to build a compiler today. But remember that you don't need a compiler or interpreter to write a program in a language. For instance, Christopher Strachey wrote a famous AI program that was able to play Checkers in CPL before there was a compiler for CPL. He had to translate the program to machine code "manually", which is tedious and error-prone, but not really difficult (that's why computers can do it so well).

  • 2
    That would be named the "human compiler", right? – ypercubeᵀᴹ Mar 26 '12 at 15:52
  • 9
    its not really accurate to say there was no compiler, manual compilation makes you the compiler. – Ryathal Mar 26 '12 at 15:55
  • 2
    @Ryathal: According to wikipedia, "A compiler is a computer program (or set of programs) that transforms source code ...". So, since a human being isn't a computer program, a human can't be a compiler ;-) – nikie Mar 26 '12 at 16:47
  • 1
    Wikipedia can't possibly be wrong – Chris Nov 23 '15 at 4:03
10

I hope this is not out of topic, but I wanted to point out that, once you have one C compiler for one platform X, bootstrapping for other platforms can be done by using cross-compilation:

  • You have a C compiler c1 for architecture X that runs on architecture X.
  • You write a C compiler c2 for architecture Y, written in C.
  • You compile the compiler c2 on X using c1 and obtain the binary for compiler c2 that runs on X.
  • You use the binary for c2 that runs on X to compile itself and obtain a binary of c2 that will run on Y.

In other words, when you have the first egg, it is easy to make more eggs.

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