Wie erstelle ich AST mit ANTLR4?

70

Ich habe VIEL darüber gesucht und konnte nichts Nützliches finden, das mir WIRKLICH hilft, einen AST aufzubauen. Ich weiß bereits, dass ANTLR4 AST nicht mehr so ​​erstellt wie früher ANTLR3. Alle sagen: "Hey, benutze Besucher!", Aber ich konnte kein Beispiel oder eine detailliertere Erklärung finden, wie ich das machen kann ...

Ich habe eine Grammatik muss C mögen, aber mit allen Befehlen in Portugiesisch (portuga Programmiersprache) geschrieben. Ich kann den Analysebaum einfach mit ANTLR4 generieren. Meine Frage ist: Was muss ich jetzt tun, um einen AST zu erstellen?

Übrigens benutze ich 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, um einen AST aus Java-Quellcode zu erstellen und Methoden, Variablen und Kommentare zu extrahieren? Es wird jedoch nur der Name der besuchten Methoden gedruckt.

Da der erste Versuch bei mir nicht wie erwartet funktioniert hat, habe ich versucht, dieses Tutorial von ANTLR3 zu verwenden, aber ich konnte nicht herausfinden, wie StringTamplate anstelle von ST verwendet wird ...

Lesen des Buches The Definitive ANTLR 4 Reference Ich konnte auch nichts im Zusammenhang mit ASTs finden.

EDIT2: Jetzt habe ich eine Klasse zum Erstellen der DOT-Datei. Ich muss nur noch herausfinden, wie Besucher richtig verwendet werden

Leandro
quelle
2
Könnten Sie etwas von dem teilen, was Sie versucht haben?
Sandy Gifford
@SandyGifford Ich habe meinen Beitrag bearbeitet, um zu erklären ... Ich habe meinen Code momentan nicht, weil ich gerade gelöscht habe, was ich gemacht habe. Im Moment habe ich nur die generierten Codes von ATNLR4 (Parser, Lexer und Basisbesucher und Listener)
Leandro
Leider weiß ich nichts über ANTLR (Sie sind in meiner Warteschlange aufgetaucht), aber Sie haben die Qualität des Beitrags erhöht!
Sandy Gifford
In dieser Antwort finden Sie eine Diskussion zwischen "CST" und "AST": stackoverflow.com/a/29456792/120163 Der Kommentar am Ende beschreibt, wie ein anderer tatsächlich einen AST erhält (im Wesentlichen durch Gehen des CST und Herstellen des gewünschten AST).
Ira Baxter
Ich war in einer ähnlichen Situation wie Sie, nachdem ich mit ANTLR kein supereinfaches AST-Beispiel gefunden habe, habe ich selbst eines erstellt. Github.com/adamsiemion/antlr-java-ast
Adam Siemion

Antworten:

168

Ok, lassen Sie uns ein einfaches mathematisches Beispiel erstellen. Das Erstellen eines AST ist für eine solche Aufgabe völlig übertrieben, aber es ist eine gute Möglichkeit, das Prinzip zu zeigen.

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

Die Grammatik

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

grammar Math;

compileUnit
    :   expr EOF
    ;

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

OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';

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

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

Die AST-Knoten

Definieren wir dann einige AST-Knoten, die wir verwenden werden. Diese sind vollständig benutzerdefiniert und können nach Ihren Wünschen definiert werden.

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; }
}

Konvertieren eines CST in einen AST

ANTLR hat die CST-Knoten für uns generiert (die MathParser.*Context Klassen) . Wir müssen diese nun in AST-Knoten konvertieren.

Dies ist mit einem Besucher leicht möglich, und ANTLR bietet uns eine MathBaseVisitor<T>Klasse an. Lassen Sie uns also 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, müssen Sie lediglich einen AST-Knoten aus einem CST-Knoten mithilfe eines Besuchers erstellen. Der Code sollte ziemlich selbsterklärend sein (naja, vielleicht mit Ausnahme des VisitFuncExprMaterials, aber es ist nur eine schnelle Möglichkeit, einen Delegierten mit einer geeigneten Methode der System.MathKlasse zu verbinden).

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

Lassen Sie uns jetzt ein bisschen mit dem AST spielen. Wir müssen eine AST-Besucherbasisklasse erstellen, um sie zu durchlaufen. Lassen Sie uns einfach etwas Ähnliches wie das AbstractParseTreeVisitor<T>von ANTLR bereitgestellte tun .

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 das dynamicSchlüsselwort von C # genutzt, um einen Doppelversand in einer Codezeile durchzuführen. In Java müssen Sie die Verkabelung selbst mit einer Folge von ifAnweisungen wie diesen durchführen:

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

Aber ich habe mich gerade für die Verknüpfung für dieses Beispiel entschieden.

Arbeiten Sie mit dem AST

Was können wir also mit einem mathematischen Ausdrucksbaum tun? Bewerten Sie es natürlich! Implementieren wir einen Ausdrucksauswerter:

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, wenn 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:

Geben Sie hier die Bildbeschreibung ein

Lucas Trzesniewski
quelle
2
@Waschbaer IMO Die manuelle Feinabstimmung der Knoten verbessert die Wartbarkeit und ist es wert, aber Sie können anderer Meinung sein. ANTLR 3 hatte einen AST-Ausgabemodus, sodass Sie diesen verwenden können, wenn Sie mit der Verwendung eines veralteten Tools vertraut sind. Oder vielleicht könnten Sie Metaprogrammierung / Template verwenden, um etwas Boilerplate-Code zu generieren, aber am Ende könnten Sie am Ende mehr Arbeit haben. Eine andere Möglichkeit besteht darin, direkt mit dem CST zu arbeiten.
Lucas Trzesniewski
2
In vielen Jahren des Lesens von SO für Tipps, Vorschläge und Antworten ist dies eine der besten Antworten, die ich je gesehen habe. Hervorragende Präsentation der Konzepte.
1
Wie haben Sie die MathBaseVisitor-Klasse erhalten? Meine Grammatik heißt QueryParser und ich habe keine QueryParserBaseVisitor-Klasse. Ich habe einen QuertyParserBaseListener, aber es ist eher ein In-Out-Walker, mit dem man praktisch nicht arbeiten kann. (Ich habe es versucht)
Trejkaz
1
@Trejkaz Diese Klasse wird von ANTLR generiert, genau wie der Listener - Sie sollten eine haben QueryBaseVisitor(es sei denn, Ihr Grammatikname enthält diesen ParserTeil, aber in diesem Fall haben Sie auch eine QueryParserParser). IIRC Das NuGet-Paket generiert es automatisch. Wenn Sie ANTLR jedoch manuell ausführen, müssen Sie die -visitorOption hinzufügen .
Lucas Trzesniewski
2
@Johannes Ich habe die Lösung gefunden, ich habe sie hier roh mit allen generierten Ausgaben und Abhängigkeiten hochgeladen . Es sollte nicht hübsch aussehen, fast alles befindet sich in derselben Datei. Die beiden VisitMethoden haben nichts miteinander zu tun, sie haben zufällig den gleichen Namen, aber da beide Klassen Besucher sind, verwenden sie den gleichen Namen :)
Lucas Trzesniewski
9

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 eine Zeichenfolge einfach analysieren, indem Sie sie an den Parser übergeben. Daraus wird automatisch ein AST generiert, der dann in Ihrer Anwendung verwendet werden kann.

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

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

Hoffe das Tool ist nützlich ;-)

julianisch
quelle
Ich habe versucht, Ihr "kleines" Projekt zu verwenden, aber Sie haben Hunderte von Dateien ohne Kommentare. Es ist unmöglich herauszufinden, was los ist. Sie haben alles in Ihrer eigenen Version der Wrapper-Funktionen verpackt. Ein Benutzer müsste Ihr gesamtes Projekt herunterladen und unverändert verwenden und lernen, Ihre neuen Klassen (GenericParser ??) zu verwenden. Ich kann Ihren Code nicht verwenden, um herauszufinden, wie ich meinen eigenen AST in meinem eigenen Code erstellen kann.
John Ktejik
2
Hallo John inmemantlrs Codebasis besteht aus 48 JavaClasses ( find inmemantlr-api/src/main -name "*.java" | nl), von denen die meisten ziemlich gut kommentiert sind ( javadoc.io/doc/com.github.julianthome/inmemantlr-api/1.3.9 ). Um die oben genannten Punkte zu veranschaulichen (API-Verwendung, ParseTree-Erstellung), habe ich Erklärungen in den README.mdTestfällen bereitgestellt und Testfälle unter github.com/julianthome/inmemantlr/tree/master/inmemantlr-api/… bereitgestellt . Falls Sie jedoch Probleme mit dem Tool haben, helfen wir Ihnen gerne weiter. Bitte schreiben Sie mir einfach eine E-Mail oder erstellen Sie ein Problem auf Github.
Julian
1
Könnte es sein, dass Sie das Submodul Grammatik-v4 gezogen haben (bitte schauen Sie es sich an inmemantlr-api/src/test/resources/grammars-v4)? Tatsächlich ist dieses Modul nicht Teil der Codebasis von inmemantlr. Es wird verwendet, um sicherzustellen, dass inmemantlr auf allen Grammatiken-v4-Grammatiken funktioniert. Das Submodul wird jedoch bei der Ausführung nicht standardmäßig abgerufen git clone https://github.com/julianthome/inmemantlr.
Julian
1
@ Julian erstaunliche Werkzeuge. Es ist wirklich leistungsstark und einfach zu bedienen. Vielen Dank, dass Sie es mit der Community geteilt haben. Ich würde gerne mehr Beispiele im Wiki sehen.
Vaibhav Jain
@ VaibhavJain vielen Dank. Wenn Sie Vorschläge zur Verbesserung der Dokumentation / des Tools / der API haben, würde ich mich freuen, wenn Sie ein Problem auf der Github-Projektseite erstellen könnten;). Danke noch einmal.
Julian
1

Ich habe zwei einfache Möglichkeiten gefunden, das sich auf die Funktionalität in der TestRig.java Datei von antlr4.

  1. Über Terminal

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 die Datei filename.cpp weglassen, liest das Rig von stdin. "translationunit" ist der Name der Startregel der von mir verwendeten Grammatikdatei CPP14.g4 .

  1. Über Java

Ich habe Teile des Codes verwendet, die in der Datei TestRig.java enthalten sind. Nehmen wir noch einmal an, wir haben eine Zeichenfolge aus C ++ - Quellcode, aus der wir den AST erzeugen möchten (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 java -jar yournaltrfile.jar yourgrammar.g4und anschließend alle * .java-Dateien kompiliert haben.

Konstantina Dritsa
quelle