Class Notes

Compiler Overview

Compilers vs. Interpreters

• Pure Compiler Implementation

• pure interpreter implementation

• hybrid pseudo-code implementation

Compiler Compilers

Using a compiler compiler, such as LEX/YACC to create a compiler from a language description.

A compiler compiler system may also be used to create an interpreter.

Bootstrapping

A compiler is characterized by three languages:

1. Source Language
2. Target Language
3. Implementation Language

Notation: ${}^S C^{T}_I$ represents a compiler for Source $S$, Target $T$, implemented in $I$. The T-diagram shown above is also used to depict the same compiler.

To create a new language, L, for machine A:

1. Create ${}^S C^{A}_A$, a compiler for a subset, S, of the desired language, L, using language A, which runs on machine A. (Language A may be assembly language.)

   

2. Create ${}^L C^{A}_S$, a compiler for language L written in a subset of L.

3. Compile ${}^L C^{A}_S$ using ${}^S C^{A}_A$ to obtain ${}^L C^{A}_A$, a compiler for language L, which runs on machine A and produces code for machine A.

$${}^L C^{A}_S \rightarrow {}^S C^{A}_A \rightarrow {}^L C^{A}_A$$

The process illustrated by the T-diagrams is called bootstrapping and can be summarized by the equation:

$$L_{S}A + S_{A}A = L_{A}A$$

To produce a compiler for a different machine B:

1. Convert ${}^L C_{S}^A$ into ${}^L C_{L}^B$ (by hand, if necessary). Recall that language S is a subset of language L.
2. Compile ${}^L C_{L}^B$ to produce ${}^L C_{A}^B$, a cross-compiler for L which runs on machine A and produces code for machine B.
3. Compile ${}^L C_{L}^B$ with the cross-compiler to produce ${}^L C_{B}^B$, a compiler for language L which runs on machine B.

Figure 1.5. Language Processing System (Aho[2])

Compiler Phases

Figure 1.7. Translation Example [ALSU]
Figure 1.7. Translation of Assignment Statement

Syntax-directed Translation

Figure 2.1. Code Example [ALSU]

{
    int i; int j; float[100] a; float v; float x;

    while ( true ) {
        do i = i+1; while ( a[i] < v );
        do j = j-1; while ( a[j] > v );
        if ( i >= j ) break;
        x = a[i]; a[i] = a[j]; a[j] = x;
    }
}

Figure 2.2. Intermediate code for code example [ALSU]

 1:  i = i + 1
 2:  t1 = a [ i ]
 3:  if t1 < v goto 1
 4:  j = j - 1
 5:  t2 = a [ j ]
 6:  if t2 > v goto 4
 7:  ifFalse i >= j goto 9
 8:  goto 14
 9:  x = a [ i ]
10:  t3 = a [ j ]
11   a [ i ] = t3
12:  a [ j ] = x
13:  goto 1
14:

Figure 2.10: SDD for infix to postfix translator [ALSU].
Figure 2.9: Annotated parse tree [ALSU].
Figure 2.35: Postfix translator specification [ASU].
Figure 2.38: Translation scheme with left-recursion removed [ASU].
Figure 2.21: Evaluation of attributes [ASU].
Figure 2.37: Token descriptions [ASU].
Figure 2.36: Postfix translator organization [ASU].
Postfix translator source code [ASU]

Lexical Analysis

• Strings
  
• Languages
  

Syntax Analysis

Syntax-Directed Translation

Code Generation