wake-up-neo.com

Wie erstelle ich AST mit ANTLR4?

Ich habe viel darüber gesucht und konnte nichts Nützliches finden, das mir WIRKLICH beim Aufbau eines AST hilft. Ich weiß bereits, dass ANTLR4 AST nicht wie früher ANTLR3 erstellt. Jeder sagt: "Hey, benutze Besucher!", Aber ich konnte kein Beispiel oder eine detailliertere Erklärung dafür finden, wie ich das machen kann ...

Ich habe eine Grammatik, die wie C sein muss, aber mit allen Befehlen, die in Portugiesisch (portugiesische Programmiersprache) geschrieben sind. Ich kann den Analysebaum mit ANTLR4 leicht erzeugen. Meine Frage ist: Was muss ich jetzt tun, um einen AST zu erstellen?

Übrigens verwende ich Java und IntelliJ ...

EDIT1: Am ehesten konnte ich die Antwort zu diesem Thema verwenden: Gibt es ein einfaches Beispiel für die Verwendung von antlr4 zum Erstellen eines AST aus Java Quellcode und Extraktmethoden, Variablen und Kommentare? Es wird jedoch nur der Name der aufgerufenen Methoden ausgegeben.

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 man StringTamplate anstelle von ST verwendet ...

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

EDIT2: Jetzt habe ich eine Klasse, um die DOT-Datei zu erstellen. Ich muss nur herausfinden, wie man Besucher richtig benutzt

53
Leandro

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 demonstrieren.

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

Die Grammatik

Lassen Sie uns zunächst eine sehr einfache 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 einzige expr -Regel, die alles behandelt (Vorrangregeln usw.).

Die AST Knoten

Definieren wir dann einige AST Knoten, die wir verwenden werden. Diese sind völlig benutzerdefiniert und können nach Belieben 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; }
}

Umwandlung einer CST in eine AST

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

Dies ist mit einem Besucher leicht möglich, und ANTLR stellt uns eine Klasse MathBaseVisitor<T> Zur Verfügung. 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, 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 von VisitFuncExpr, aber es ist nur eine schnelle Möglichkeit, einen Delegaten mit einer geeigneten Methode des System.Math Klasse).

Und hier haben Sie die AST Bausteine. Das ist alles was benötigt wird. Extrahieren Sie einfach die relevanten Informationen aus dem CST und speichern Sie sie im AST.

Der AST Besucher

Lass uns jetzt ein bisschen mit dem AST spielen. Wir müssen eine AST -Besucher-Basisklasse erstellen, um sie zu durchlaufen. Machen wir einfach etwas Ähnliches wie das von ANTLR bereitgestellte AbstractParseTreeVisitor<T>.

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 nutzte ich das Schlüsselwort dynamic von C #, um einen Doppelversand in einer Codezeile durchzuführen. In Java müssen Sie die Verkabelung mit einer Folge von if -Anweisungen wie den folgenden selbst durchführen:

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

Aber ich habe gerade die Abkürzung für dieses Beispiel gewählt.

Arbeite 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 zusammen

Zu guter Letzt müssen wir das Hauptprogramm 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:

enter image description here

132

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 analysieren, indem Sie ihn an den Parser übergeben , und es wird automatisch ein AST daraus generiert, das dann in Ihrer Anwendung verwendet werden kann.

Zum Verringern der Größe des AST 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 ;-)

4
Julian