Cómo crear AST con ANTLR4?

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: “¡Oigan, visiten!”, Pero no pude encontrar ningún ejemplo o explicación más detallada sobre CÓMO puedo hacer esto …

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

Por cierto, estoy usando Java e IntelliJ …

EDIT1: Lo más cerca que pude estar 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 bash no funcionó para mí como esperaba, traté de usar este tutorial de ANTLR3, pero no pude encontrar la manera de usar StringTamplate en lugar de ST …

Leyendo el libro The Definitive ANTLR 4 Reference También no pude encontrar nada relacionado con los AST.

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

Ok, construyamos un ejemplo matemático simple. Crear 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, vamos a escribir 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 Function { get; set; } public ExpressionNode Argument { get; set; } } internal class NumberNode : ExpressionNode { public double Value { get; set; } } 

Convirtiendo un CST a un AST

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

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

 internal class BuildAstVisitor : MathBaseVisitor { 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)func.CreateDelegate(typeof(Func)), 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 ser bastante autoexplicativo (bueno, tal vez excepto para el material de VisitFuncExpr , pero es solo una manera 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 guárdela en el AST.

El visitante de AST

Ahora, juguemos un poco con AST. Tendremos que construir una clase base de visitantes de AST para atravesarla. Hagamos algo similar a AbstractParseTreeVisitor proporcionado por ANTLR.

 internal abstract class AstVisitor { 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 doble despacho 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 AST

Entonces, ¿qué podemos hacer con un árbol de expresiones matemáticas? Evaluar, por supuesto! Implementemos un evaluador de expresiones:

 internal class EvaluateExpressionVisitor : AstVisitor { 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 es así?

Poniendolo todo junto

Por último, pero no menos importante, tenemos que escribir el progtwig 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 eso:

enter image description here

He creado un pequeño proyecto de Java que le permite probar su gramática ANTLR de forma instantánea comstackndo el lexer y el analizador generados por ANTLR en la memoria. Puede analizar una cadena pasándola al analizador y automáticamente generará un AST que luego podrá usar en su aplicación.

Con el fin de reducir el tamaño del AST, podría usar un NodeFilter al que podría agregar los nombres de regla de producción de los no terminales que le gustaría considerar 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 😉

    Intereting Posts