This Turing award lecture by Ken Thompson on topic “Reflections on Trusting Trust” gives good insight about how C compiler was made in C itself.
Though I understand the crux, it still hasn’t sunk in. So ultimately, once the compiler is written to do lexical analysis, parse trees, syntax analysis, byte code generation etc, a separate machine code is again written to do all that on compiler?
Can anyone please explain with a small example of the procedure? Bootstrapping on wiki gives good insights, but only a rough view on it.
PS: I am aware of the duplicates on the site, but found them to be an overview which I am already aware
5
Lets say you are writing a new programming language named “XYZ”. The first step is to write a compiler for this language. Since this new language doesn’t exist yet, you write the compiler in… lets say java. We’ll call it jxyz. Doing this process is a typical class in college.
Now you have a java program (jxyz) that takes an XYZ source file and produces an executable. It is then possible to undertake writing a compiler for XYZ in XYZ that is complied by jxyz.
At this point, you have a complier for XYZ that was complied with jxyz. Well call this program ‘xyzFromJ’.
‘xyzFromJ’ should be able to take itself as an input and and compile itself completely removing anything created by jxyz from the dependencies and definition of the language. From this point on, any changes to the XYZ language can be done on the compiler written in XYZ and compiled using itself.
Step 1. Write your compiler in a different language.
Step 2. Compile the code from Step 1.
Step 3. Write your compiler in the same language.
Step 4. Compile the code from step 3.
Repeat Steps 3-4 for any further updates to your compiler.
Note that steps 1 and 3 may happen simultaneously or in a different order.
I admit that this is very much an oversimplification.
3
Unlike some other answers that suggest writing the compiler in some other language (presumable one that runs on the same machine you are targeting), it is also possible (actually preferable) to write the compiler in the target language from the beginning.
Say you want to write a compiler for C for an ARM processor. You already have a C compiler that runs on Windows (Intel architecture). You write your new compiler in C, both the front end (lexical analysis and parsing), and back end (code generation). The back end of course is written to generate code for the ARM, not Intel.
You then compile the source for the new compiler with the existing compiler. Once you are satisfied the compiler is generating valid code for the ARM, you take the compiled ARM code and run it on the target ARM architecture. You now have the source for the new compiler, that can be modified and fed into it’s executable and generate a new version.
This is process is called cross-compiling. The advantage is that you only have to write the compiler once.
from another answer:
Step 1. Write your compiler in a different language.
Step 2. Compile the code from Step 1.
Step 3. Write your compiler in the same language.
Step 4. Compile the code from step 3.
Steps 1 and 2 are only needed for the “first ever” compiler for a new language. There are lots of variations on steps 3 and 4, so for example you can write the code generator for a new architecture, cross compile, then run the same compiler on a new machine. Or you can extend your compiler to handle new syntax and constructs without using any of the extensions, then rewrite the compiler to use the extensions and compile itself.
0