30

Possible Duplicates:
implementing a compiler in “itself”
Bootstrapping a language

How can you write a compiler in the same language as the language you're writing that compiler for? Isn't that sort of recursive?

Edit: This may be deleted, but otherwise... :

How to bootstrap:

Why to bootstrap:

Community
  • 1
  • 1
froadie
  • 79,995
  • 75
  • 166
  • 235
  • 2
    Various earlier versions and related links: http://stackoverflow.com/questions/13537/bootstrapping-a-language http://stackoverflow.com/questions/1493747/bootstrapping-a-compiler-why http://stackoverflow.com/questions/193560/implementing-a-compiler-in-itself http://stackoverflow.com/questions/1173780/programming-language-and-compiler http://stackoverflow.com/questions/2035838/what-language-do-they-build-other-languages-with http://stackoverflow.com/questions/2740994/what-is-the-language-of-compilersare-they-written-with-different-languages The word you wanted was "bootstrapping". – dmckee --- ex-moderator kitten Jun 08 '10 at 15:29
  • I wonder how often people implement compilers for mainstream languages using esoteric ones. – JAB Jun 08 '10 at 15:33
  • @Phil Ross - wow, thanks, how'd you find that? wasn't sure how to search :) – froadie Jun 08 '10 at 15:36
  • 1
    I searched for compiler bootstrapping using the search box in the top right. – Phil Ross Jun 08 '10 at 20:59

6 Answers6

40

Generally the first version of the compiler is written in a different language, and then each subsequent version is written in that language and compiled with the older version. Once you've compiled version x with version x-1, you can use the newly built version x to recompile itself, taking advantage of any new optimizations that version introduces; GCC does its releases that way

Michael Mrozek
  • 169,610
  • 28
  • 168
  • 175
  • +1 I've built a simple Lisp interpreter in JAVA. – Achilles Jun 08 '10 at 15:30
  • 1
    so... why can't you just use the first version of the compiler? Why would you want a double-level compiler? – froadie Jun 08 '10 at 16:08
  • 5
    @froadie You mean why not compile every version with version 1? Usually new versions of a compiler generate better machine code than the previous versions, so building with the newest version will make the compiler itself as fast/efficient as possible. Also if the language itself is changing and you want to use those newer features in the compiler's source code, you'll need to build with a more recent version – Michael Mrozek Jun 08 '10 at 20:36
  • @MichaelMrozek that's pretty cool, are you saying that all languages derive from assembly? – CMCDragonkai May 28 '14 at 14:21
  • @froadie see this q [bootstrapping-a-compiler-why?](http://stackoverflow.com/questions/1493747/bootstrapping-a-compiler-why?lq=1) – nawfal Jul 23 '14 at 07:50
  • @nawfal - I added a link to that question in my question itself shortly after asking the question several years ago – froadie Jul 23 '14 at 19:20
  • @froadie oh yes, I missed it... – nawfal Jul 23 '14 at 19:26
17

It is. You usually need a bootstrap version of the language either compiled or interpreted from another language.

And to bend your mind a little more, years ago I read the history of a Pascal compiler written as a grad student project. It written in Pascal and compiled with the system's built-in Pascal compiler. Eventually, it was good enough to replace the system's built-in Pascal compiler. Unfortunately, they found a bug in code generation, but the fix for the code generator triggered the bug in the compiler, generating a bad compiler. To fix it required hand-patching the binaries from the installed compiler to then apply the patch to the source to replace itself.

plinth
  • 48,267
  • 11
  • 78
  • 120
  • I found this question wondering exactly what one would do in this kind of bug situation. Hand-patching had not occurred to me. Funny story. haha – GabrielF Jul 27 '17 at 19:40
8

It's only a problem for the very first version ever. Once I have V1.0 of the compiler working I can write V2.0 in my language and use the V1.0 compiler to compile it. Then I can write V3.0 and use V2.0 to compile that, use V3.0 to compile V4.0 and so on.

eemz
  • 1,183
  • 6
  • 10
  • Did you mean V0.1? The first version will lack important features and doesn't qualify to be versioned as 1.0 – darw Oct 18 '20 at 09:53
3

The first pass of the compiler is normally written in something else until the language is well-formed enough to be able to compile it's own compiler, then you can get into the x is written in x.

Lazarus
  • 41,906
  • 4
  • 43
  • 54
2

At some point, you need a compiler (or interpreter) written in a different language. But it doesn't need to be efficient and can be done in a language that makes parsing and prototyping easy (LISP is popular). Once you have used this to compile the "self-compiler", you can discard it and use the result.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • 2
    Not necessarily. The very first "compiler" can also be a human, in which case you do not need a bootstrap compiler in a different language *at all*. This is how the first compilers for most of Niklaus Wirth's languages were written: he basically assigned them to his students :-) – Jörg W Mittag Jun 08 '10 at 17:51
1

At the very beginning, the real first compiler of that language, was written not in that language of course. Very second could be written in that language. Moreover, given a spec of a language, you can implement a basic core in a bootstrap compiler, and then write the full compliant compiler in that language using the subset understood by the "bootstrap" compiler. Second generation compilers can forget "bootstrap" compiler too.

ShinTakezou
  • 9,432
  • 1
  • 29
  • 39