Entwicklung einer eigenen Program­mier­sprache in Java+ANTLR: Fehlerdiagnose

Dies ist der zweite Artikel in der Serie „Entwicklung unserer Program­mier­sprache in Java“. Der erste Artikel kann hier gelesen werden.

In der aktuellen Phase haben wir einen Inter­preter, der in der Lage ist, die Befehle unserer Sprache auszu­führen. Dies reicht jedoch nicht aus, wenn wir den Code auf Fehler überprüfen und diese dem Benutzer auf eine klare Weise anzeigen wollen. In diesem Artikel werden wir die Hinzu­fügung von Fehler­dia­gnosen zur Sprache betrachten. Die Durch­führung einer Fehler­analyse in Ihrer eigenen Program­mier­sprache ist ein wichtiger Schritt in der Sprach­ent­wicklung. Die Verwendung leistungs­starker Werkzeuge wie ANTLR ermög­licht es Ihnen, in kurzer Zeit recht effiziente Codeanalyse-Tools zu imple­men­tieren, die Ihnen helfen, poten­zielle Probleme in einem Programm in frühen Entwick­lungs­stadien zu erkennen, was die Software­qua­lität verbessert und die Produk­ti­vität der Entwickler steigert.

Klassi­fi­zierung von Fehlern

Es gibt verschiedene Arten von Fehlern, aber im Allge­meinen können sie in drei Kategorien unter­teilt werden: Syntax-, Semantik- und Laufzeit­fehler.

Syntax­fehler treten aufgrund der Verletzung der Syntax­regeln einer bestimmten Program­mier­sprache auf. Syntax­regeln definieren, wie Anwei­sungen und Ausdrücke im Code organi­siert sein sollten.

Beispiel für einen Syntax­fehler (fehlendes abschlie­ßendes Anführungszeichen):

println("Hello, World!)

Semantische Fehler treten auf, wenn ein Programm kompi­liert und sogar ausge­führt wird, das Ergebnis jedoch anders ist als erwartet. Diese Art von Fehler ist die schwie­rigste. Seman­tische Fehler können durch das Missver­ständnis des Program­mierers bezüglich der Sprache oder der anste­henden Aufgabe verur­sacht werden. Zum Beispiel, wenn ein Program­mierer ein schlechtes Verständnis der Opera­tor­rang­folge hat, könnte er folgenden Code schreiben:

var a = 1 + 2 * 3

Er könnte erwarten, dass die Variable a gleich 9 ist, aber tatsächlich wird sie gleich 7. Dies geschieht, weil der Multi­pli­ka­ti­ons­ope­rator eine höhere Priorität als der Additi­ons­ope­rator hat. Ein seman­ti­scher Fehler kann norma­ler­weise während des Debuggens oder durch umfang­reiche Tests des Programms entdeckt werden.

Laufzeit­fehler, auch bekannt als „Excep­tions“, treten während der Programm­aus­führung auf. Solche Fehler können aufgrund falscher Daten­eingabe, dem Versuch, auf eine nicht vorhandene Datei zuzugreifen, und in vielen anderen Szenarien auftreten. Einige Laufzeit­fehler können in einem Programm gehändelt werden, aber wenn dies nicht geschieht, stürzt das Programm norma­ler­weise ab.

Neben Fehlern ist es auch wichtig, poten­zielle Probleme oder nicht offen­sicht­liche Situa­tionen zu erkennen, die im strengen Sinne keine Fehler sind, aber zu unerwünschten Konse­quenzen führen können. Zum Beispiel könnte es sich um eine ungenutzte Variable handeln, die Verwendung veral­teter Funktionen oder eine überflüssige Operation. In all diesen Fällen können dem Benutzer Warnungen angezeigt werden.

Jimple­Ba­se­Vi­sitor

Um Fehler und Warnungen zu identi­fi­zieren, benötigen wir die abstrakte Klasse JimpleBaseVisitor (erzeugt von ANTLR), die uns bereits aus dem ersten Artikel bekannt ist und standard­mäßig das JimleVisitor-Interface imple­men­tiert. Sie ermög­licht es uns, den AST-Baum (Abstract Syntax Tree) zu durch­laufen, und basierend auf der Analyse seiner Knoten wird entscheiden, ob es sich um einen Fehler, eine Warnung oder einen normalen Teil des Codes handelt. Im Wesent­lichen ist die Diagnose von Fehlern fast nicht anders als das Inter­pre­tieren von Code, außer wenn wir I/O durch­führen oder auf externe Ressourcen zugreifen müssen. Zum Beispiel, wenn ein Konso­len­aus­ga­be­befehl ausge­führt wird, dann ist es unsere Aufgabe zu überprüfen, ob der als Argument übergebene Datentyp gültig ist, ohne es direkt an die Konsole auszugeben.

Lassen Sie uns die Klasse JimpleDiagnosticTool erstellen, die JimleBaseVisitor erbt und die gesamte Logik des Findens und Speicherns von Fehlern kapselt:

class JimpleDiagnosticTool extends JimpleBaseVisitor<ValidationInfo> {
    private Set<Issue> issues = new LinkedHashSet<>();
}

record Issue(IssueType type, String message, int lineNumber, int lineOffset, String details) {}

Diese Klasse enthält eine Liste vom Typ Issue, welcher Infor­ma­tionen über einen spezi­fi­schen Fehler enthält.

Es ist bekannt, dass jede Methode einer gegebenen Klasse einen Wert eines bestimmten Typs zurück­geben muss. In unserem Fall werden wir Infor­ma­tionen über den Typ des Knotens im Baum zurück­geben – ValidationInfo. Diese Klasse enthält auch Infor­ma­tionen über den möglichen Wert, dies wird uns helfen, einige seman­tische oder Laufzeit­fehler zu identifizieren.

record ValidationInfo(ValidationType type, Object value) {}

enum ValidationType {
    /**
     * Expression returns nothing.
     */
    VOID,

    /**
     * Expression is String
     */
    STRING,

    /**
     * Expression is double
     */
    DOUBLE,

    /**
     * Expression is long
     */
    NUMBER,

    /**
     * Expression is boolean
     */
    BOOL,

    /**
     * Expression contains error and analysing in another context no makes sense.
     */
    SKIP,

    /**
     * When object can be any type. Used only in Check function definition mode.
     */
    ANY,

    /**
     * Tree part is function declaration
     */
    FUNCTION_DEFINITION
}

Sie sollten auf den Wert von ValidationType.SKIP achten. Er wird verwendet, wenn ein Fehler gefunden und bereits in einem Teil des Baums regis­triert wurde und eine weitere Analyse dieses Baumknotens nicht sinnvoll ist. Wenn zum Beispiel ein Argument in einem Summen­aus­druck einen Fehler enthält, wird das zweite Argument des Ausdrucks nicht analysiert.

ValidationInfo checkBinaryOperatorCommon(ParseTree leftExp, ParseTree rightExp, Token operator) {
    ValidationInfo left = visit(leftExp);
    if (left.isSkip()) {
        return ValidationInfo.SKIP;
    }
    ValidationInfo right = visit(rightExp);
    if (right.isSkip()) {
        return ValidationInfo.SKIP;
    }
    // code omitted
}

Listers vs Visitors

Before moving on, let’s take a look at another ANTLR-generated interface  (), which can also be used if we need traverse the AST tree. What is the diffe­rence between them? The biggest diffe­rence between these mecha­nisms is that listener methods are always called by ANTLR on a per-node basis, whereas visitor methods must bypass their child elements with explicit calls. And if the programmer does not call on child nodes, then these nodes are not visited, i.e. we have the ability to control tree traversal. For example, in our imple­men­tation, the function body is first visited once in its entirety (mode ) to detect errors in the entire function (all if and else blocks), and several times with specific argument values:

Bevor wir fortfahren, werfen wir einen Blick auf ein weiteres von ANTLR generiertes Interface, JimpleListener (pattern Observer), das ebenfalls verwendet werden kann, wenn wir den AST-Baum durch­laufen müssen. Was ist der Unter­schied zwischen ihnen? Der größte Unter­schied zwischen diesen Mecha­nismen ist, dass Listener-Methoden immer von ANTLR auf einer pro-Knoten-Basis aufge­rufen werden, während Besucher-Methoden ihre Kind-Elemente mit expli­ziten Aufrufen umgehen müssen. Und wenn der Program­mierer nicht visit() auf Kindknoten aufruft, dann werden diese Knoten nicht besucht, d.h. wir haben die Möglichkeit, die Baumdurch­querung zu steuern. In unserer Imple­men­tierung wird beispiels­weise der Funktionskörper

zunächst einmal in seiner Gesamtheit (Modus checkFuncDefinition==true) besucht, um Fehler in der gesamten Funktion (alle if- und else-Blöcke) zu erkennen, und dann mehrmals mit spezi­fi­schen Argumentwerten:

@Override
ValidationInfo visitIfStatement(IfStatementContext ctx) {
    // calc expression in "if" condition
    ValidationInfo condition = visit(ctx.expression());

    if (checkFuncDefinition) {
        visit(ctx.statement());
        // as it's just function definition check, check else statement as well
        JimpleParser.ElseStatementContext elseStatement = ctx.elseStatement();
        if (elseStatement != null) {
            visit(elseStatement);
        }
        return ValidationInfo.VOID;
    }

    // it's not check function definition, it's checking of certain function call
    if (condition.isBool() && condition.hasValue()) {
        if (condition.asBoolean()) {
            visit(ctx.statement());
        } else {
            JimpleParser.ElseStatementContext elseStatement = ctx.elseStatement();
            if (elseStatement != null) {
                visit(elseStatement);
            }
        }
    }

    return ValidationInfo.VOID;
}

Das „Visitor“ Muster eignet sich sehr gut, wenn wir für jeden Baumknoten einen bestimmten Wert zuordnen müssen. Das ist genau das, was wir brauchen.

Abfangen von syntak­ti­schen Fehlern

Um einige Syntax­fehler im Code zu finden, müssen wir die Schnitt­stelle ANTLRErrorListener imple­men­tieren. Diese Schnitt­stelle enthält vier Methoden, die (vom Parser und/oder Lexer) im Falle eines Fehlers oder undefi­nierten Verhaltens aufge­rufen werden:

interface ANTLRErrorListener {
    void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine, String msg, RecognitionException e);
    void reportAmbiguity(Parser recognizer, DFA dfa, int startIndex, int stopIndex, boolean exact, BitSet ambigAlts, ATNConfigSet configs);
    void reportAttemptingFullContext(Parser recognizer, DFA dfa, int startIndex, int stopIndex, BitSet conflictingAlts, ATNConfigSet configs);
    void reportContextSensitivity(Parser recognizer, DFA dfa, int startIndex, int stopIndex, int prediction, ATNConfigSet configs);
} 

Der Name der ersten Methode (syntaxError) spricht für sich selbst; sie wird im Falle eines Syntax­fehlers aufge­rufen. Die Imple­men­tierung ist recht einfach: Wir müssen die Fehler­infor­ma­tionen in ein Objekt des Typs Issue umwandeln und es der Liste der Fehler hinzufügen:

@Override
void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine, String msg, RecognitionException e) {
    int offset = charPositionInLine + 1;
    issues.add(new Issue(IssueType.ERROR, msg, line, offset, makeDetails(line, offset)));
}

Die verblei­benden drei Methoden können ignoriert werden. ANTLR imple­men­tiert dieses Interface auch selbst (siehe Klasse ConsoleErrorListener) und sendet Fehler an den standard error stream (System.err). Um es und andere Standard-Handler zu deakti­vieren, müssen wir die Methode removeErrorListeners am Parser und Lexer aufrufen:

    // remove default error handlers
    lexer.removeErrorListeners();
    parser.removeErrorListeners();

Ein anderer Typ eines Syntax­fehlers basiert auf den Regeln einer bestimmten Sprache. Zum Beispiel wird in unserer Sprache eine Funktion durch ihren Namen und die Anzahl der Argumente identi­fi­ziert. Wenn der Analy­sator auf einen Funkti­ons­aufruf trifft, überprüft er, ob eine Funktion mit demselben Namen und der gleichen Anzahl an Argumenten existiert. Wenn nicht, dann wird ein Fehler ausgelöst. Um dies zu tun, müssen wir die Methode visitFunctionCall überschreiben:

@Override
ValidationInfo visitFunctionCall(FunctionCallContext ctx) {
    String funName = ctx.IDENTIFIER().getText();
    int argumentsCount = ctx.expression().size();
    var funSignature = new FunctionSignature(funName, argumentsCount, ctx.getParent());
    // find a function in the context by signature (name+number of arguments)
    var handler = context.getFunction(funSignature);

    if (handler == null) {
        addIssue(IssueType.ERROR, ctx.start, "Function with such signature not found: " + funName);
        return ValidationInfo.SKIP;
    }

    // code omitted
}

Prüfen wir die if-Konstruktion. Jimple setzt voraus, dass der Ausdruck in der if-Bedingung vom Typ boolean ist:

@Override
ValidationInfo visitIfStatement(IfStatementContext ctx) {
    // visit expression
    ValidationInfo condition = visit(ctx.expression());
    // skip if expression contains error
    if (condition.isSkip()) {
        return ValidationInfo.SKIP;
    }

    if (!condition.isBool()) {
        addIssue(IssueType.WARNING, ctx.expression().start, "The \"if\" condition must be of boolean type only. But found: " + condition.type());
    }

    // code omitted
}

Der aufmerksame Leser wird feststellen, dass wir in diesem Fall eine Warnung und keinen Fehler hinzu­gefügt haben. Dies geschieht aufgrund der Tatsache, dass unsere Sprache dynamisch ist und wir nicht immer die genauen Infor­ma­tionen über den Typ des Ausdrucks kennen.

Identi­fi­zieren seman­ti­scher Fehler

Wie bereits erwähnt, sind seman­tische Fehler schwer zu finden und können oft nur beim Debuggen oder Testen des Programms gefunden werden. Einige davon können jedoch bereits in der Kompi­lie­rungs­phase identi­fi­ziert werden. Wenn wir beispiels­weise wissen, dass die Funktion zurückgibt, können wir eine Warnung anzeigen, wenn ein Divisi­ons­aus­druck diese Funktion als Divisor verwendet. Die Division durch null wird in der Regel als seman­ti­scher Fehler betrachtet, da die Division durch null in der Mathe­matik keinen Sinn ergibt.

Ein Beispiel für die Fehler­er­kennung „Division by zero“: wird ausgelöst, wenn ein Ausdruck als Divisor verwendet wird, der immer den Wert 0 zurückgibt.

ValidationInfo checkBinaryOperatorForNumeric(ValidationInfo left, ValidationInfo right, Token operator) {
    if (operator.getType() == JimpleParser.SLASH && right.hasValue() && ((Number) right.value()).longValue() == 0) {
        // if we have value of right's part of division expression and it's zero
        addIssue(IssueType.WARNING, operator, "Division by zero");
    }

    // code omitted
}

Laufzeit­fehler

Laufzeit­fehler sind ebenfalls schwer oder sogar unmöglich in der Kompi­lie­rungs-/Inter­pre­tie­rungs­phase zu erkennen. Dennoch können einige solcher Fehler identi­fi­ziert werden. Zum Beispiel, wenn eine Funktion sich selbst aufruft (entweder direkt oder durch eine andere Funktion), kann dies zu einem Stapel­überlauf-Fehler (Stack­Overflow) führen. Das Erste, was wir tun müssen, ist eine Liste (Set) zu dekla­rieren, in der wir die Funktionen speichern, die gerade aufge­rufen werden. Die Überprüfung selbst kann (und sollte) in der Methode handle­Fun­c­In­ternal zur Verar­beitung des Funkti­ons­aufrufs platziert werden. Zu Beginn dieser Methode überprüfen wir, ob der aktuelle  Function­De­fi­ni­tionContext (Funkti­ons­de­kla­ra­ti­ons­kontext) auf der Liste der bereits aufge­ru­fenen Funktionen steht, und falls dies der Fall ist, proto­kol­lieren wir eine Warnung und unter­brechen die weitere Verar­beitung der Funktion. Wenn nicht, dann fügen wir den aktuellen Kontext zu unserer Liste hinzu, und der Rest der Logik folgt. Beim Verlassen von handle­Fun­c­In­ternal muss der aktuelle Funkti­ons­kontext aus der Liste entfernt werden. Hier sollte angemerkt werden, dass wir in diesem Fall nicht nur einen poten­zi­ellen Stack­Overflow identi­fi­ziert haben, sondern auch denselben Fehler beim Diagnos­ti­zieren von Fehlern vermieden haben, nämlich beim Schleifen der Methode handleFuncInternal.

Set<FunctionDefinitionContext> calledFuncs = new HashSet<>();

ValidationInfo handleFuncInternal(List<String> parameters, List<Object> arguments, FunctionDefinitionContext ctx) {
    if (calledFuncs.contains(ctx)) {
        addIssue(IssueType.WARNING, ctx.name, String.format("Recursive call of function '%s' can lead to StackOverflow", ctx.name.getText()));
        return ValidationInfo.SKIP;
    }
    calledFuncs.add(ctx);
    
    // other checkings

    calledFuncs.remove(ctx);

    // return resulting ValidationInfo
}

Kontroll-/Daten­fluss­analyse

Für eine tiefere Unter­su­chung des Programm­codes, Optimierung und Identi­fi­zierung komplexer Fehler werden auch die Kontroll­fluss­analyse und Daten­fluss­analyse verwendet.

Die Kontroll­fluss­analyse konzen­triert sich darauf zu verstehen, welche Teile eines Programms in Abhän­gigkeit von verschie­denen Bedin­gungen und Steuer­struk­turen wie bedingten (if-else) Anwei­sungen, Schleifen und Verzwei­gungen ausge­führt werden. Sie ermög­licht es, die Ausfüh­rungs­pfade des Programms zu identi­fi­zieren und poten­zielle Fehler zu erkennen, die mit einer fehler­haften Steuer­logik zusam­men­hängen. Zum Beispiel unerreich­barer Code oder poten­zielle Programmaufhänger.

Die Daten­fluss­analyse hingegen konzen­triert sich darauf, wie Daten innerhalb eines Programms verteilt und verwendet werden. Sie hilft, poten­zielle Daten­pro­bleme wie die Verwendung von nicht initia­li­sierten Variablen, Daten­ab­hän­gig­keiten und mögliche Speicher­lecks („memory leaks“) zu identi­fi­zieren. Die Daten­fluss­analyse kann auch Fehler erkennen, die mit falschen Daten­ope­ra­tionen zusam­men­hängen, wie die Verwendung falscher Typen oder inkor­rekter (überflüs­siger) Berechnungen.

Zusam­men­fassung

In diesem Artikel haben wir den Prozess des Hinzu­fügens von Fehler- und Warndia­gnosen zu Ihrer Program­mier­sprache unter­sucht. Wir haben gelernt, was ANTLR von Haus aus für die Proto­kol­lierung von Syntax­fehlern bietet. Außerdem haben wir eine Behandlung einiger Fehler und poten­zi­eller Probleme während der Programm­aus­führung implementiert.

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

Links

• https://www.antlr.org/api/Java/org/antlr/v4/runtime/ANTLRErrorListener.html
• https://de.wikipedia.org/wiki/Kontrollflussgraph
• https://en.wikipedia.org/wiki/Control_flow_analysis
• https://de.wikipedia.org/wiki/Datenflussanalyse

Ruslan Absaliamov

See Full Bio