Ich habe VIEL darüber gesucht und konnte nichts Nützliches finden, das mir WIRKLICH hilft, einen AST zu bauen. Ich weiß bereits, dass ANTLR4 AST nicht wie früher ANTLR3 erstellt. Alle sagen: “Hey, benutze Besucher!”, aber ich konnte kein Beispiel oder eine detailliertere Erklärung dazu finden, WIE ich das machen kann …

Ich habe eine Grammatik muss wie C, aber mit allen Befehlen in Portugiesisch (Portugal Programmiersprache) geschrieben. Ich kann den Parse-Baum einfach mit ANTLR4 generieren. Meine Frage ist: Was muss ich jetzt tun, um ein AST zu erstellen?

Übrigens, ich benutze Java und IntelliJ …

EDIT1: Am ehesten konnte ich die Antwort auf dieses Thema verwenden: Gibt es ein einfaches Beispiel für die Verwendung von antlr4 zum Erstellen eines AST aus dem Java-Quellcode und zum Extrahieren von Methoden, Variablen und Kommentaren? Aber es gibt nur den Namen der besuchten Methoden aus.

Da der erste Versuch bei mir nicht wie erwartet funktionierte, habe ich versucht zu verwenden dieses Tutorial von ANTLR3, aber ich konnte nicht herausfinden, wie man StringTamplate anstelle von ST verwendet …

Das Buch lesen Die endgültige ANTLR 4-Referenz Ich konnte auch nichts über ASTs finden.

EDIT2: Jetzt habe ich eine Klasse, um die DOT-Datei zu erstellen, ich muss nur noch herausfinden, wie Besucher richtig verwendet werden

Ok, bauen wir ein einfaches mathematisches Beispiel. Ein AST zu bauen ist für eine solche Aufgabe völlig übertrieben, aber es ist eine schöne Art, das Prinzip zu zeigen.

Ich mache es in C#, aber die Java-Version wäre sehr ähnlich.

Die Grammatik

Lassen Sie uns zunächst eine sehr grundlegende mathematische Grammatik schreiben, mit der wir arbeiten können:

grammar Math;

compileUnit
    :   expr EOF
    ;

expr
    :   '(' expr ')'                         # parensExpr
    |   op=('+'|'-') expr                    # unaryExpr
    |   left=expr op=('*'|"https://stackoverflow.com/") right=expr    # infixExpr
    |   left=expr op=('+'|'-') right=expr    # infixExpr
    |   func=ID '(' expr ')'                 # funcExpr
    |   value=NUM                            # numberExpr
    ;

OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: "https://stackoverflow.com/";

NUM :   [0-9]+ ('.' [0-9]+)? ([eE] [+-]? [0-9]+)?;
ID  :   [a-zA-Z]+;
WS  :   [ trn] -> channel(HIDDEN);

Ziemlich einfaches Zeug, wir haben eine Single expr Regel, die alles behandelt (Vorrangregeln usw.).

Die AST-Knoten

Lassen Sie uns dann einige AST-Knoten definieren, die wir verwenden werden. Diese sind vollständig benutzerdefiniert und Sie können sie so definieren, wie Sie möchten.

Hier sind die Knoten, die wir für dieses Beispiel verwenden werden:

internal abstract class ExpressionNode
{
}

internal abstract class InfixExpressionNode : ExpressionNode
{
    public ExpressionNode Left { get; set; }
    public ExpressionNode Right { get; set; }
}

internal class AdditionNode : InfixExpressionNode
{
}

internal class SubtractionNode : InfixExpressionNode
{
}

internal class MultiplicationNode : InfixExpressionNode
{
}

internal class DivisionNode : InfixExpressionNode
{
}

internal class NegateNode : ExpressionNode
{
    public ExpressionNode InnerNode { get; set; }
}

internal class FunctionNode : ExpressionNode
{
    public Func<double, double> Function { get; set; }
    public ExpressionNode Argument { get; set; }
}

internal class NumberNode : ExpressionNode
{
    public double Value { get; set; }
}

Umwandlung eines CST in einen AST

ANTLR hat die CST-Knoten für uns generiert (die MathParser.*Context Klassen). Diese müssen wir nun in AST-Knoten umwandeln.

Dies ist mit einem Besucher leicht zu bewerkstelligen, und ANTLR stellt uns eine zur Verfügung MathBaseVisitor<T> Klasse, also lasst uns damit arbeiten.

internal class BuildAstVisitor : MathBaseVisitor<ExpressionNode>
{
    public override ExpressionNode VisitCompileUnit(MathParser.CompileUnitContext context)
    {
        return Visit(context.expr());
    }

    public override ExpressionNode VisitNumberExpr(MathParser.NumberExprContext context)
    {
        return new NumberNode
        {
            Value = double.Parse(context.value.Text, NumberStyles.AllowDecimalPoint | NumberStyles.AllowExponent)
        };
    }

    public override ExpressionNode VisitParensExpr(MathParser.ParensExprContext context)
    {
        return Visit(context.expr());
    }

    public override ExpressionNode VisitInfixExpr(MathParser.InfixExprContext context)
    {
        InfixExpressionNode node;

        switch (context.op.Type)
        {
            case MathLexer.OP_ADD:
                node = new AdditionNode();
                break;

            case MathLexer.OP_SUB:
                node = new SubtractionNode();
                break;

            case MathLexer.OP_MUL:
                node = new MultiplicationNode();
                break;

            case MathLexer.OP_DIV:
                node = new DivisionNode();
                break;

            default:
                throw new NotSupportedException();
        }

        node.Left = Visit(context.left);
        node.Right = Visit(context.right);

        return node;
    }

    public override ExpressionNode VisitUnaryExpr(MathParser.UnaryExprContext context)
    {
        switch (context.op.Type)
        {
            case MathLexer.OP_ADD:
                return Visit(context.expr());

            case MathLexer.OP_SUB:
                return new NegateNode
                {
                    InnerNode = Visit(context.expr())
                };

            default:
                throw new NotSupportedException();
        }
    }

    public override ExpressionNode VisitFuncExpr(MathParser.FuncExprContext context)
    {
        var functionName = context.func.Text;

        var func = typeof(Math)
            .GetMethods(BindingFlags.Public | BindingFlags.Static)
            .Where(m => m.ReturnType == typeof(double))
            .Where(m => m.GetParameters().Select(p => p.ParameterType).SequenceEqual(new[] { typeof(double) }))
            .FirstOrDefault(m => m.Name.Equals(functionName, StringComparison.OrdinalIgnoreCase));

        if (func == null)
            throw new NotSupportedException(string.Format("Function {0} is not supported", functionName));

        return new FunctionNode
        {
            Function = (Func<double, double>)func.CreateDelegate(typeof(Func<double, double>)),
            Argument = Visit(context.expr())
        };
    }
}

Wie Sie sehen können, geht es nur darum, mithilfe eines Besuchers aus einem CST-Knoten einen AST-Knoten zu erstellen. Der Code sollte ziemlich selbsterklärend sein (na ja, vielleicht bis auf die VisitFuncExpr Zeug, aber es ist nur eine schnelle Möglichkeit, einen Delegaten mit einer geeigneten Methode des zu verbinden System.Math Klasse).

Und hier haben Sie das AST-Baumaterial. Das ist alles, was benötigt wird. Extrahieren Sie einfach die relevanten Informationen aus dem CST und bewahren Sie sie im AST auf.

Der AST-Besucher

Jetzt spielen wir ein bisschen mit dem AST. Wir müssen eine AST-Besucher-Basisklasse bauen, um sie zu durchqueren. Machen wir einfach etwas Ähnliches wie das AbstractParseTreeVisitor<T> bereitgestellt von ANTLR.

internal abstract class AstVisitor<T>
{
    public abstract T Visit(AdditionNode node);
    public abstract T Visit(SubtractionNode node);
    public abstract T Visit(MultiplicationNode node);
    public abstract T Visit(DivisionNode node);
    public abstract T Visit(NegateNode node);
    public abstract T Visit(FunctionNode node);
    public abstract T Visit(NumberNode node);

    public T Visit(ExpressionNode node)
    {
        return Visit((dynamic)node);
    }
}

Hier habe ich C#’s ausgenutzt dynamic Schlüsselwort, um einen doppelten Versand in einer Codezeile auszuführen. In Java müssen Sie die Verkabelung mit einer Folge von selbst vornehmen if Aussagen wie diese:

if (node is AdditionNode) {
    return Visit((AdditionNode)node);
} else if (node is SubtractionNode) {
    return Visit((SubtractionNode)node);
} else if ...

Aber ich habe mich für dieses Beispiel nur für die Abkürzung entschieden.

Arbeiten Sie mit dem AST

Was können wir also mit einem mathematischen Ausdrucksbaum machen? Natürlich auswerten! Lassen Sie uns einen Ausdrucksauswerter implementieren:

internal class EvaluateExpressionVisitor : AstVisitor<double>
{
    public override double Visit(AdditionNode node)
    {
        return Visit(node.Left) + Visit(node.Right);
    }

    public override double Visit(SubtractionNode node)
    {
        return Visit(node.Left) - Visit(node.Right);
    }

    public override double Visit(MultiplicationNode node)
    {
        return Visit(node.Left) * Visit(node.Right);
    }

    public override double Visit(DivisionNode node)
    {
        return Visit(node.Left) / Visit(node.Right);
    }

    public override double Visit(NegateNode node)
    {
        return -Visit(node.InnerNode);
    }

    public override double Visit(FunctionNode node)
    {
        return node.Function(Visit(node.Argument));
    }

    public override double Visit(NumberNode node)
    {
        return node.Value;
    }
}

Ziemlich einfach, sobald wir einen AST haben, nicht wahr?

Alles zusammenfügen

Zu guter Letzt müssen wir das Hauptprogramm tatsächlich schreiben:

internal class Program
{
    private static void Main()
    {
        while (true)
        {
            Console.Write("> ");
            var exprText = Console.ReadLine();

            if (string.IsNullOrWhiteSpace(exprText))
                break;

            var inputStream = new AntlrInputStream(new StringReader(exprText));
            var lexer = new MathLexer(inputStream);
            var tokenStream = new CommonTokenStream(lexer);
            var parser = new MathParser(tokenStream);

            try
            {
                var cst = parser.compileUnit();
                var ast = new BuildAstVisitor().VisitCompileUnit(cst);
                var value = new EvaluateExpressionVisitor().Visit(ast);

                Console.WriteLine("= {0}", value);
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }

            Console.WriteLine();
        }
    }
}

Und jetzt können wir endlich damit spielen:

Ich habe ein kleines Java-Projekt erstellt, mit dem Sie Ihre ANTLR-Grammatik sofort testen können, indem Sie den von ANTLR im Speicher generierten Lexer und Parser kompilieren. Sie können einen String einfach parsen, indem Sie ihn an den Parser übergeben, und er generiert daraus automatisch einen AST, der dann in Ihrer Anwendung verwendet werden kann.

Um die Größe des AST zu reduzieren, könnten Sie einen NodeFilter verwenden, dem Sie die Produktionsregelnamen der Nicht-Terminals hinzufügen könnten, die Sie beim Erstellen des AST berücksichtigen möchten.

Den Code und einige Codebeispiele finden Sie unter
https://github.com/julianthome/inmemantlr

Hoffe das Tool ist nützlich 😉

Ich habe zwei einfache Möglichkeiten gefunden, die sich auf die in der verfügbaren Funktionen konzentrieren TestRig.java Datei von antlr4.

1. Über Klemme

Dies ist mein Beispiel für das Parsen von C++ mit der entsprechenden CPP14.g4-Grammatikdatei
java -cp .:antlr-4.9-complete.jar org.antlr.v4.gui.TestRig CPP14 translationunit -tree filename.cpp. Wenn Sie filename.cpp weglassen, liest das Rig von stdin. “translationunit” ist der Startregelname der CPP14.g4 Grammatikdatei, die ich verwende.

2. Über Java

Ich habe Teile des Codes aus der Datei TestRig.java verwendet. Nehmen wir noch einmal an, wir haben eine Reihe von C++-Quellcodes, aus denen wir den AST erzeugen wollen (Sie können auch direkt aus einer Datei lesen).

String source_code = "...your cpp source code...";

CodePointCharStream stream_from_string = CharStreams.fromString(source_code);
CPP14Lexer lexer = new CPP14Lexer(new ANTLRInputStream(source_code));
CommonTokenStream tokens = new CommonTokenStream(lexer);
CPP14Parser parser = new CPP14Parser(tokens);

String parserName = "CPP14Parser";
ClassLoader cl = Thread.currentThread().getContextClassLoader();
Class<? extends Parser> parserClass = null;
parserClass = cl.loadClass(parserName).asSubclass(Parser.class);

String startRuleName = "translationunit"; //as specified in my CPP14.g4 file
Method startRule = parserClass.getMethod(startRuleName);
ParserRuleContext tree = (ParserRuleContext)startRule.invoke(parser, (Object[])null);
System.out.println(tree.toStringTree(parser));

Meine Importe sind:

import java.lang.reflect.Method;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CodePointCharStream;
import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.ParserRuleContext;
import org.antlr.v4.runtime.Parser;

All dies setzt voraus, dass Sie die erforderlichen Dateien (Lexer, Parser usw.) mit dem Befehl erstellt haben java -jar yournaltrfile.jar yourgrammar.g4 und dass Sie dann alle *.java-Dateien kompiliert haben.