Folge 25 - Was ist ein Compiler?

Ein Compiler ist ein Programm, das einen Text einer Quellsprache (z.B. Java) in einen Text einer Zielsprache (z.B. Maschinencode) übersetzt. Bei dieser Übersetzung arbeitet ein Compiler in mehreren Durchgängen:


lexikalische Analyse
syntaktische Analyse
semantische Analyse

Analysephase (Front-End)


Zwischencode-Erzeugung
Zwischencode-Optimierung
Maschinencode-Erzeugung

Synthesephase (Back-End)



1.1 Analysephase

Lexikalische Analyse

In der Programm-Zeile
umfang = radius^2 * 3,14; 

würde die lexikalische Analyse zwei Fehler finden: der Bezeichner "radius^2" enthält ein ungültiges Zeichen, nämlich "^", und die Real-Zahl "3,14" enthält ein Komma statt einem Punkt. In der lexikalischen Analyse wird also festgestellt, ob Bezeichner, Zahlen, Schlüsselworte etc. richtig geschrieben sind. Die lexikalische Analyse ist mit der Rechtschreibkorrektur eines Textverarbeitungsprogramms vergleichbar.

Syntaktische Analyse

Eine lexikalisch korrekte Programm-Zeile wie z.B.
flaeche = pi * r * ;

wird als syntaktisch falsch erkannt, da auf das letzte Multiplikationszeichen keine Zahl oder Variable mehr folgt. Die syntaktische Analyse ist also mit der Grammatikprüfung eines Textverarbeitungsprogramms vergleichbar. Das Satz "Ich bin gestern nach." ist syntaktisch falsch, da ein wichtiger Satzteil fehlt, nämlich die entscheidende Information, wohin ich gegangen bin.

Semantische Analyse

Die Anweisung
a = 3 * wurzel(5);

ist lexikalisch und syntaktisch völlig korrekt, kann semantisch dagegen falsch sein, wenn z.B. die Methode wurzel() nicht definiert wurde oder wenn der Rückgabewert der sondierenden Methode ein String und keine double-Zahl ist. Textverarbeitungsprogramme verfügen zur Zeit noch über keine semantische Korrektur, was aber vielleicht auch gar nicht gewünscht wird. Würde man z.B. eine Bundestags-Rede durch eine solche semantische Korrektur jagen, so blieben wahrscheinlich nur noch 10% des ursprünglichen Textes übrig. Die restlichen 90% würden als "überflüssig, unwichtig, widersprüchlich, nichtssagend oder redundant" gestrichen werden. Auch die drei letzten Sätze dieses Abschnitts würden wahrscheinlich von der semantischen Analyse stark zusammengestaucht werden.

 

1.2 Synthesephase

Zwischencode-Erzeugung

Betrachten wir die Programm-Zeile
p = i + r * 60;

Die lexikalische und die syntaktische Analyse finden keinen Fehler. Wir gehen auch mal davon aus, dass die Programm-Zeile auch semantisch korrekt ist, dass also die Variablen p, i und r korrekt deklariert und initialisiert sind.

Der vom Compiler erzeugte Zwischencode könnte dann so aussehen:

temp1 := 60
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3 

temp1, temp2 und temp3 sind dabei temporäre Variablen, id1, id2 und id3 sollen die in der Analysephase erkannten Variablen sein.

Zwischencode-Optimierung

Nach der Optimierung könnte der Zwischencode dann so aussehen:
temp1 = id3 * 60
id1 = id2 + temp1

Der Code wurde also von vier Zeilen auf zwei Zeilen reduziert, die aber das Gleiche leisten.

Maschinencode-Generierung

Im letzten Teil des Übersetzungsvorganges, der Code-Generierung, wird aus dem optimierten Zwischencode der endgültige maschinennahe Code erzeugt, der z.B. wie folgt aussehen könnte:
MOV id3,R2
MUL 60,R2
MOV id2,R1
ADD R2,R1
MOV R1,id1 

Anmerkung 1:
Bei diesem Code handelt es sich nicht um die endgültige, prozessorabhängige Maschinensprache, sondern um eine maschinen-nahe Assemblersprache. Diese Form wurde hier nur der besseren Lesbarkeit wegen verwendet; ein wirklicher Compiler erzeugt nämlich keine Assemblersprache, sondern echte Maschinensprache.

Anmerkung 2:
In den Folgen 21 bis 23 hatten wir ja einen Stackinterpreter konstruiert, der einen Stackmaschinencode abarbeiten konnte. Der hier gezeigte Maschinencode ist mit diesem Stackmaschinencode vergleichbar. Allerdings wird hier keine Stackmaschine gesteuert, sondern eine Registermaschine. Statt mit Hilfe eines Stacks verwaltet eine Registermaschine ihre Daten mit Hilfe von 4, 8, 16, 32 oder mehr starren Registern.

Ausblick

In meinem Kurs werde ich auf Registermaschinen nur am Rande eingehen. Im Laufe der nächsten Folgen werde ich vielmehr einen großen Bogen vom Thema "Syntaxanalyse" und "Codeerzeugung" zum Thema "Stackinterpreter" schlagen.

Zielsetzung: Wir werden ein Java-Programm entwickeln, das Java-ähnlichen Code in Stackmaschinencode übersetzt, der dann von unserem Stackinterpreter aus Folge 21 - 23 interpretiert werden kann.

Anmerkung 3:
Der alte Kurs "Compilerbau" wird noch innerhalb dieses Jahres von meiner Homepage entfernt, die Folgen 21ff des BlueJ-Kurses ersetzen den alten Kurs voll und ganz.

weiter mit Folge 26: Einfachste Sprachen

Wie kann man einen Bezeichner, eine int-Zahl, eine double-Zahl etc. eigentlich erkennen und auf lexikalische Korrektheit überprüfen? Hier wird das Konzept der Determinierten Endlichen Automaten vorgestellt, die zur lexikalischen Analyse eingesetzt werden. Für die Klausur- und Abiturleute gibt es einen umfangreichen Theorieteil über Nichtdeterminierte Endliche Automaten.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 25. Juli 2006.






IMPRESSUM