Compilerbau (eBook)

1Überblick

Ein Compiler ist ein Werkzeug, das ein Quellprogramm (z.B. in Java, Pascal oder C) in ein Zielprogramm übersetzt. Die Sprache des Zielprogramms ist meist Maschinencode (z.B. Instruktionen eines Prozessors oder Java-Bytecode). Das Übersetzungsziel kann aber auch eine andere Quellsprache sein. In diesem Fall spricht man von einem Cross-Compiler.

Neben Compilern im engeren Sinne gibt es auch compilerähnliche Werkzeuge, die eine beliebige syntaktisch strukturierte Eingabe in etwas übersetzen, das keine Sprache im engeren Sinne ist. So ein Werkzeug könnte zum Beispiel eine Logdatei in eine Tabelle übersetzen, die Informationen aus der Logdatei in aggregierter Form darstellt.

Man mag sich vielleicht fragen, wozu Compilerbau-Kenntnisse eigentlich nützlich sind. Schließlich entwickeln nur große Firmen wie Microsoft, Google oder Oracle Compiler. Das ist zwar richtig, aber es sprechen mehrere Gründe dafür, Compiler zu studieren:

• Compiler gehören zu den am häufigsten benutzten Werkzeugen der Softwareentwicklung. Daher sollten wir verstehen, wie sie aufgebaut sind und wie sie funktionieren.
• Wenn wir und mit Compilern beschäftigen, lernen wir auch, wie ein Computer auf Maschinenebene funktioniert. Wir müssen uns mit seinem Instruktionssatz, seinen Registern, seinen Adressierungsarten sowie mit seinen Datenbereichen wie dem Methodenkeller oder dem Heap befassen. Das schafft eine Brücke zwischen Hardware und Software.
• Wer weiß, in welche Instruktionen bestimmte Sprachkonstrukte übersetzt werden, bekommt ein besseres Gefühl für die Effizienz von Programmen.
• Im Compilerbau müssen wir uns mit Grammatiken beschäftigen. Strukturierte Daten durch Grammatiken zu beschreiben, gehört so wie das Programmieren zum Handwerkszeug der Softwareentwicklung.

Darüber hinaus sind Compilerbau-Kenntnisse aber auch im allgemeinen Software Engineering nützlich. Während nur wenige Leute Compiler im engeren Sinne bauen, sind die meisten von ihnen im Laufe ihres Berufslebens irgendwann einmal mit der Aufgabe konfrontiert, compilerähnliche Werkzeuge zu entwickeln. Dies reicht von der Auswertung von Kommandozeilenparametern über die Verarbeitung von Stücklisten oder Dokumentbeschreibungssprachen (z.B. PDF oder Postscript) bis hin zur statischen Programmanalyse, die aus einem Quellprogramm Kennzahlen wie zum Beispiel seine Komplexität berechnet. In all diesen Fällen sind Compilerbau-Techniken nützlich.

Das vorliegende Buch beschäftigt sich mit dem Compilerbau im engeren Sinne, obwohl die vermittelten Techniken auch im allgemeinen Software Engineering eingesetzt werden können. Es beschreibt die vollständige Implementierung eines Compilers für eine einfache Java-ähnliche Programmiersprache (MicroJava), der ausführbaren Bytecode (ähnlich dem Java-Bytecode) erzeugt. Dabei richtet es sich an Fachleute aus der Praxis. Formale Grundlagen werden nur so weit behandelt, wie sie zum Verständnis der angewandten Techniken nötig sind. Das Buch deckt auch bewusst nicht alle Feinheiten des Compilerbaus ab, sondern nur jene Techniken, die in der Praxis benötigt werden. Insbesondere geht es kaum auf Optimierungsverfahren ein, die ein eigenes Buch füllen würden und nur für Leute relevant sind, die Produkt-Compiler schreiben. Ferner behandelt es lediglich Compilerbau-Techniken für imperative Sprachen. Funktionale oder logische Programmiersprachen benötigen zumindest teilweise andere Techniken, die aber im praktischen Software Engineering auch seltener zum Einsatz kommen.

Bücher über fortgeschrittene Techniken des Compilerbaus gibt es in großer Anzahl (z.B. [ALSU08], [Appe02], [Coop22], [FCL09], [Much97]). Sie behandeln vor allem Techniken der statischen und dynamischen Codeanalyse, das umfangreiche Gebiet der Compiler-Optimierung sowie Feinheiten der Codeerzeugung und der Registerallokation. Sie sind allerdings nur für Leute relevant, die Produkt-Compiler für Sprachen wie Java oder C++ entwickeln wollen. Für Einsteiger sind sie oft eher verwirrend.

Das vorliegende Buch entstand aus einer zweistündigen Vorlesung über die Grundlagen des Compilerbaus und kann als Lehrbuch für diese Zwecke eingesetzt werden. Es richtet sich aber auch an Leute aus der Praxis, die die Arbeitsweise eines Compilers besser verstehen und ihr Methodenrepertoire erweitern wollen.

1.1Geschichte des Compilerbaus

Die ersten Compiler entstanden Ende der 1950er-Jahre. Damals war der Compilerbau eine Geheimwissenschaft, ja ein Hype, den man durchaus mit dem heutigen Interesse an künstlicher Intelligenz vergleichen kann. Nur wenige wussten darüber Bescheid, und es gab auch noch kaum Techniken zur Übersetzung von Programmiersprachen. Die Entwicklung der ersten Compiler kostete viele Personenjahre. Heute ist der Compilerbau eines der am besten erforschten Gebiete der Informatik. Es gibt ausgereifte Techniken für die Syntaxanalyse, die Optimierung und die Codeerzeugung, sodass Studierende heute einen (einfachen) Compiler in einem einzigen Semester implementieren können.

Dieses Kapitel gibt einen kurzen (und notwendigerweise unvollständigen) Abriss der Geschichte des Compilerbaus, die gleichzeitig auch eine Geschichte der Programmiersprachen und ihrer Konzepte ist. Dabei werden die Erkenntnisse und Fortschritte an exemplarischen Sprachen festgemacht, die als Meilensteine gelten und die Entwicklung der Compilerbau-Techniken in diesem Zeitfenster repräsentieren.

1957: Fortran. Eine der ersten höheren Programmiersprachen war Fortran [Back56]. John Backus, der damals für IBM arbeitete, leitete ein Team, das sich zum Ziel gesetzt hatte, die damals übliche Assembler-Programmierung durch eine höhere Programmiersprache zu ersetzen und einen Compiler dafür zu implementieren, der Maschinencode erzeugte, der es mit der Effizienz handgeschriebener Assembler-Programme aufnehmen konnte. Viele der Grundtechniken des Compilerbaus wurden hier entwickelt. So war es anfangs alles andere als klar, wie man arithmetische Ausdrücke (z.B. a + b * c) so in Maschinenbefehle übersetzen konnte, dass die Vorrangregeln der Operatoren beachtet werden. Auch die Übersetzung von Verzweigungen und Schleifen in Maschinenbefehle musste erst erarbeitet werden, ebenso wie die Mechanismen zum Aufruf von Prozeduren oder zum Zugriff auf Arrays.

1960: Algol. Algol60 [Naur64] war ein Meilenstein in der Geschichte der Programmiersprachen. Es wurde von einem Konsortium von Experten aus Europa und den USA entwickelt, die teilweise von Universitäten kamen, teilweise aber auch aus der Industrie. Wichtige Neuerungen waren die Blockstruktur mit lokalen und globalen Variablen sowie das Konzept der Rekursion, das es ermöglichte, dass Prozeduren ihre Variablenwerte über rekursive Aufrufe hinweg beibehielten. Algol60 war aber auch deshalb bemerkenswert, weil es die erste Programmiersprache war, deren Syntax formal durch eine Grammatik definiert wurde. John Backus und Peter Naur entwickelten dafür die Backus-Naur-Form (BNF), die heute in zahlreichen Varianten zum Rüstzeug jedes Compilerbauers gehört.

1970: Pascal. Ein Nachfolger von Algol60 war die Sprache Pascal [JW75], hinter der Pioniere wie Niklaus Wirth und Tony Hoare standen. Obwohl Pascal als einfache Unterrichtssprache konzipiert war, führte sie wichtige Neuerungen ein, die auch im Compilerbau ihren Niederschlag fanden. Während ältere Sprachen nur vordefinierte Datentypen wie integer oder real kannten, konnte man in Pascal eigene Datentypen definieren, die man dann zur Deklaration von Variablen verwenden konnte. Neben Arrays als Tabellen gleichartiger Elemente wurden Records (auch Structs genannt) eingeführt, die Daten unterschiedlichen Typs zu einer neuen Einheit zusammenfassten. Obwohl die Idee von Records bereits in Cobol auftauchte, wurden Records als Datentyp erst in Pascal eingeführt. Der Zugriff auf Elemente solcher strukturierten Datentypen erforderte neue Compilerbau-Techniken. Außerdem erzeugten die ersten Pascal-Compiler nicht Maschinencode, sondern sogenannten »P-Code«, der dem heutigen Bytecode von Java ähnelte. P-Code war wesentlich kompakter als Maschinencode, wodurch Pascal-Programme auch auf Mikrocomputern mit ihren damals sehr beschränkten Speicherkapazitäten liefen. Das förderte die Verbreitung von Pascal, hatte allerdings den Nachteil, dass P-Code nicht direkt auf einer Maschine ausführbar war, sondern interpretiert werden musste, was Laufzeit kostete.

1985: C++. C++ [Stro85] ist ein Nachfolger der Sprache C, die etwa zur gleichen Zeit wie Pascal entstand und ebenfalls ein Nachfolger von Algol60 war. In C++ wurde das damalige Wissen im Bereich der Programmiersprachen und des Compilerbaus konsolidiert. Es wurden unter anderem Konzepte wie Objektorientierung, Ausnahmebehandlung oder generische (d.h. parametrisierbare) Datentypen eingeführt, die es zwar auch schon in anderen Sprachen gab, die aber erst mit C++ populär wurden....