Compilerbau (1. Teil): Grundlagen back to frontpage

Ein spannendes Feld in der theoretischen Informatik ist der Compilerbau (auch Übersetzerbau). Leider finden sich nur wenige für Einsteiger oder Interessierte gut verständliche Ressourcen im Netz, die einen kurzen und schnellen Überblick über das Thema ermöglichen (natürlich gibt es jedoch exzellente Literatur zum Thema, die es jedoch zugleich wesentlich ausführlicher und ggfs. formaler darstellt, als ich dies in dem Blogpost beabsichtige). Anders als es zunächst auf den ersten Blick erscheint, hat Compilerbau auch heute noch für den “normalen” (= nicht Compiler entwickelnden) Softwareentwickler praktische Relevanz. Ich möchte mein Blog daher dazu nutzen, um ein paar Worte zum Compilerbau zu verlieren und in einer Blogserie einen kleinen Übersetzer entwickeln.

Motivation

Mit Compilern oder Übersetzern haben alle, die diesen Beitrag hier lesen, schon einmal zu tun gehabt. Sei es beim Kompilieren eines Projektes, dem Nutzen einer Template-Sprache oder dem Ausführen einer Datenbankanfrage - und nicht zuletzt beim Aufrufen dieser Webseite. Worum geht es letzten Endes also beim Übersetzerbau? Um eine Übersetzung von einer (zumeist höheren) Quell- in eine (zumeist niedrigere) Zielsprache. Also zum Beispiel von einem C-Quellcode in x86-Maschinencode, von einem Java-Quellcode in Java-Bytecode, von einer textuellen Datenbankanfrage in eine interne Repräsentation (damit die Anfrage vom Datenbanksystem “verstanden” werden kann) oder von HTML-Code in eine interne Darstellung, damit daraufhin die geeignete graphische Ausgabe erzeugt werden kann. Grundsätzlich kann man sagen, dass fast immer dann, wenn eine textuelle Darstellung in eine interne Repräsentation zur Weiterverarbeitung durch eine Software überführt werden muss, Techniken des Übersetzerbaus zur Anwendung kommen. Selbst in Taschenrechnern kann man diese eleganten Techniken nutzen und komplexeste Ausdrücke evaluieren.

Grundsätzliche Funktionsweise

Die Grundlagen des Übersetzerbaus sind gut verstanden, und daher gibt es in diesem Bereich wenig neue Erkenntnisse oder Überraschungen, dafür aber gute Algorithmen und daraus abgeleitete (automatisierte) Tools zur Unterstützung. Auf diese Tools möchte ich im Folgenden verzichten, da sie letzten Endes nur das automatisieren, was ich versuche, mit meinen Beiträgen zu erklären. Im Gegensatz zu den Grundlagen ist die Optimierung von Computerprogrammen weiterhin ein aktives und besonders komplexes Forschungsfeld, auf das ich hier nur am Rande eingehen werde.

Übersetzer bestehen grundsätzlich aus mehreren Phasen, die im Zuge der Übersetzung (oft verzahnt) durchlaufen werden. Verzahnt meint, dass zunächst Zug um Zug Produkte früherer Phasen in späteren Phasen verarbeitet werden, bis daraufhin weitere Produkte in früheren Phasen produziert und erneut weitergereicht und verarbeitet werden.

Die erste Phase eines Übersetzers, der sogenannte Lexer, umfasst stets das Einlesen des Input-Strings (zum Beispiel ein Programmquelltext oder ein Ausdruck bei einem Taschenrechner) und das Aufsplitten dieses Strings in seine elementaren Bestandteile (sogenannte Tokens). Um beim Beispiel zu bleiben, könnte man Ganzzahlen, Operatoren und Klammern bei einem einfachen mathematischen Ausdruck erkennen und aufsplitten. Der Input

5 * 2 + 10 / (1 - 4)

würde daraufhin wie folgt aufgesplittet:

Num(5) Op(*) Num(2) Op(+) Num(10) Op(/) BraceOpen Num(1) Op(-) Num(4) BraceClose

(Num = Zahl, Op = Operator, BraceOpen = offene Klammer, BraceClose = geschlossene Klammer).

Mit Erkennung und Produktion dieser Tokens schließt die erste Phase ab. Der Lexer übergibt seine Tokens der zweiten Phase, dem Parser.

Der Parser baut daraufhin anhand einer sogenannten Grammatik (einem Regelwerk für die Sprache, die erkannt werden soll; die Tokens sind, wie ich in späteren Blogposts zeige, in der Grammatik involviert) eine baumartige Struktur auf, die für den oben genannten Ausdruck wie folgt aussehen könnte.

Abstract Syntax Tree eines mathematischen Ausdrucks

Solch einen Baum nennt man Abstract Syntax Tree (AST). Es existiert neben dieser abstrakten Darstellung noch eine Darstellung, die man als Parsetree (oder konkreten Parsebaum) bezeichnet. Auf diese komme ich im Zuge kontextfreier Grammatiken noch einmal zurück. Für den Moment genügt die anschauliche Darstellung des AST.

Wie an dem Baum schön ersichtlich, führte die Konstruktion dieses Baums anhand einer (noch) nicht näher spezifizierten Grammatik zur Berücksichtigung der gängigen Präzedenzregel “Punkt- vor Strichrechnung”. Der Operator einer Operation findet sich stets als Elternknoten wieder, die Kinder links und rechts stellen jeweils die Operanden dar. Durchläuft man den Baum in-order, erhält man den obigen mathematischen Ausdruck zurück:

5 * 2 + 10 / (1 - 4)

Diese interne Baumdarstellung ist Grundlage für die anschließenden Phasen.

Nachdem der Parser sichergestellt hat, dass sich der Input (also der mathematische Ausdruck) syntaktisch an die festgelegte Grammatik hält und diesen daraufhin in eine Baumdarstellung überführt hat, wird in der darauffolgenden Phase der Input semantisch in der semantischen Analyse untersucht. Hierzu gehören Typüberprüfungen oder die Ermittlung impliziter Typen, die sich aus Ausdrücken ergeben. Beispielsweise impliziert eine Addition zweier Ganzzahlen erneut den Typ Ganzzahl. Der Baum wird entsprechend durchlaufen und für jeden Knoten des Ausdrucks wird ein ermittelter Typ hinterlegt und auf kompatible Typen bei Operationen geachtet. Würde zum Beispiel der folgende Ausdruck der definierten Grammatik entsprechen (d.h. auf syntaktischer Ebene korrekt sein), so muss dieser noch lange nicht auf semantischer Ebene einen Sinn ergeben. Demzufolge würde die semantische Prüfung nach Prüfung der Operanden der Addition einen Fehler wegen inkompatibler Typen auslösen.

"Nummer" + 5 => Addition von String und Integer nicht möglich

Die drei genannten Phasen (lexikalische Analyse (Lexer), syntaktische Analyse (Parser), semantische Analyse) werden unter dem Begriff des Frontend zusammengefasst. Das Ergebnis des Frontend ist die produzierte Baumstruktur sowie weitere strukturierte Daten, die während der einzelnen Phasen erzeugt wurden (zum Beispiel Tabellen über verwendete Symbole wie Variablen, Typen usw.). Je nach Typ des Übersetzers kann das Frontend zudem einen sogenannten Zwischencode produzieren, der bereits von diversen Elementen der Quellsprache (z. B. C oder Java) abstrahiert. Dieser Zwischencode könnte beispielsweise nur noch einen sehr eingeschränkten, jedoch noch umfangreicheren Instruktionsumfang besitzen, als ihn die Zielsprache (zum Beispiel Maschinencode) aufweist. Ziel ist es, die Komplexität der Anweisungen zu reduzieren, Analysen auf diesem Zwischencode zu ermöglichen und eine gute Interoperabilität zwischen Frontend und Backend herzustellen.

Diese Datenstrukturen und ggfs. der Zwischencode dienen dem darauffolgenden Backend als Input. Bei Compilern, wie einem C- oder Java-Compiler, besteht das Backend aus einer Analyse-, Optimierungs- und Codeerzeugungsphase. Ziel ist hier, den Zwischencode mithilfe der weiteren Datenstrukturen in den endgültigen Maschinen- oder Bytecode zu übersetzen. Interpreter hingegen könnten direkt auf dem Baum arbeiten und diesen ausführen, indem sie für jede Operation eine geeignete Implementation zur Verfügung stellen und beim Traversieren durch den Baum die jeweilige Funktion mit den jeweiligen Operanden aufrufen.

Die Trennung von Frontend und Backend erlaubt es, für ein gegebenes Backend, das in der Regel aufgrund seiner Optimierungs- und Codeerzeugungsphasen weitaus komplexer ist (s. o.), ein beliebiges (einfacher zu erstellendes) Frontend zu entwickeln, das eine andere Sprache als Input akzeptiert. Vorteil dieser Entkopplung ist die Wiederverwendung der Funktionen des Backends, die auf Basis des Frontend-Outputs den passenden (hoch-)optimierten Code für die gewünschte Zielplattform erzeugen können. LLVM ist ein Beispiel für ein Compiler-Backend, für das diverse Frontends entwickelt werden können (z. B. existiert mit Clang ein Frontend für die Programmiersprache C, das einen Zwischencode produziert, der von LLVM als Input genutzt wird)

Ein Taschenrechner könnte, ähnlich wie ein Interpreter, direkt auf dem AST arbeiten. Diesen Ansatz möchte ich in weiteren Blogposts näher verfolgen und Schritt für Schritt einen Lexer (sowie die dahinter stehende Theorie der regulären Ausdrücke), einen Parser (und auch die hier benötige Grammatik) sowie zu guter Letzt ein Backend als Evaluator entwickeln, um Ausdrücke der oben gezeigten Art auswerten zu können. Dabei wird die zu entwickelnde Sprache unter anderem Variablen und Funktionen zur Verfügung stellen. Bis dahin!

Weiter zum Teil 2

Literaturtipps


New comment

Comments are moderated and therefore are not published instantly.





Comments

No comments yet. Be the first! :-)