3.1 Design Options
3.1.1 Bootstrapping
The concept of bootstrapping originally refers to a story about a man being able to fly by pulling himself up in his bootstraps [6]. The term has been used later on to describe the idea of creating a new tool using the tool itself.
The way it is typically done is by creating a simple version of the new tool by hand or other simple tools, and then use the simple version of the tool to create a more advanced version of a tool.
In the development of a language processor, the idea is to develop a language processor for a language using the language itself. First a primitive version of the language processor is created by hand, then this version is used for creating a more advanced version of the language processor.
The term has been widened to the concept of processing a language pro-cessor using itself. The process may be used for creating a compiler from scratch, for optimizing a compiler, creating a true compiler from a portable compiler, or creating a compiler generating another target language. It is the development of a language processor from scratch and optimizing a language processor, which are of interest in this project and these two processes will be covered in the following.
Tombstone Diagrams
The application of a language processor on either programs or other language processors can be clearly illustrated by tombstone diagrams. The different kinds of diagrams will be briefly introduced in following. A more extensive covering can be found in [19].
An ordinary program is represented by a round-topped tombstone with the name of the program in the head of the tombstone and the implementa-tion language program at the base of the tombstone, an example of a program is shown in Figure 3.1.
Figure 3.1 A program P implemented in C.
P
C
A machine, which may execute a program, is represented by a pentagon pointing downwards with the name of the machine code language it is able to execute inside of it, an example of a machine is shown in Figure 3.2.
An interpreter is represented by a rectangular tombstone with the guage interpreted at the top of the tombstone and the implementation lan-guage at the base of the tombstone, an example of an interpreter is shown in Figure 3.3.
A translator or compiler is represented by a T–shaped tombstone with source language at the left, the target language at the right and the
imple-Figure 3.2 A machine running machine code M.
M
Figure 3.3 An interpreter interpreting P implemented in I.
P I
mentation language at the base of the tombstone, an example of a translator is shown in Figure 3.4.
Figure 3.4 A translator translating from S into T implemented in I.
S T
I
Translation of a program using a translator can be illustrated by putting the program to be translated to the left of the translator and the result to the right of the translator. An example of this is shown in Figure 3.5. The implementation language of the program to the left must match the source language of the translator. The implementation language is then changed by the translator to represent a program with a new implementation language to the right. If a machine or a combination of a machine and an interpreter can execute a language then a program with that implementation language may be executed.
A translator is also a program and may be translated using a translator, which is a program and must be executed using a machine of a combination
Figure 3.5 A Java program P being translated to Java Byte Code (JBC) using a Java to JBC translator implemented in C.
P
Java
P
Java JBC JBC
C
of a machine and an interpreter. An example of this is shown in Figure 3.6.
Figure 3.6An RSL to Java translator implemented in Java being translated into a RSL to Java translator implemented in JBC, using a Java to JBC translator implemented in JBC interpreted by a JBC to M interpreter on a machine M.
M JBC
M
Java JBC
JBC
RSL Java
Java
RSL Java
JBC
The tombstone diagrams can also be used to describe a multistage com-piler by putting the comcom-pilers adjacent to each other separated by a program expressed in the intermediate language, an example of a multistage compiler is shown in Figure 3.7.
Full Bootstrapping Process
The full bootstrapping process is used for developing a new compiler from scratch. An advantage of the full bootstrapping process is that at the end of the process, the compiler is expressed in the source language, for which it is developed i.e. maintenance and extension of the compiler do not depend on any other languages. The development of the Java compiler will be used as
Figure 3.7 A two–stage compiler compiling from Java to M with JBC as intermediate language.
P
Java
P
JBC
P
Java JBC M
Java
JBC M
Java
an example. The Java source code comes in different versions in this context.
The first version is a small subset which is named Javas. The target language of the compiler is JBC (Java Byte Code). An interpreter for JBC is assumed available, and therefore JBC is assumed to be executable.
The first step of the process is to develop a compiler for the small subset Javas in a language, for which a compiler is already available. The language used for developing the Java compiler was C [19]. The compiler is shown in Figure 3.8.
Figure 3.8 A compiler for Java0 into JBC implemented in C.
Javas JBC
C
This compiler for Javas is compiled using the available compiler for the implementation language. The result is an executable compiler for Javas. The compilation is shown in Figure 3.9.
The second step of the bootstrapping process is to write a second version of the compiler. The second version is written in the source language Javas, as shown in Figure 3.10. The second version of the compiler is then compiled using the first version, as shown in Figure 3.11.
The third and final step is to extend the second version of the compiler to the full language. The third version of the compiler is shown in Figure 3.12. The third version is compiled using the second version, as shown in Figure 3.13. The result is a compiler for the full source language written in some subset of the source language. There are no dependencies on other languages. The third version of the compiler may be used to compile new
Figure 3.9 Compilation of the developed compiler.
M
C M
M
Javas JBC
C
Javas JBC
M
Figure 3.10 Second version of the compiler written in Javas.
Javas JBC
Javas
Figure 3.11 Compilation of the second version of the compiler.
Javas JBC
JBC
Javas JBC
Javas
Javas JBC
JBC
M JBC M
versions of the compiler itself.
Optimization Using Bootstrapping
Bootstrapping can also be used to optimize a compiler. The optimization has two purposes:
Figure 3.12 Third version of the compiler extended to the whole source language.
Java JBC
Javas
Figure 3.13 Compilation of the third version of the compiler.
Javas JBC
JBC
Java JBC
Javas
Java JBC
JBC
M JBC
M
1. Producing better programs, i.e. higher quality of code in the target language.
2. Improving the compiler itself, i.e. the efficiency in the compilation process.
The starting point for the optimization process is a compiler expressed in source language as well as in low quality target language. In this section optimization of an RSL to Java translator will be used as example. Java is assumed to be executable in this context. Both versions of the translators are shown in Figure 3.14. The quality of the target language is indicated by superscript low and high on the arrow of the translator and as subscript under the tombstone base.
The first step is to modify the first version of the translator implemented in the source language to produce higher quality target language, as shown in Figure 3.15.
The new version of the translator is translated using the executable ver-sion of the first translator, which is shown in Figure 3.16.
Figure 3.14 Left: Translator implemented in the source language. Right:
Translator implemented in the target language.
Low
RSL Java
Java
Low
RSL Java
RSL
Low
Figure 3.15The modified translator producing high quality target language.
High
RSL Java
RSL
Figure 3.16 Translation of the new version of the translator using the first version.
RSL Java
Java High
RSL Java
RSL
RSL Java
Java
Low High
Low
Low
The result of the translation of the second version of the translator is a translator producing high quality target language. However, the executable version of the translator is still implemented in the low quality target lan-guage. This is fixed by translating the second version of the translator using the executable version of itself, as shown in Figure 3.17.
The result of this is a translator producing high quality target language implemented in high quality target language.