Compiler Grundlagen

Category: 

Ein Compiler übersetzt den Code einer Sprache in den einer anderen Sprache. Klassische Compiler übersetzen dabei den Programmcode in Maschinencode, welcher direkt vom Computer ausgeführt werden kann. Manche Sprachen, wie z.B. Java und C# erzeugen Bytecode, welcher von einer virtuellen Maschine ausgeführt wird oder auch beim ersten starten in Maschinencode übersetzt wird.

Spracheigenschaften

Die Eigenschaften von Programmiersprachen werden in vier Ebenen unterteilt:
  1. Tokens/Grundsymbole (Bezeichner, Zahlen, ...)
  2. Syntax (Struktur des Programms)
  3. Statische Semantik (Zusammenhänge die zur compile time bekannt sind)
  4. Dynamische Semantik (Auswirkungen zur Laufzeit)

Die ersten drei Ebenen werden vom Compiler überprüft, während der vierte Punkt nur die Laufzeit betrifft und somit nicht vom Compiler geprüft werden kann.

Compiler Phasen

Compiler sind üblicherweise in vier Phasen aufgeteilt:

  1. Lexikalische Analyse: Tokens erzeugen
  2. Syntaktische Analyse: Syntax prüfen und Syntaxbaum erzeugen
  3. Semantische Analyse: Namens- Typanalyse
  4. Transformation: Code Erzeugung

Lexikalische Analyse

Der Programmcode ist erst einmal nichts weiter als eine Folge an Zeichen, welche bisher noch keine Bedeutung haben.
Als erstes wird der Zeichenstream in sogenannte Tokens zerteilt, welche jeweils einzelne Ausdrücke darstellen.
Typischerweise betrachtet man die folgenden vier Klassen von Grundsymbolen:

  1. Bezeichner (z.B. Variablennamen)
  2. Literale (Zahlen, Strings, true/false, etc.)
  3. Wortsymbole (Schlüsselwörter wie z.B. class)
  4. Spezialsymbole (z.B. +, {, ...)

Diese Tokens werden meistens durch reguläre Ausdrücke beschrieben.

//Beispiel Bezeichner:
ident = Letter (Letter | Digit)*

//Beispiel Integer
integer = [-/+] Digit (Digit)*

Typischerweise wird aus diesen regulären Ausdrücken ein endlicher Automat erzeugt, welcher schnell und effizient die Tokens erkennt. Für jeden Token speichert der Scanner den Typ, die Position und ggf. einen zusätzlichen Wert ab.
//Beispiel Wortsymbol
class
//wird durch folgendes Tripel repräsentiert:
(ClassToken, , (x,y))

//Beispiel Zahl
3.141
//wird durch folgendes Tripel repräsentiert:
(DoubleToken, 3.141, (x,y))

Syntaktische Analyse

Der Tokenstream des Scanners dient nun als Eingabe für die syntaktische Analyse. In dieser Phase wird die Syntax des Programms überprüft.
Dies wird üblicherweise durch eine Kontextfreie Grammatik (KFG) erreicht. Eine Kontextfreie Grammatik $G$ ist ein 4-Tupel $(N, T, P, S)$ mit den folgenden Eigenschaften:

  • Startsymbol $S \in N$
  • Nichtterminale $N$ und Terminale $T$ sind disjunkte Alphabete
  • $P$ ist eine endliche Teilmenge von $N \times (N \cup T)*$ und bezeichnet die Menge der Produktionen.

Nichtterminale sind Symbole aus dem Alphabet, welche durch Produktionen ersetzt werden und nicht im finalen Satz auftreten. Terminale hingegen dürfen nicht ersetzt werden und treten im finalen Satz auf.
Zur besseren Verständnis schauen wir uns dazu ein Beispiel an.

G = ( N, T, P, S ) mit
N = { Klammern, Liste }
T = { Zahl, '(', ')', ',' }
S = Klammern

P = {
  Klammern ::= '(' Liste ')
  Liste ::= Zahl ',' Liste
  Liste ::= Zahl
}

Diese KFG ist nun in der Lage beliebige lange Listen von Zahlen zu Erzeugen.
Gültige Sätze:
(1)
(1,2,3)
(4,5,7,8,3456456,34563456,555)

Ungültige Sätze:
()
(1,2,,,3)
(a,b,c)

Um nun zu überprüfen ob ein gegebener Satz auch durch die Grammatik erzeugt werden kann, wird vom Startsymbol aus versucht den Satz zu erzeugen.

Prüfe den folgenden Satz
(1,2,3)
Beginne mit Startsymbol
Klammern => erste Produktion liefert:
'(' Liste ')' => zweite Produktion liefert:
'(' Zahl ',' Liste ')' => zweite Produktion:
'(' Zahl ',' Zahl ',' Liste ')' => dritte Produktion:
'(' Zahl ',' Zahl ',' Zahl ')'

Beim einlesen des Programmcodes erzeugt der Compiler mit Hilfe der Grammatik einen abstrakten Syntaxbaum (abstract syntax tree AST). Dieser dient nun als Eingabe für die nächste Phase.

Semantische Analyse

Hier wird den einzelnen Teilbäumen des AST eine Bedeutung zugeweisen. Dabei wird auch die semantische Korrektheit geprüft. Beispielsweisse kann hier nun die Typsicherheit geprüft werden und ebenso ob eine Variable überhaupt deklariert wurde.
Der folgende code sollte die beiden vorherigen Phasen fehlerfrei überstanden haben, da er lexikalisch und strukturel korrekt ist:

public int test() {
  return "test";
}

Die semantische Analyse sollte in diesem Fall einen Fehler werfen, da die Typen nicht kompatibel sind.
Einige Dinge die typischerweise nun geprüft werden sollten:

  • Typsicherheit
  • Korrekte deklaration
  • Sichtbarkeit der Variablen
  • Sichtbarkeit von Methoden
  • Mehrfachdeklaration
  • ...

Auf Grund des Umfangs dieses Compiler Schrittes, werde ich im folgenden nur auf ein paar Details eingehen.

Symboltabelle

Die Symboltabelle ist eine sehr wichtige Datenstruktur und speichert den Namen, Typen, sowie das Auftreten einer Variable. Je nachdem was für eine Sprache man implementieren möchte, werden nicht nur Variablennamen, sondern auch die Namen von Funktionen und Klassen in dieser Tabelle aufgenommen.
Wenn man beim durchlaufen des AST auf eine Deklaration stößt, so wird in der Symboltabelle geprüft ob es bereits eine Deklaration mit diesem Namen gibt und wirft ggf. einen Fehler. Falls es zu keinem Fehler kommt, so wird die Tabelle um einen Eintrag erweitert. Wenn im weiteren Durchlauf eine Variable verwendet wird, so wird geprüft ob diese denn auch schon deklariert ist und ob der Typ korrekt ist. Unter Umständen wird auch hier ein Fehler geworfen.

Scope Management

In den meisten Sprachen ist es erlaubt, dass der Name einer Variable unter gewissen Umständen mehrfach benutzt wird. Zum Beispiel ist das folgende Beispiel gültiger Java Code, obwohl der Name name mehrfach benutzt wird:

public class ScopeTest {
  private String value;
        public void test() {
    if(xyz) {
      int value = 42;
    } else {
      double value = 3.141;
    }
        }
}

Da der Name in verschiedenen Scopes benutzt wird, wirft der Compiler keinen Fehler. Für eine Objektorientierte Sprache wie Java, speichert der Compiler eine globale Liste, welche die Klassen enthält und jeweils lokale Listen für jeden Scope.
Die Klasse ScopeTest würde somit im globalen Scope liegen, während die Klasssenvariable value, sowie die Methode test im Scope der Klasse liegen.
Die lokalen Variable liegen wiederum im Scope der entsprechenden Methode. Wenn nun eine Variable benutzt wird, so wird zuerst im aktuellen Scope danach gessucht. Falls sie dort nciht gefunden wird, so wird im darüberliegenden Scope weitergesucht, bis wir die Variable gefunden haben oder aber keinen übergeordneten Scope mehr gibt. Im letzteren Fall wird dann ein Fehler geworfen.

Code Generation

Anstatt direkt Maschinencode zu erzeugen, bietet es sich häufig an, einen Zwischencode zu erzeugen. Dieser kann dabei relativ Maschinennah sein, wie z.B. Assembler Code oder weiterhin eher abstrakt, wie z.B. wenn man in eine andere Programmiersprache übersetzen möchte.
Sprachen wie Java oder auch C# werden in sogenannten Bytecode übersetzt. Dieser hat Ähnlichkeit zu Assembler, ist jedoch weiterhin Objektorientiert und noch relativ nah an der Ursprungssprache.
Der Java Bytecode arbeitet Beispielsweise weiterhin auf Objekten und prüft auch die Sichtbarkeit.
Damit sind wir auch schon am Ende dieses kleinen Einstiegs in den Compiler Aufbau.