I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone provide some better explanation, analogy or an example to relate with some real world compiler?

Some notation first. By $LSN=$ enter image description here I mean a compiler for language $L$ written in language $S$ that produces output language/machine code $N$. This is a tombstone or T-diagrams.

Compiling a Compiler

  1. Suppose we have cross-compiler for a new language L in implementation language S generating code for machine N.

    T-diagram for LSN

  2. Suppose we also have an existing S compiler running on machine M implementing code for machine M:

    T-diagram for SMM

  3. Run LSN through SMM to produce LMN

Compiler Construction

T-diagram for LMN = LSN + SMM


migrated from cstheory.stackexchange.com Apr 15 '12 at 6:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ I added some T-diagrams, which should actually make it easier to understand what's going on. Hopefully someone can fine a better way of rendering them. $\endgroup$ – Dave Clarke Apr 15 '12 at 9:07

The T-diagrams (which you had omitted from the original version of your question) are crucial for understanding this sort of question. Let's look at the last T-diagram.

enter image description here

The first T describes a compiler from L to N written in S.

The second T describes a compiler from S to M written in M (or running on M). This will be your compiler compiler.

Applying the second T to the first T compiles the first T so that it runs on machine M. The result is thus a compiler from L to N running on machine M.

The fact that the second T also runs on machine M is captures that you are running the compiler compiler on the machine which you will run the compiler, rather than having to use a cross compiler (which would be the case if the bottom M were different).


It means that we compile LSN with SMM, that is, run source code of LSN through SMM.

When SMM compiles some source code, it produces an executable for machine M, so when we compile LSN with SMM we get LMN - an executable, which compiles L source files on machine M in order to produce executables for machine N.

Perhaps it would be easier to understand this with an analogy. Supppse we have a C compiler cc which is written in Fortran, which generates ARM code. Suppose we also have a Fortran compiler fc on our x64 computer. If we compile cc source code with fc we get a program which runs on x64, compiles C programs, but produces executables for ARM.


To make it simple....

Note: Remember Compiler can run only on a low level language.

In 1st Diagram,compiler is written in HLL(High Level Langg) so inorder to run that on a machine the implementation langg of compiler should be in LLL.

So,in 2nd Diagram,the Implementation langg of compiler is ran on a self Resident compiler such that the target code can run on its own machine.

Finally ,combining both of them the compiler runs on a machine with langg--M

input langg--L

output Langg--N


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy