Compilerbau mit ANTLR4 und ASM4 entmystifiziert

E pluribus JVM

Oliver Zeigermann


Im Folgenden möchte ich mit Ihnen zusammen einen kleinen Compiler schreiben. Dabei werden wir uns einer Reihe von Herausforderungen stellen müssen. Zum einen im Compiler-Frontend: Wie analysieren wir die Eingabe des Benutzers?, zum anderen im Backend: Wie machen wir daraus ausführbaren Bytecode?

Die Grammatik

Um unsere Sprache zu beschreiben, benutzen wir eine Grammatik für ANTLR4 (Kasten „Wie funktioniert ANTLR4?“ und [3]) wie in Listing 1. Eine Grammatik besteht aus Regeln, eine Regel wiederum aus einem Namen und einer Beschreibung, welche Eingaben zu der jeweiligen Regel passen. Regeln, deren Namen mit einem Großbuchstaben anfangen, beschreiben Token. Das sind die einzelnen Wörter unserer Sprache. Regeln, deren Namen mit einem Kleinbuchstaben beginnen, beschreiben, wie man diese Wörter zu komplexeren Ausdrücken zusammensetzen kann.

Wie funktioniert ANTLR4?ANTLR4 ist ein Compilergenerator, der aus einer Grammatik eine komplette Grundstruktur für einen Compiler erzeugt. Diese Grundstruktur besteht aus generierten Java-Klassen.Dazu gehört ein Lexer, der aus der Eingabe von einzelnen Zeichen Wörter, so genannte Token, zusammenfasst und an den ebenfalls erzeugten Parser weiter gibt. Der Parser liest diese Wörter ein und prüft, zu welchen Regeln und darin enthaltenen Alternativen die Abfolge dieser Wörter passt. Dabei wird die Struktur der Wörter mit der Grammatik abgeglichen und eine Reihe von Informationen zusammengestellt. Diese Informationen gibt ANTLR nun an Ihren Code weiter, der in Form von Listenern, die Callback-Methoden enthalten, vorliegt.Die angegebene Grammatik muss bestimmte syntaktische Regeln einhalten, unterliegt aber ansonsten fast keinen weiteren Beschränkungen. Insbesondere natürliche Definitionen von Ausdrücken inklusive direkter linksrekursiver Aufrufe sind möglich. Bisher gibt es kein finales Release von ANTLR4. Ein „Early Access“-Release ist jedoch verfügbar. Darin sind die für unser Beispiel verwendeten Features bereits stabil.

Unsere Grammatik in Listing 1 beschreibt eine Sprache für einfache Berechnungen auf ganzen Zahlen. Die Wörter unserer Sprache – Token – werden in der Regel INT beschrieben:

INT : ('0'..'9')+ ;

Die Ziffern 0 bis 9, beliebig oft hintereinander geschrieben, ergeben eine ganze Zahl. Die Wiederholung wird durch das + am Ende der Klammerung angegeben.

Listing 1start : expr EOF ; expr: '(' e=expr ')' -> ParenExpr| left=expr (op='*'|op='/') right=expr -> OpExpr| left=expr (op='+'|op='-') r...

Compilerbau mit ANTLR4 und ASM4 entmystifiziert

E pluribus JVM

Oliver Zeigermann


Im Folgenden möchte ich mit Ihnen zusammen einen kleinen Compiler schreiben. Dabei werden wir uns einer Reihe von Herausforderungen stellen müssen. Zum einen im Compiler-Frontend: Wie analysieren wir die Eingabe des Benutzers?, zum anderen im Backend: Wie machen wir daraus ausführbaren Bytecode?

Die Grammatik

Um unsere Sprache zu beschreiben, benutzen wir eine Grammatik für ANTLR4 (Kasten „Wie funktioniert ANTLR4?“ und [3]) wie in Listing 1. Eine Grammatik besteht aus Regeln, eine Regel wiederum aus einem Namen und einer Beschreibung, welche Eingaben zu der jeweiligen Regel passen. Regeln, deren Namen mit einem Großbuchstaben anfangen, beschreiben Token. Das sind die einzelnen Wörter unserer Sprache. Regeln, deren Namen mit einem Kleinbuchstaben beginnen, beschreiben, wie man diese Wörter zu komplexeren Ausdrücken zusammensetzen kann.

Wie funktioniert ANTLR4?ANTLR4 ist ein Compilergenerator, der aus einer Grammatik eine komplette Grundstruktur für einen Compiler erzeugt. Diese Grundstruktur besteht aus generierten Java-Klassen.Dazu gehört ein Lexer, der aus der Eingabe von einzelnen Zeichen Wörter, so genannte Token, zusammenfasst und an den ebenfalls erzeugten Parser weiter gibt. Der Parser liest diese Wörter ein und prüft, zu welchen Regeln und darin enthaltenen Alternativen die Abfolge dieser Wörter passt. Dabei wird die Struktur der Wörter mit der Grammatik abgeglichen und eine Reihe von Informationen zusammengestellt. Diese Informationen gibt ANTLR nun an Ihren Code weiter, der in Form von Listenern, die Callback-Methoden enthalten, vorliegt.Die angegebene Grammatik muss bestimmte syntaktische Regeln einhalten, unterliegt aber ansonsten fast keinen weiteren Beschränkungen. Insbesondere natürliche Definitionen von Ausdrücken inklusive direkter linksrekursiver Aufrufe sind möglich. Bisher gibt es kein finales Release von ANTLR4. Ein „Early Access“-Release ist jedoch verfügbar. Darin sind die für unser Beispiel verwendeten Features bereits stabil.

Unsere Grammatik in Listing 1 beschreibt eine Sprache für einfache Berechnungen auf ganzen Zahlen. Die Wörter unserer Sprache – Token – werden in der Regel INT beschrieben:

INT : ('0'..'9')+ ;

Die Ziffern 0 bis 9, beliebig oft hintereinander geschrieben, ergeben eine ganze Zahl. Die Wiederholung wird durch das + am Ende der Klammerung angegeben.

Listing 1start : expr EOF ; expr: '(' e=expr ')' -> ParenExpr| left=expr (op='*'|op='/') right=expr -> OpExpr| left=expr (op='+'|op='-') r...

Neugierig geworden?


    
Loading...

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