© 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 Gramma...

Exklusives Abo-Special

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