Java如何使用ANTLR4创建AST？

让我们建立一个简单的数学示例。对于这样的任务，构建AST完全是矫kill过正，但这是展示原理的好方法。

我将使用C＃进行操作，但Java版本将非常相似。

语法
首先，让我们写一个非常基本的数学语法来使用：

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  :   [ trn] -> 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为我们（

MathParser.*Context类

访问者很容易做到这一点，而ANTLR为我们提供了一个MathbaseVisitor类，因此让我们开始吧。

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节点中创建AST节点的问题。代码应该很容易解释（嗯，也许除了VisitFuncExpr东西之外，但这只是将委托连接到类的合适方法的一种快速方法System.Math）。

在这里，你将拥有AST建筑材料。这就是所需要的。只需从CST中提取相关信息，然后将其保存在AST中即可。

AST访客
现在，让我们玩一下AST。我们必须建立一个AST访问者基类来遍历它。让我们做一些与AbstractParseTreeVisitorANTLR提供的类似的事情。

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合作
那么，我们可以用数学表达式树做什么？评估一下，当然！让我们实现一个表达式评估器：

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