© GoodStudio/Shutterstock.com
Bau eines Compilers mit Go und ANTLR4

Das Monster bändigen


Compiler sind mitunter riesige Gebilde aus unzähligen Codezeilen. Dieser Artikel zeigt, wie eine einfache Struktur für einen Multi-pass-Source-to-Source-Compiler aufgebaut werden kann, die über ANTLR4 und Templates sowohl Parser als auch Ausgabeformate einfach erweiterbar macht.

Jeder von uns hat ein Bild im Kopf, wenn das Wort Compiler fällt. Riesen wie GCC oder auch der Go-Compiler bestehen oft aus tausenden Zeilen Code und scheinen auf den ersten Blick nicht gebändigt werden zu können. Auch Programmiersprachen auf Basis von virtuellen Maschinen, wie zum Beispiel die JVM, nutzen einen Compiler (JIT-Compiler), der vorher erzeugten Bytecode maschinenspezifisch übersetzt, um ein Programm ausführen zu können. Im Grunde übersetzen alle Compiler „nur“ von einer Sprache in eine andere. Das kann von High-Level- zu Low-Level-Sprache (z. B. Assembler), von High-Level zu High-Level (Source-to-Source-Compiler) oder auch von Low-Level zu High-Level (Decompiler) sein. Für diese Übersetzungen benötigt fast jeder Compiler ein Grundgerüst aus Lexer, Parser und eine Repräsentation des Codes über einen Abstract Syntax Tree. Im folgenden Beispiel, einem Source-to-Source-Compiler, werden diese über einen Codegenerator erzeugt.

Lexer

Um aus Eingaben einen Output zu erzeugen, werden aus den einzelnen Wörtern mittels Regeln Token erzeugt. Diese Regeln (reguläre Sprache/Lexical Grammar) bilden die Grundlage, um Zeichenketten einen Typ zuzuweisen und so einen Stream aus Token zu erzeugen. Dies ist die Aufgabe des Lexers. Das Beispiel in Listing 1 zeigt, wie im ersten Schritt die Regeln definiert werden, anhand derer die Definition einzelner Token festgelegt wird.

Listing 1

// token REPEATED : 'repeated'; TYPE : 'string' | 'bool' | 'int32'; IDENT : [a-zA-Z]([a-zA-Z0-9_])+; NUMBER : [0-9]+; WHITESPACE : [ \r\n\t]+ -> skip;

Die hier gewählte Grammatik zur Beschreibung dieser Regeln ist die erweiterte Backus-Naur-Form. Bestimmte Beschreibungen wie das -> skip sind zusätzliche Erweiterungen aus ANTLR4 [1]. Da die Regeln in Reihenfolge angewendet werden, wird beispielsweise aus dem Wort „string“ das Token TYPE und nicht IDENT. Die Tokenisierung ermöglicht im nächsten Schritt, die Reihenfolge der Token zu analysieren, um ihr einen Sinn geben zu können. Dieser Schritt findet allerdings nicht mehr im Lexer, sondern im Parser statt.

Parser

Der Token-Stream wird vom Lexer zum Parser übergeben, um die Reihenfolge der Token zu interpretieren und anhand von Regeln ähnlich der Lexical Grammar eine abstrakte Repräsentation der Eingaben zu erstellen. Über die Regeln wird ebenfalls validiert, ob die Abfolge der Token der angegebenen Grammatik entspricht. Die Definition der Token wird um die Regeln des Parsers erweitert. Anhand dieser Regeln kann die Abfolge der Token in einen Graphen mit Abhängigkeiten überführt werden, wie Listing 2 zeigt.

Listing 2

// parser rules packageDefinition : 'package' fullIdent ';'; messageDefinition : 'message' IDENT '{' fieldDefinition* '}'; fieldDefinition : REPEATED? typeIdent IDENT '=' NUMBER';'; // literals & identifier fullIdent : IDENT ('.' IDENT)*; typeIdent : fullIdent | TYPE;

Diese resultierende Abstraktion wird Abstract Syntax Tree (AST) genannt. Für die Syntax unwichtige Elemente wie Klammern werden im Baum nicht mehr berücksichtigt, sodass die Repräsentation auf das Notwendige reduziert wird. Wird zum Beispiel die Eingabe message Stopwatch { int32 Ticks = 0 } geparst, ergibt sich daraus der erste Node über die Regel messageDefinition. Abhängig davon müssen Eingaben zwischen {} als fieldDefinition interpretiert und entsprechend geparst werden können. Andernfalls würde die Eingabe gegen die abgebildeten Regeln verstoßen. Der in Abbildung 1 gezeigte AST würde in top-down [2] geparst werden.

serowy_compilerbau_1.tif_fmt1.jpgAbb. 1: Beispiel eines in top-down geparsten AST

Warum aber einen Parser selbst schreiben? Genauso gut kann man diesen Schritt automatisieren lassen. Tools wie yacc, bison oder ANTLR können Lexer und Parser anhand ein...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang