java - ¿Cómo crear AST con ANTLR4?

compiler-construction abstract-syntax-tree

Question

He estado buscando MUCHO sobre esto y no pude encontrar nada útil que REALMENTE me ayude a construir un AST. Ya sé que ANTLR4 no construye AST como solía hacer ANTLR3. Todos dicen: "¡Hey, usa visitantes!", Pero no pude encontrar ningún ejemplo o explicación más detallada sobre CÓMO puedo hacer esto ...

Tengo una gramática que me gusta C, pero con todos los comandos escritos en portugués (lenguaje de programación portuga). Puedo generar fácilmente el árbol de análisis usando ANTLR4. Mi pregunta es: ¿Qué necesito hacer ahora para crear un AST?

Por cierto, estoy usando Java e IntelliJ ...

EDITAR1: Lo más cerca que pude llegar fue usar la respuesta de este tema: ¿Hay un ejemplo simple de usar antlr4 para crear un AST a partir del código fuente de Java y extraer métodos, variables y comentarios? Pero solo imprime el nombre de los métodos visitados.

Como el primer intento no funcionó para mí como esperaba, traté de usar este tutorial de ANTLR3, pero no pude descubrir cómo usar StringTamplate en lugar de ST ...

Leyendo el libro La referencia definitiva de ANTLR 4 Tampoco pude encontrar nada relacionado con AST.

EDIT2: ahora tengo una clase para crear el archivo DOT, solo necesito descubrir cómo usar los visitantes correctamente

Answer 1

He creado un pequeño proyecto Java que le permite probar su gramática ANTLR al instante compilando el lexer y el analizador generados por ANTLR en la memoria. Simplemente puede analizar una cadena pasándola al analizador, y generará automáticamente un AST a partir de ella que luego se puede utilizar en su aplicación.

Con el fin de reducir el tamaño del AST, puede usar un NodeFilter al que puede agregar los nombres de las reglas de producción de los no terminales que le gustaría tener en cuenta al construir el AST.

El código y algunos ejemplos de código se pueden encontrar en https://github.com/julianthome/inmemantlr

Espero que la herramienta sea útil ;-)

Answer 2

Ok, construyamos un ejemplo matemático simple. Construir un AST es totalmente exagerado para tal tarea, pero es una buena manera de mostrar el principio.

Lo haré en C # pero la versión de Java sería muy similar.

La gramática

Primero, escribamos una gramática matemática muy básica para trabajar con:

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

Bastante básico, tenemos una sola regla expr que maneja todo (reglas de precedencia, etc.).

Los nodos AST

Luego, definamos algunos nodos AST que usaremos. Estos son totalmente personalizados y puede definirlos de la manera que desee.

Aquí están los nodos que usaremos para este ejemplo:

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

Convertir un CST en un AST

ANTLR generó los nodos CST para nosotros ( MathParser.*Context Clases de MathParser.*Context ). Ahora tenemos que convertirlos a nodos AST.

Esto se hace fácilmente con un visitante, y ANTLR nos proporciona una MathBaseVisitor<T> , así que MathBaseVisitor<T> con eso.

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

Como puede ver, solo se trata de crear un nodo AST a partir de un nodo CST utilizando un visitante. El código debería explicarse bastante bien (bueno, tal vez a excepción de las cosas de VisitFuncExpr , pero es solo una forma rápida de conectar un delegado a un método adecuado de la clase System.Math ).

Y aquí tienes las cosas de construcción de AST. Eso es todo lo que se necesita. Simplemente extraiga la información relevante del CST y manténgala en el AST.

El visitante AST

Ahora, juguemos un poco con el AST. Tendremos que construir una clase base de visitante AST para atravesarla. Hagamos algo similar al AbstractParseTreeVisitor<T> proporcionado por 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);
    }
}

Aquí, aproveché dynamic palabra clave dynamic de C # para realizar un envío doble en una línea de código. En Java, tendrá que hacer el cableado usted mismo con una secuencia de sentencias if como estas:

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

Pero solo fui por el atajo para este ejemplo.

Trabaja con la AST

Entonces, ¿qué podemos hacer con un árbol de expresión matemática? Evaluarlo, por supuesto! Implementemos un evaluador de expresiones:

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

Bastante simple una vez que tenemos un AST, ¿no?

Poniendolo todo junto

Por último, pero no menos importante, tenemos que escribir el programa principal:

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

Y ahora finalmente podemos jugar con él: