Bootstrapping in Compiler

This is the 4th tutorial in the series... its about bootstrapping a compiler... how a compiler compiles itself?

1. Bootstrapping

2. Translator

3. Compiling a Compiler

4. Tombstone Diagrams D iagrams consist of a set of “puzzle pieces” that can be used to reason about language processors and programs. Different kinds of pieces. Combination rules (not all diagrams are “well formed ”).

5. Tombstone Diagrams The rules for T-diagrams are very simple. A compiler written in some language “C” that translates programs in language A to language B looks like this:-

6. Tombstone Diagrams

7. Tombstone Diagrams The combination rules of Tombstone diagrams can vary:

8. Tombstone Diagrams The combination rules of Tombstone diagrams can vary:

9. Tombstone Diagrams Compilation of C programs on an x86 machine:

10. Bootstrapping It refers to the seemingly impossible task of pulling oneself up by the bootstraps.

11. Bootstrapping The idea of bootstrapping is quite simple:- You write your compiler in language A (but still let it target B) and then let it compile itself. The result is a compiler from A to B written in B . In order to use the compiler to compile a program, we must already have compiled it, and to do this we must use the compiler. In a way, it is a bit like the chicken-and-egg paradox.

12. Bootstrapping Note that the languages match at every connection and that the source and target program aren't standing on anything , as they aren't executed in this diagram.

13. Bootstrapping The basic idea in bootstrapping is to use compilers to compile themselves or other compilers . Target -> we want a compiler for ML to Pentium machine code and want this to run on a Pentium . We have -> an ML-compiler that generates HP machine code and runs on an HP machine.

14. Bootstrapping One way of obtaining the desired compiler would be to do binary translation, i.e., Write a compiler from HP machine code to Pentium machine code . This is a very tedious and herculean task and some efficiency will be lost in it.

15. Bootstrapping A better solution is to write an ML-to-Pentium compiler in ML (a high-level language). We can compile this using the ML compiler on the HP :

16. Bootstrapping The output is: we get a program that converts ML code into P code and now written in HP machine code ( a new compiler ).

17. Bootstrapping Now, we can run the ML-to-Pentium compiler on the HP and let it compile itself i.e. – We input our original program to the newly generated compiler.

18. Bootstrapping Finally, we get the required compiler which converts ML code into P code and also written in P language (a low-level language).

19. Bootstrapping The whole process can be combined as follows:

20. Bootstrapping

21. Bootstrapping for Cross-compiler Cross-compiler: It’s a compiler which runs on one machine (the host machine) but emits code for another machine (the target machine ). T-diagrams can help generating cross-compilers. For example, a compiler that runs on a Windows 10  PC but generates code that runs on Android smartphone is a cross compiler.

22. Bootstrapping for Cross-compiler C “cross compiler” from x86 to PPC

23. Bootstrapping for Cross-compiler Two Stage Compilation: It is a combination of 2 translators. The output of the first translator is provided as input to the second translator.