Schlagwortarchiv für: EBNF

Dies ist der erste Artikel in der Reihe „Entwicklung einer eigenen Java-Program­mier­sprache“, in dem der gesamte Weg der Erstellung einer Program­mier­sprache sowie der Erstellung und Pflege von Werkzeugen für diese Sprache am Beispiel der Entwicklung einer einfachen Sprache aufge­zeigt wird. Am Ende dieses Artikels werden wir einen Inter­preter imple­men­tieren, der zur Ausführung von Programmen in unserer Sprache verwendet werden kann.

Jede Program­mier­sprache hat eine Syntax, die in eine Daten­struktur umgewandelt werden muss, die für die Validierung, Trans­for­mation und Ausführung geeignet ist. In der Regel handelt es sich bei einer solchen Daten­struktur um einen abstrakten Syntaxbaum (AST). Jeder Knoten des Baums steht für ein Konstrukt, das im Quellcode vorkommt. Der Quellcode wird von einem Parser geparst und die Ausgabe ist ein AST.

Sprachen werden schon seit langem entwickelt, so dass wir heute über eine Reihe ausge­reifter Werkzeuge verfügen, darunter auch Parser­ge­ne­ra­toren. Parser­ge­ne­ra­toren nehmen als Eingabe eine Beschreibung der Grammatik einer bestimmten Sprache, und die Ausgabe besteht aus Parsern, Inter­pretern und Compilern.

In diesem Artikel wird das Werkzeug ANTLR betrachtet. ANTLR ist ein Dienst­pro­gramm, das als Eingabe eine Grammatik in Form von RBNFs erhält und Schnittstellen/Klassen (in unserem Fall ist es Java-Code) für das Parsen von Programmen ausgibt. Die Liste der Sprachen, für die Parser generiert werden, finden Sie hier.

Beispiel­gram­matik

Bevor wir uns der eigent­lichen Grammatik zuwenden, wollen wir versuchen, einige der Regeln einer typischen Program­mier­sprache in Worte zu fassen:

• VARIABLE – ist ein IDENTIFIER
• DIGITAL – ist eines der Zeichen 0 1 1 2 3 4 5 6 7 8 9
• NUMBER – ist ein oder mehrere Elemente vom Typ DIGITAL.
• EXPRESSION – ist eine NUMBER
• EXPRESSION – ist eine VARIABLE
• EXPRESSION – ist ein EXPRESSION ‚+‘ EXPRESSION
• EXPRESSION – ist ‚(‚EXPRESSION‘)‘)

Wie Sie aus dieser Liste ersehen können, ist eine Sprach­gram­matik eine Menge von Regeln, die rekursive Verknüp­fungen haben können. Jede Regel kann sich auf sich selbst oder auf eine andere Regel beziehen. ANTLR hat in seinem Arsenal viele Opera­toren, um solche Regeln zu beschreiben.

:    Regelstartbezeichnung
; Ende der Regelmarke
| Alternativer Betreiber
.. Bereichsoperator
~ Verleugnung
. Irgendein Charakter
= Aufgabe
(...)  Unterregel
(...)* Unterregel 0 Mal oder öfter wiederholen
(...)+ Unterregel mindestens einmal wiederholen
(...)? Unterregel fehlt möglicherweise
{...}  Ssemantische Aktionen (in der Sprache, die als Ausgabe verwendet wird – zum Beispiel Java)
[...] Regelparameter

Beispiele für Regeln in ANTLR

Das folgende Beispiel beschreibt die Regeln für ganze Zahlen und Fließkommazahlen:

NUMBER : [0-9]+ ;
FLOAT  : NUMBER '.' NUMBER ;

Es ist sehr wichtig zu wissen, dass die Grammatik nur die Syntax der Sprache beschreibt, aus der der Parser generiert wird. Der Parser wird einen AST erzeugen, der zur Imple­men­tierung der Semantik der Sprache verwendet werden kann. Im vorigen Beispiel haben wir eine Regel zum Parsen einer ganzen Zahl definiert, aber wir haben nicht beschrieben, wie viel Speicher­platz die Zahl belegt (8 Bit, 16, …), ob die Zahl vorzei­chen­be­haftet oder vorzei­chenlos ist. In einigen Program­mier­sprachen kann man zum Beispiel eine Variable verwenden, ohne sie zu dekla­rieren. Es ist auch möglich, den Typ einer Variablen nicht zu dekla­rieren; in diesem Fall wird der Typ zur Laufzeit automa­tisch bestimmt. Alle diese Regeln der Sprach­se­mantik werden nicht in der Grammatik beschrieben, sondern sind in einem anderen Teil der Sprache implementiert.

ANTLR-Lexeme und ‑Ausdrücke

Die ANTLR-Grammatik besteht aus zwei Arten von Regeln: Lexeme und Ausdrücke, die dazu dienen, die Struktur der Grammatik zu definieren und die Einga­be­daten zu parsen.

Lexeme (oder Token) sind Regeln, die einzelne lexika­lische Elemente der Einga­be­sprache definieren, wie z. B. Zahlen, Bezeichner, Opera­ti­ons­zeichen usw. Jedes Lexem entspricht einem bestimmten Typ von Token, der vom Parser für die weitere Verar­beitung verwendet wird. Der lexika­lische Analy­sator scannt den Einga­betext, zerlegt ihn in Token und erstellt eine Folge von Token, die dann an den Parser weiter­ge­geben werden. Token werden in Großbuch­staben geschrieben (z. B. NUMBER, IDENTIFIER).

Ausdrücke sind Regeln, die die Struktur der Grammatik der Einga­be­sprache definieren. Sie beschreiben, wie Token zuein­ander in Beziehung stehen und wie sie zu komple­xeren Konstrukten kombi­niert werden können. Ausdrücke können sowohl Verweise auf Token als auch auf andere Ausdrücke enthalten. Sie werden in camelCase-Schreib­weise geschrieben (zum Beispiel: expression, functionDefinition).

Der Unter­schied zwischen Token und Ausdrücken in ANTLR besteht also darin, dass Token die einzelnen lexika­li­schen Elemente der Einga­be­sprache definieren und sie in Token umwandeln, während Ausdrücke die Struktur der Grammatik definieren und beschreiben, wie Token zu komple­xeren Konstrukten verknüpft werden.

Sprach­liche Anforderungen

Bevor wir mit der Imple­men­tierung einer Sprache beginnen, müssen wir entscheiden, welche Funktionen sie unter­stützen soll. Für unsere Aufgabe, die wir zu Ausbil­dungs­zwecken durch­führen, werden wir eine einfache Grammatik verwenden. Die Sprache wird die folgenden Konstrukte unterstützen:

• Variablen (Typen String, Long, Double);
• Zuwei­sungs­ope­rator (=);
• Arith­me­tische Operationen (+, -, *, /);
• Vergleichs­ope­ra­toren (>, <, >=, <=, ==, !=);
• Bedin­gungs­ope­ra­toren (if, else);
• Funktionen;
• Auf der Konsole drucken (integrierte println-Anweisung).

Grammatik

Schließlich eine vollständige Beschreibung der Grammatik der Sprache:

grammar Jimple;

// Grundregel der Grammatik
program: (statement)* EOF;

// Liste möglicher Aussagen
statement: variableDeclaration
| assignment
| functionDefinition
| functionCall
| println
| return
| ifStatement
| blockStatement
;

// Liste möglicher Ausdrücke
expression: '(' expression ')' #parenthesisExpr
| left=expression op=(ASTERISK | SLASH) right=expression #mulDivExpr
| left=expression op=(PLUS | MINUS) right=expression #plusMinusExpr
| left=expression compOperator right=expression #compExpr
| IDENTIFIER #idExp
| NUMBER #numExpr
| DOUBLE_NUMBER #doubleExpr
| STRING_LITERAL #stringExpr
| functionCall #funcCallExpr
;

// Beschreibungen einzelner Ausdrücke und Aussagen
variableDeclaration: 'var' IDENTIFIER '=' expression ;
assignment: IDENTIFIER '=' expression ;
compOperator: op=(LESS | LESS_OR_EQUAL | EQUAL | NOT_EQUAL | GREATER | GREATER_OR_EQUAL) ;
println: 'println' expression ;
return: 'return' expression ;
blockStatement: '{' (statement)* '}' ;
functionCall: IDENTIFIER '(' (expression (',' expression)*)? ')' ;
functionDefinition: 'fun' name=IDENTIFIER '(' (IDENTIFIER (',' IDENTIFIER)*)? ')' '{' (statement)* '}' ;
ifStatement: 'if' '(' expression ')' statement elseStatement? ;
elseStatement: 'else' statement ;

// Liste der Token
IDENTIFIER : [a-zA-Z_] [a-zA-Z_0-9]* ;
NUMBER : [0-9]+ ;
DOUBLE_NUMBER : NUMBER '.' NUMBER ;
STRING_LITERAL : '"' (~["])* '"' ;
ASTERISK : '*' ;
SLASH : '/' ;
PLUS : '+' ;
MINUS : '-' ;
ASSIGN : '=' ;
EQUAL : '==' ;
NOT_EQUAL : '!=' ;
LESS : '<' ;
LESS_OR_EQUAL : '<=' ;
GREATER : '>' ;
GREATER_OR_EQUAL : '>=' ;
SPACE : [ \r\n\t]+ -> skip;
LINE_COMMENT : '//' ~[\n\r]* -> skip;

Wie Sie vielleicht schon erraten haben, heißt unsere Sprache Jimple (abgeleitet von Jvm Simple). Vielleicht lohnt es sich, einige Punkte zu erläutern, die beim ersten Kennen­lernen von ANTLR vielleicht nicht offen­sichtlich sind.

Labels

Bei der Beschreibung der Regeln einiger Opera­tionen wurde das Label op verwendet, so dass wir dieses Label als Namen der Variablen verwenden können, die den Wert des Operators enthält. Im Prinzip könnten wir auf die Angabe von Labels verzichten, aber in diesem Fall müssen wir zusätz­lichen Code schreiben, um den Wert des Operators aus dem Parse-Baum zu erhalten.

compOperator: op=(LESS | LESS_OR_EQUAL | EQUAL | NOT_EQUAL | GREATER | GREATER_OR_EQUAL) ;

Benannte Regel­al­ter­na­tiven

Wenn in ANTLR eine Regel mit mehreren Alter­na­tiven definiert wird, kann jeder von ihnen ein Name gegeben werden und wird dann ein separater Verar­bei­tungs­knoten im Baum sein. Dies ist sehr praktisch, wenn es notwendig ist, die Verar­beitung jeder Regel­al­ter­native in eine separate Methode zu legen. Es ist wichtig, dass entweder alle Alter­na­tiven oder keine von ihnen einen Namen erhalten. Das folgende Beispiel zeigt, wie das aussehen kann:

expression: '(' expression ')' #parenthesisExpr
 | IDENTIFIER #idExp
 | NUMBER #numExpr

ANTLR erzeugt den folgenden Code:

public interface JimpleVisitor<T> {
    T visitParenthesisExpr(ParenthesisExprContext ctx);
    T visitIdExp(IdExpContext ctx);
    T visitNumExpr(NumExprContext ctx);
}

Kanäle

In ANTLR gibt es ein solches Konstrukt als Kanal (channel). Norma­ler­weise werden Kanäle verwendet, um mit Kommen­taren zu arbeiten, aber da wir in den meisten Fällen nicht prüfen müssen, ob es Kommentare gibt, sollten sie mit -> skip verworfen werden, was wir auch verwendet haben. Es gibt jedoch Fälle, in denen wir die Bedeutung von Kommen­taren oder anderen Konstrukten inter­pre­tieren müssen, dann verwenden Sie Kanäle. ANTLR hat bereits einen einge­bauten Kanal namens HIDDEN, den Sie verwenden können, oder Sie dekla­rieren Ihre eigenen Kanäle für bestimmte Zwecke. Auf diese Kanäle können Sie beim Parsen des Codes weiter zugreifen.

Beispiel für die Ankün­digung und Nutzung eines Kanals

channels { MYLINECOMMENT }
LINE_COMMENT : '//' ~[rn]+ -> channel(MYLINECOMMENT) ;

Fragmente

Zusätzlich zu den Token gibt es in ANTLR ein Konzept, das als Fragment (fragment) bezeichnet wird. Regeln mit dem Präfix fragment können nur von anderen Regeln im Lexer aufge­rufen werden. Sie sind selbst keine Token. Im folgenden Beispiel haben wir die Defini­tionen von Zahlen für verschiedene Zahlen­systeme in Fragmenten zusammengefasst.

NUMBER: DIGITS | OCTAL_DIGITS | HEX_DIGITS;
fragment DIGITS: '1'..'9' '0'..'9'*;
fragment OCTAL_DIGITS: '0' '0'..'7'+;
fragment HEX_DIGITS: '0x' ('0'..'9' | 'a'..'f' | 'A'..'F')+;

So wird eine Zahl in einem belie­bigen Zahlen­system (zum Beispiel «123», «0762» oder «0xac1») als NUMBER-Token und nicht als DIGITS, OCTAL_DIGITS oder HEX_DIGITS behandelt. Fragmente werden in Jimple nicht verwendet.

Instru­mente

Bevor wir mit der Generierung des Parsers beginnen, müssen wir Werkzeuge für die Arbeit mit ANTLR einrichten. Wie wir wissen, ist ein gutes und bequemes Werkzeug die Hälfte des Erfolgs. Zu diesem Zweck müssen wir die ANTLR-Bibliothek herun­ter­laden und Skripte schreiben, um sie auszu­führen. Es gibt auch Maven/Gradle/IntelliJ IDEA Plugins, die wir in diesem Artikel nicht verwenden werden, die aber für eine produktive Entwicklung nützlich sein können.

Wir benötigen die folgenden Skripte:

Skript antlr4.sh

java -Xmx500M -cp ".:/usr/lib/antlr-4.12.0-complete.jar" org.antlr.v4.Tool $@

Skript grun.sh

java -Xmx500M -cp ".:/usr/lib/antlr-4.12.0-complete.jar" org.antlr.v4.gui.TestRig $@

 

Parser-Generierung

Speichern Sie die Grammatik in der Datei Jimple.g4. Führen Sie dann das Skript wie folgt aus:

antlr4.sh Jimple.g4 -package org.jimple.lang -visitor

Mit dem Parameter ‑package können Sie das Java-package angeben, in dem der Code generiert werden soll. Mit dem Parameter ‑visitor können Sie die Schnitt­stelle Jimple­Vi­sitor generieren, die das Visitor-Muster imple­men­tiert.

Nach erfolg­reicher Ausführung des Skripts erscheinen mehrere Dateien im aktuellen Verzeichnis: JimpleParser.java, JimpleLexer.java, JimpleListener.java, JimpleVisitor.java.

Die ersten beiden Dateien enthalten den generierten Parser- bzw. Lexer-Code. Die beiden anderen Dateien enthalten die Schnitt­stellen für die Arbeit mit dem Parse-Baum. In diesem Artikel werden wir die Jimple­Vi­sitor-Schnitt­stelle verwenden, genauer gesagt ist Jimple­Ba­se­Vi­sitor  — ebenfalls eine generierte Klasse, die die Jimple­Vi­sitor-Schnitt­stelle imple­men­tiert und Imple­men­tie­rungen aller Methoden enthält. So können wir nur die Methoden überschreiben, die wir benötigen.

Imple­men­tierung des Interpreters

Schließlich kommen wir zum inter­es­san­testen Teil — der Imple­men­tierung des Inter­preters. Obwohl wir uns in diesem Artikel nicht mit der Überprüfung des Codes auf Fehler befassen werden, werden wir dennoch Inter­pre­ta­ti­ons­fehler imple­men­tieren. Als erstes erstellen wir eine Klasse Jimple­Inter­preter  mit der eval-Methode, deren Input ein String mit Jimple-Code sein wird. Als nächstes müssen wir den Quellcode mit JimpleLexer in Token zerlegen und dann mit Jimple­Parser einen AST-Baum erstellen.

public class JimpleInterpreter {
    public Object eval(final String input) {
        // Parsen des Quellcodes in Token
        final JimpleLexer lexer = new JimpleLexer(CharStreams.fromString(input));
        // Erstellen Sie einen AST-Baum
        final JimpleParser parser = new JimpleParser(new CommonTokenStream(lexer));
        // Erstellen Sie ein Objekt der Klasse JimpleInterpreterVisitor
        final JimpleInterpreterVisitor interpreterVisitor = new JimpleInterpreterVisitor(new JimpleContextImpl(stdout));
        // Starten Sie den Interpreter
        return interpreterVisitor.visitProgram(parser.program());
    }
}

Wir haben einen Syntaxbaum. Fügen wir nun mit Hilfe der von uns geschrie­benen Klasse Jimple­Inter­pre­ter­Vi­sitor, die den AST durch Aufruf der entspre­chenden Methoden durch­läuft, einige Seman­tiken hinzu. Da die Wurzel­regel unserer Grammatik die program Regel ist (siehe oben program: (statement)* EOF), beginnt die Baumdurch­querung dort. Dazu rufen wir die Standard­me­thode visit­Program des Jimple­Inter­pre­ter­Vi­sitor-Objekts auf, mit einem Objekt der Klasse Program­Context als Eingabe. Die ANTLR-Imple­men­tierung besteht aus dem Aufruf der visitChildren(RuleNode node-Methode, die alle Kinder eines bestimmten Baumknotens durch­läuft und für jedes von ihnen die visit-Methode aufruft.

// Von ANTLR generierter Code
public class JimpleBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements JimpleVisitor<T> {
    @Override
    public T visitProgram(JimpleParser.ProgramContext ctx) {
        return visitChildren(ctx);
    }

    // Andere Methoden werden der Kürze halber weggelassen
}

Wie Sie sehen, ist Jimple­Ba­se­Vi­sitor eine generische Klasse, für die Sie den Verar­bei­tungstyp für jeden Knoten definieren müssen. In unserem Fall ist dies die Object-Klasse, da Ausdrücke Werte unter­schied­lichen Typs zurück­geben können. Norma­ler­weise muss ein Ausdruck einen Wert zurück­geben, eine Anweisung gibt jedoch nichts zurück. Das ist ihr Unter­schied. Bei Geneh­migung können wir null zurück­geben. Um jedoch nicht verse­hentlich auf eine NullPoin­ter­Ex­ception zu stoßen, geben wir anstelle von null ein Objekt vom Typ Object zurück, das global in der Jimple­Inter­preter-Klasse definiert ist:

Wie Sie sehen können, Jimple­Ba­se­Vi­sitor — ist eine generische Klasse, für die wir die Art der Verar­beitung für jeden Knoten definieren müssen. In unserem Fall ist dies die Klasse Object, da Ausdrücke Werte unter­schied­lichen Typs zurück­geben können. Norma­ler­weise sollte ein Ausdruck (expression) einen Wert zurück­geben, während eine Anweisung ((statement) nichts zurückgibt. Das ist der Unter­schied zwischen ihnen. Im Falle einer Anweisung können wir null zurück­geben. Um jedoch eine NullPoin­ter­Ex­ception zu vermeiden, geben wir anstelle von null ein Objekt vom Typ Object zurück, das global in der Klasse Jimple­Inter­preter definiert ist:

public static final Object VOID = new Object();

Die Klasse Jimple­Inter­pre­ter­Vi­sitor erweitert die Klasse Jimple­Ba­se­Vi­sitor und überschreibt nur die Methoden, an denen wir inter­es­siert sind. Schauen wir uns die Imple­men­tierung des einge­bauten println-Operators an, der in der Grammatik als println: ‚println‘ expression; beschrieben wird. Als erstes müssen wir den Ausdruck expression berechnen, dazu müssen wir die visit-Methode aufrufen und ihr das expression-Objekt aus dem aktuellen Println­Context übergeben. In der visit­Println-Methode inter­es­sieren wir uns überhaupt nicht dafür, wie der Ausdruck ausge­wertet wird, die entspre­chende Methode ist für die Auswertung jeder Regel (Kontext) zuständig. Die Methode visitStringExpr.rpreter wird zum Beispiel verwendet, um ein String-Literal auszuwerten:

public class JimpleInterpreterVisitor extends JimpleBaseVisitor<Object> {
    @Override
    public Object visitPrintln(final JimpleParser.PrintlnContext ctx) {
        final Object result = visit(ctx.expression());
        System.out.println(result);
        return null;
    }
    
    @Override
    public Object visitStringExpr(final JimpleParser.StringExprContext ctx) {
        // Gibt ein String-Literal zurück
        return cleanStringLiteral(ctx.STRING_LITERAL().getText());
    }


    private String cleanStringLiteral(final String literal) {
        // Anführungszeichen aus der Zeichenfolge entfernen
        return literal.length() > 1 ? literal.substring(1, literal.length() - 1) : literal;
    }

    // Andere Methoden werden der Kürze halber weggelassen
}

Indem nur diese Methoden imple­men­tiert werden, unter­stützt der Inter­preter bereits println und String­li­terale, so dass wir den Code println „Hello, Jimple!“ ausführen können.

Starten des Interpreters

Um den Inter­preter zu starten, müssen wir eine Standard-Main-Methode erstellen, die nach kleinen Prüfungen unter Verwendung der Klasse Jimple­Inter­preter unseren Code ausführt:

public class MainApp {
    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("usage: jimple input.jimple");
            System.exit(1);
        }
        
        Path path = Paths.get(args[0]);
        if (!Files.exists(path)) {
            System.err.println("File not found: " + path);
            System.exit(1);
        }
        
        new JimpleInterpreter().eval(path);
    }
}

Einzel­heiten der Durchführung

Es ist nicht nötig, den gesamten Code der Inter­preter-Imple­men­tierung wieder­zu­geben, der Link zu den Quellen befindet sich am Ende des Artikels. Ich möchte jedoch auf einige inter­es­sante Details eingehen.

Wie bereits erwähnt, basiert der Inter­preter auf dem Visitor-Muster, welches die Knoten des AST-Baums besucht und die entspre­chenden Anwei­sungen ausführt. Während der Codeaus­führung erscheinen neue Bezeichner (Variablen- und/oder Funkti­ons­namen) im aktuellen Kontext, die irgendwo gespei­chert werden müssen. Zu diesem Zweck schreiben wir eine Klasse Jimple­Context, die nicht nur diese Bezeichner, sondern auch den aktuellen Ausfüh­rungs­kontext von verschach­telten Codeblöcken und Funktionen speichert, da eine lokale Variable und/oder ein Funkti­ons­pa­ra­meter nach dem Verlassen ihres Geltungs­be­reichs gelöscht werden muss.

@Override
public Object handleFunc(FunctionSignature func, List<String> parameters, List<Object> arguments, FunctionDefinitionContext ctx) {
    Map<String, Object> variables = new HashMap<>(parameters.size());
    for (int i = 0; i < parameters.size(); i++) {
        variables.put(parameters.get(i), arguments.get(i));
    }
    // Erstellen Sie einen neuen Funktionsparameterbereich und verschieben Sie ihn auf den Stapel
    context.pushCallScope(variables);
    // Ausführungsfunktionsausdrücke wurden der Kürze halber weggelassen
    // Entfernen Sie den Umfang der Funktionsparameter vom Stapel
    context.popCallScope();
    return functionResult;
}

In unserer Sprache speichert eine Variable den Wert eines Typs, der zur Laufzeit definiert wird. In den folgenden Anwei­sungen kann dieser Typ dann geändert werden. Im Grunde genommen haben wir eine Sprache mit dynami­scher Typisierung. Aller­dings gibt es immer noch eine Typüber­prüfung in Fällen, in denen es sinnlos ist, eine Operation auszu­führen. Zum Beispiel kann eine Zahl nicht durch eine Zeichen­kette dividiert werden.

Warum brauchen Sie zwei Durchgänge?

Die ursprüng­liche Version des Inter­preters sah vor, für jede Regel eine Methode zu imple­men­tieren. Findet beispiels­weise die Methode zur Funkti­ons­de­kla­ration eine Funktion mit diesem Namen (und der Anzahl der Parameter) im aktuellen Kontext, wird eine Ausnahme ausgelöst, andern­falls wird die Funktion dem aktuellen Kontext hinzu­gefügt. Die Methode des Funkti­ons­aufrufs funktio­niert auf die gleiche Weise. Wenn keine Funktion gefunden wird, wird eine Ausnahme ausgelöst, andern­falls wird die Funktion aufge­rufen. Dieser Ansatz funktio­niert, aber er erlaubt es nicht, eine Funktion aufzu­rufen, bevor sie definiert ist. Der folgende Code funktio­niert zum Beispiel nicht:

var result = 9 + 10

println "Result is " + add(result, 34)

fun add (a, b){
    return a + b
}

In diesem Fall gibt es zwei Ansätze. Der erste besteht darin, dass eine Funktion vor ihrer Verwendung definiert werden muss (was für Sprach­be­nutzer nicht sehr praktisch ist). Die zweite besteht darin, zwei Durch­gänge durch­zu­führen. Der erste Durchlauf wird benötigt, um alle Funktionen zu finden, die im Code definiert wurden. Der zweite Durchgang dient der direkten Ausführung des Codes. In meiner Imple­men­tierung habe ich den zweiten Ansatz gewählt. Man sollte die Imple­men­tierung der visit­Func­tion­De­fi­nition Methode in eine eigene Klasse verschieben, die die uns bereits bekannte generierte Klasse JimpleBaseVisitor<T> erweitert.

// Die Klasse findet alle Funktionen im Code und registriert sie im Kontext
public class FunctionDefinitionVisitor extends JimpleBaseVisitor<Object> {
    private final JimpleContext context;
    private final FunctionCallHandler handler;

    public FunctionDefinitionVisitor(final JimpleContext context, final FunctionCallHandler handler) {
        this.context = context;
        this.handler = handler;
    }

    @Override
    public Object visitFunctionDefinition(final JimpleParser.FunctionDefinitionContext ctx) {
        final String name = ctx.name.getText();
        final List<String> parameters = ctx.IDENTIFIER().stream().skip(1).map(ParseTree::getText).toList();
        final var funcSig = new FunctionSignature(name, parameters.size());
        context.registerFunction(funcSig, (func, args) -> handler.handleFunc(func, parameters, args, ctx));
        return VOID;
    }
}

Jetzt haben wir eine Klasse, die wir verwenden können, bevor wir die Inter­pre­ter­klasse direkt starten. Sie füllt unseren Kontext mit den Defini­tionen aller Funktionen, die wir in der Inter­pre­ter­klasse aufrufen werden.

Wie sieht AST aus?

Um AST zu visua­li­sieren, müssen wir das Dienst­pro­gramm grun verwenden (siehe oben). Starten Sie dazu grun mit den Parametern Jimple program ‑gui (der erste Parameter ist der Name der Grammatik, der zweite Parameter ist der Name der Regel). Dadurch wird ein Fenster mit dem AST-Baum geöffnet. Bevor Sie dieses Dienst­pro­gramm ausführen, müssen Sie den mit ANTLR erzeugten Code kompilieren.

# Parser generieren
antlr4.sh Jimple.g4

# Kompilieren Sie den generierten Code
javac -cp ".:/usr/lib/jvm/antlr-4.12.0-complete.jar" Jimple*.java

# Führen Sie das grun aus
grun.sh Jimple program -gui

# Geben Sie den Code ein: „println „Hallo, Jimple!““.
# Drücken Sie Strg+D (Linux) oder Strg+Z (Windows)

Für den Jimple-Code println „Hello, Jimple!“ wird der folgende AST erzeugt:

Zusam­men­fassung

In diesem Artikel haben Sie sich mit Konzepten wie lexika­li­schen und syntak­ti­schen Analy­sa­toren vertraut gemacht. Sie haben das ANTLR-Tool verwendet, um solche Parser zu erzeugen. Sie haben gelernt, wie man eine ANTLR-Grammatik schreibt. Schließlich waren wir in der Lage, eine einfache Sprache zu erstellen, d. h. wir haben einen Inter­preter für sie entwickelt. Als Bonus konnten wir die AST visualisieren.

Der gesamte Quellcode des Inter­preters kann hier einge­sehen werden.

Referenzen

• https://www.antlr.org/
• https://en.wikipedia.org/wiki/Abstract_syntax_tree
• https://en.wikipedia.org/wiki/Compiler-compiler