1    Einleitung

Programs must be written for people to read, and only incidentally for machines to execute.
– Herold Abelson & Gerald Jay Sussmann

1.1    Compiler und Sprache

Was ist ein Compiler?

Das Wort »compilare« ist lateinisch und bedeutet so viel wie »zusammenstellen«, »aufhäufen«.

Sicherlich haben Sie schon mit Compilern gearbeitet: Der Java-Compiler javac übersetzt Java-Programme in Java-Bytecode, der auf der Java Virtual Machine (JVM) ausgeführt werden kann, der C-Compiler gcc erzeugt Maschinenprogramme, die direkt auf Ihrem Rechner ausgeführt werden können.

Der Compiler ist also das Programm, das Ihren Programmen dazu verhilft, ausgeführt zu werden, wie es in der zweiten Hälfte des Zitats von Abelson und Sussmann aus ihrem Standardwerk Structure and Interpretation of Computer Programs heißt.

Abbildung 1.1 veranschaulicht diese Definition und gibt Ihnen den ersten, noch sehr groben Überblick über den Compiler.

P und P' stehen dabei für Programme, die in den Programmiersprachen L und L' abgefasst sind. Der Compiler könnte zum Beispiel Ihr Programm hello.java, das in Java geschrieben ist, in hello.class übersetzen, das in der Sprache des Java-Bytecodes abgefasst ist.

Abbildung 1.1     Funktion eines Compilers

Warum sollten Sie sich mit Compilerbau beschäftigen? Dazu fallen mir gleich mehrere gute Gründe ein:

• Wenn Sie verstehen, wie ein Compiler funktioniert, werden Sie auch ein besserer Programmierer oder eine bessere Programmiererin, weil Sie besser abschätzen können, warum die Programmiersprache, die Sie gerade benutzen, dieses oder jenes Feature hat oder nicht hat.

• Compilerbau ist unzertrennbar mit dem Design von Programmiersprachen verbunden – das Verständnis dafür, was alles getan werden muss, um einen Compiler für eine Sprache zu erstellen, hilft beim Erlernen jeder Programmiersprache.

• In dem Kapitel über die Konzepte von Programmiersprachen werden Sie – sofern Sie mindestens eine Programmiersprache kennen – viele Dinge wiedererkennen. Hier erfahren Sie, wie die Elemente der Programmiersprachen zusammenhängen.

• Wir werden einige Datenstrukturen und Muster benutzen, die zum Lösen vieler anderer Probleme ebenfalls nützlich sind.

• Compilerbau ist ein sehr anschauliches Beispiel dafür, wie Theorie (und davon werden Sie einige in diesem Buch lernen!) die praktische Arbeit enorm erleichtern kann: Lesen Sie die Geschichte des ersten Compilers auf der nächsten Seite!

• Gleichzeitig ist ein großer Teil der Theorie auch für viele andere Gebiete der Informatik relevant. Endliche Automaten beispielsweise werden Ihnen oft begegnen, weil sie ein häufig anwendbares Modell sind.

• Selbst einen Compiler zu schreiben ist ein spannendes Projekt!

Lassen Sie uns aber, bevor wir nun mit dem eigentlichen Inhalt beginnen, einen Blick in die Vergangenheit werfen:

Die ersten Compiler entstanden in den 1950er-Jahren, ohne dass eine Theorie über Compilerbau geschweige denn -werkzeuge existierten. John Backus beschreibt in [Backus J. , 1978], wie bis 1957 fast ausschließlich direkt in Maschinencode programmiert wurde, was aber dazu führte, dass die Programmierung und vor allem die Fehlersuche überproportional viel Zeit benötigten. Backus, damals angestellt bei IBM, startete daher Anfang 1954 das Projekt FORTRAN, eine Abkürzung für »FORmula TRANslator«, und die erste Version der gleichnamigen Sprache wurde im Frühjahr 1957 ausgeliefert. Die Zeitspanne von drei Jahren mag Ihnen sehr lang erscheinen, aber bedenken Sie, dass es keinerlei Vorerfahrungen und vor allem keine Algorithmen und Werkzeuge gab!

Der erste Compiler ist nach Meinung vieler der A-0-Compiler von Grace Hopper, die später die Programmiersprache COBOL entwickelte [Hopper, 1955].

In diesem Buch werden Sie viel Theorie lernen, vor allem über formale Sprachen, Automaten und Parser-Verfahren. Denken Sie dabei immer daran, dass Sie ohne diese Theorie niemals in der Lage wären, einen Compiler in wenigen Wochen zu entwickeln!

Nach FORTRAN und dann 1960 dem ersten COBOL-Compiler, ebenfalls entwickelt von Grace Hopper, hat vor allem die Entwicklung von ALGOL (»ALGOrithmic Language«) die Evolution von Programmiersprachen deutlich vorangetrieben. Von ALGOL stammt unter anderem Pascal ab [Wirth, The programming language pascal, 1971] und von diesem leiten sich direkt oder indirekt die meisten der heute populären Sprachen her.

Nachdem wir einen ersten, sehr kurzen Blick auf Compiler geworfen haben, müssen wir im zweiten Schritt den in der Definition vorkommenden Begriff »Programmiersprache« untersuchen.

Eine Programmiersprache ist eine Sprache, in der »Programme« geschrieben werden. Was aber ist dann eine Sprache?

Die Nutzung des Wortes »Sprache« ist hier nicht zufällig – vor allem in den Kapiteln 3 und 4 werden wir die Beziehungen zwischen natürlichen Sprachen und Sprache, wie man sie in der Informatik nutzt, tiefer beleuchten.

So viel sei vorweggenommen: Jede Sprache besteht aus Grundeinheiten, zum Beispiel den Buchstaben und Zeichen (Komma, Punkt, ...) in der deutschen Sprache. Aus diesen Zeichen bilden wir Wörter. Legen wir das lateinische Alphabet (plus im Deutschen die Umlaute) als Menge der zulässigen Buchstaben zugrunde, könnten wir unendlich viele Wörter bilden, von denen die meisten im Deutschen aber völlig sinnfrei wären. Für die deutsche Sprache enthält der Duden alle gebräuchlichen Wörter. Wir nehmen insbesondere bei gesprochener Sprache eher die Wörter als Einheiten wahr als die Buchstaben, aus denen die Wörter bestehen.

Um dieses Denkmuster zu vervollständigen, fügen wir Wörter zu Sätzen zusammen. Dabei könnten wir beliebig Wörter aus dem Duden aneinanderreihen – in den seltensten Fällen ergibt das aber einen korrekten und sinnvollen Satz. Warum?

Es fehlt noch die Bauanleitung für Sätze!

Obwohl der Duden nur endlich viele »zugelassene« Wörter enthält, können Sie daraus unendlich viele korrekte deutsche Sätze formen. Der Mechanismus, der dies bewerkstelligt, sozusagen die Bauanleitung, ist die Grammatik.

Diese Bauanleitungen sind meistens relativ kompakt – selbst die für die meisten von uns komplizierte deutsche Grammatik wird im Duden auf nur ca. 70 Seiten beschrieben, während das Verzeichnis der Wörter 1100 Seiten umfasst.

Mit diesen drei Konzepten – »Zeichen«, »Wörter« und »Grammatik« – können wir nun also korrekte Sätze zusammenbauen.

Abbildung 1.2     Von Zeichen zu Wörtern und Sätzen

Das reicht aber leider noch nicht, wie beispielsweise der Satz »Fahrrad spielt flüssiges Buch« zeigt:

• Besteht der Satz aus lauter Buchstaben des Alphabetes? Ja!

• Besteht der Satz nur aus Wörtern, die im Duden stehen? Ja!

• Ist der Satz grammatikalisch korrekt? Ja!

Der Inhalt des Satzes ist aber völlig sinnfrei. Hm.

Neben den in Abbildung 1.2 gezeigten formalen Konzepten, die die Syntax beschreiben, gehört zu einer Sprache auch die Bedeutung, die Semantik. In jeder Sprache (sowohl in den natürlichen Sprachen als auch in den Programmiersprachen) gibt es neben den syntaktischen Regeln daher auch semantische Regeln, die die Bedeutung der Sätze festlegen.

Alle Begriffe, die wir bis hierhin anhand einer natürlichen Sprache eingeführt haben, finden sich auch so in Programmiersprachen: In Kapitel 3 werden wir uns ansehen, wie wir – jetzt für eine Programmiersprache und nicht für eine natürliche Sprache – aus Zeichen Wörter bilden können.

In den folgenden Kapiteln 4 und 5 starten wir in die nächste Stufe: Wir erstellen eine Grammatik und bauen damit aus den Wörtern Sätze. Die Sätze sind in einer Programmiersprache verfasste Quelltexte, und wir können dann feststellen, ob die Programme syntaktisch korrekt sind.

Kapitel 6 ist überschrieben mit »Semantische Analyse«. Darunter versteht man im Compilerbau aber »nur« die Prüfung...