如何用ANTLR4创buildAST？

我一直在寻找一个关于这一点，我找不到有用的东西，真的帮助我build立一个AST。 我已经知道ANTLR4并不像ANTLR3那样build立AST。 每个人都说：“嗨，使用游客！”，但我怎么能做到这一点，我找不到任何例子或更详细的解释…

我有一个语法必须像C，但用葡萄牙语（葡萄牙语编程语言）写的每个命令。 我可以使用ANTLR4轻松生成分析树。 我的问题是：我现在需要做什么来创build一个AST？

顺便说一句，我正在使用Java和IntelliJ …

编辑1：我能得到的最接近的是使用这个话题的答案： 是否有一个简单的例子，使用antlr4从java源代码创build一个AST并提取方法，variables和注释？ 但它只打印访问方法的名称..

由于第一次尝试不适合我，因为我期望，我试图从ANTLR3使用本教程 ，但我不知道如何使用StringTamplate，而不是ST …

阅读这本书The Definitive ANTLR 4 Reference我也找不到任何与AST有关的东西。

编辑2：现在我有一个类来创buildDOT文件，我只需要弄清楚如何正确使用访问者

Answer 1

好吧，我们来构build一个简单的math示例。 构build一个AST对于这样一个任务来说是完全过分的，但这是展示原理的一个好方法。

我会用C＃来做，但Java版本会非常相似。

语法

首先，我们来写一个非常基本的math语法来处理：

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

相当基本的东西，我们有一个处理一切（优先规则等）的单个expr规则。

AST节点

然后，我们来定义一些我们将要使用的AST节点。 这些都是完全自定义的，你可以用你想要的方式来定义它们。

这里是我们将用于这个例子的节点：

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

将CST转换为AST

ANTLR为我们生成了CST节点（ MathParser.*Context类）。 我们现在必须将这些转换为AST节点。

访问者很容易做到这一点，ANTLR为我们提供了一个MathBaseVisitor<T>类，所以让我们来处理这个问题。

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

正如您所看到的，这只是使用访问者从CST节点创buildAST节点的问题。 该代码应该是非常明显的（也许，除了VisitFuncExpr东西，但它只是一个快捷的方法来连接委托给System.Math类的适当的方法）。

在这里你有ASTbuild筑的东西。 这就是所需要的。 只需从CST提取相关信息并保存在AST中即可。

AST访客

现在，让我们玩一下AST。 我们将不得不构build一个AST访问者基类来遍历它。 我们来做一些类似于ANTLR提供的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); } } 

在这里，我利用C＃的dynamic关键字在一行代码中执行双重调度。 在Java中，你必须用下面这样的一系列if语句来连接你自己：

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

但我只是为了这个例子的快捷方式。

与AST一起工作

那么，我们可以用mathexpression式树做什么？ 评估它，当然！ 我们来实现一个expression式评估器：

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

一旦我们有AST，很简单，不是吗？

把它放在一起

最后但并非最不重要的是，我们必须实际编写主程序：

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

现在我们终于可以玩了：

Answer 2

我创build了一个小型的Java项目，允许您通过编译由ANTLR在内存中生成的词法分析器和分析器来立即testing您的ANTLR语法。 你可以通过传递给parsing器来parsing一个string，它会自动生成一个AST，然后在你的应用程序中使用它。

为了减小AST的大小，你可以使用一个NodeFilter，你可以在这个NodeFilter上添加非terminal的生产规则名称，在构buildAST时你会考虑这个名称。

代码和一些代码示例可以在https://github.com/julianthome/inmemantlrfind

希望这个工具很有用;-)