如何使用ANTLR4创建AST？

Question

我已经搜索了很多关于如何构建AST的内容，但是没找到真正有用的东西。我已经知道ANTLR4不像ANTLR3那样构建AST。每个人都说：“嘿，使用访问者(visitor)！” 但我找不到任何关于如何做到这一点的例子或更详细的解释...

我的语法类似于C，但所有命令都是用葡萄牙语（portuga编程语言）编写的。我可以很容易地使用ANTLR4生成解析树(parse tree)。我的问题是：现在我需要做什么来创建AST呢？

顺便说一下，我正在使用Java和IntelliJ...

EDIT1： 我最接近的是使用这个主题的回答：Is there a simple example of using antlr4 to create an AST from java source code and extract methods, variables and comments? 但它只打印访问的方法名称..

由于第一次尝试并没有像我预期的那样工作，所以我尝试使用ANTLR3中的这个教程，但我无法弄清楚如何使用StringTemplate而不是ST...

在阅读《ANTLR 4权威指南》时，我也没有找到任何关于AST的相关内容。

EDIT2：现在我有一个类来创建DOT文件，我只需要确定如何正确使用访问者(visitor)

- Leandro

---

你能分享一下你尝试过的东西吗？ - Sandy Gifford

@SandyGifford 我编辑了我的帖子，试图解释...我现在没有我的代码，因为我刚刚删除了我所做的。现在我只有从ATNLR4生成的代码（解析器、词法分析器和基本访问者和监听器）。 - Leandro

很遗憾，我对ANTLR一无所知（你出现在我的队列中），但你提高了这篇文章的质量！ - Sandy Gifford

请参考此答案讨论“CST”与“AST”的区别：http://stackoverflow.com/a/29456792/120163。结尾的评论讨论了另一种如何获取AST的方法（基本上是通过遍历CST并制造所需的AST）。 - Ira Baxter

我曾经和你一样处于类似的情况，当我无法找到使用ANTLR创建超级简单AST示例时，我自己创造了一个。https://github.com/adamsiemion/antlr-java-ast - Adam Siemion

@AdamSiemion，你的示例出现错误，无法找到Java8Lexer类。 - john k

Answer 1

好的，让我们构建一个简单的数学示例。对于这样的任务来说，构建AST是完全不必要的，但它是展示原理的好方法。

我将使用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  :   [ \t\r\n] -> channel(HIDDEN);

这是一些基础内容，我们有一个单一的expr规则来处理所有内容（包括优先级规则等）。

抽象语法树节点

接下来，让我们定义一些我们将使用的抽象语法树节点。这些完全是自定义的，您可以按照您想要的方式定义它们。

这是我们将在本例中使用的节点：

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节点转换为AST节点即可。代码应该很容易理解（除了VisitFuncExpr部分可能有些难懂，但它只是一种将委托与System.Math类的适当方法连接起来的快速方式）。

这里是构建AST的内容。这就是所需的全部内容。只需从CST中提取相关信息并将其保存在AST中即可。

AST访问器

现在，让我们稍微玩一下AST。我们需要构建一个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

那么，我们可以用数学表达式树做什么呢？当然是求值！让我们实现一个表达式求值器：

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

现在我们终于可以玩它了：

- Lucas Trzesniewski

---

在我看来，手动微调节点会提高代码的可维护性并且是值得的，但你可能不同意。ANTLR 3有一个AST输出模式，如果你能使用这个过时的工具，你也可以使用它。或者你可以使用元编程/模板生成一些样板代码，但最终可能需要更多的工作量。另外一个选择是直接使用CST进行操作。 - Lucas Trzesniewski

在阅读 Stack Overflow（SO）以获取技巧、建议和答案的多年中，这是我见过的最好的答案之一。对概念的阐述非常出色。 - user7564947

你是怎么得到MathBaseVisitor类的？我的语法叫做QueryParser，我没有一个QueryParserBaseVisitor类。我有一个QuertyParserBaseListener，但它更像是一个进出遍历器，实际上很难使用。（我试过了） - Hakanai

@Trejkaz 这个类是由ANTLR生成的，就像listener一样-你应该有一个QueryBaseVisitor（除非你的语法名称包括那个Parser部分，但在这种情况下你也会有一个QueryParserParser）。如果我没记错的话，NuGet包会自动生成它，但如果你手动运行ANTLR，你必须添加-visitor选项。 - Lucas Trzesniewski

@Johannes 我找到了解决方案，我上传了它这里，包括所有生成的输出和依赖项。它并不是为了好看，几乎所有内容都在同一个文件中。两个Visit方法没有关联，它们碰巧有相同的名称，但由于两个类都是访问者，所以它们使用相同的名称 :) - Lucas Trzesniewski

Answer 2

我创建了一个小的Java项目，允许你通过在内存中编译由ANTLR生成的词法分析器和语法分析器来立即测试你的ANTLR语法。你只需将一个字符串传递给解析器进行解析，它会自动生成一个AST，然后可以在你的应用程序中使用。

为了减小AST的大小，你可以使用NodeFilter，并添加非终端符号的产生式名称，以便在构建AST时将其纳入考虑。

代码和一些示例可以在https://github.com/julianthome/inmemantlr找到。

希望这个工具对您有用；-）

- Julian

---

我尝试使用你的“小”项目，但是你有数百个没有注释的文件，很难弄清楚发生了什么。你把所有东西都包装在自己版本的包装函数中。用户必须下载整个项目并按原样使用它，并学习使用你的新类（GenericParser？？）。我无法使用你的代码来找出如何在我的代码中创建自己的AST。 - john k

嗨 John，inmemantlr的代码库由48个Java类组成（find inmemantlr-api/src/main -name "*.java" | nl），其中大部分都被很好地注释了（http://www.javadoc.io/doc/com.github.julianthome/inmemantlr-api/1.3.9）。为了说明你上面提到的点（API使用、ParseTree创建），我已经在`README.md`中提供了解释，并在https://github.com/julianthome/inmemantlr/tree/master/inmemantlr-api/src/test/java中提供了测试用例。但是，如果你在使用这个工具时有任何问题，我很乐意帮助你。请发封电子邮件或在github上创建一个问题。 - Julian

你可能已经拉取了 grammars-v4 子模块（请查看 inmemantlr-api/src/test/resources/grammars-v4）。实际上，这个模块并不是 inmemantlr 代码库的一部分；它用于确保 inmemantlr 可以在所有 grammars-v4 语法上运行。然而，默认情况下，在执行 git clone https://github.com/julianthome/inmemantlr 命令时，并没有拉取这个子模块。 - Julian

@Julian 的工具很棒。它真的非常强大且易于使用。非常感谢您与社区分享。希望在维基中看到更多示例。 - Vaibhav Jain

@VaibhavJain非常感谢你。如果你对如何改进文档/工具/API有一些建议，我会很高兴如果你可以在GitHub项目页面上创建一个问题。再次感谢。 - Julian

Answer 3

我找到了两种简单的方法，专注于antlr4的TestRig.java文件中提供的功能。

1. 通过终端

这是我的一个例子，使用相应的CPP14.g4语法文件解析C++：java -cp .:antlr-4.9-complete.jar org.antlr.v4.gui.TestRig CPP14 translationunit -tree filename.cpp。如果省略filename.cpp，rig将从stdin读取。 "translationunit"是我使用的CPP14.g4语法文件的起始规则名称。

2. 通过Java

我使用了TestRig.java文件中找到的代码部分。假设我们再次有一个C++源代码字符串，我们想从中生成AST（也可以直接从文件中读取）。

String source_code = "...your cpp source code...";

CodePointCharStream stream_from_string = CharStreams.fromString(source_code);
CPP14Lexer lexer = new CPP14Lexer(new ANTLRInputStream(source_code));
CommonTokenStream tokens = new CommonTokenStream(lexer);
CPP14Parser parser = new CPP14Parser(tokens);

String parserName = "CPP14Parser";
ClassLoader cl = Thread.currentThread().getContextClassLoader();
Class<? extends Parser> parserClass = null;
parserClass = cl.loadClass(parserName).asSubclass(Parser.class);

String startRuleName = "translationunit"; //as specified in my CPP14.g4 file
Method startRule = parserClass.getMethod(startRuleName);
ParserRuleContext tree = (ParserRuleContext)startRule.invoke(parser, (Object[])null);
System.out.println(tree.toStringTree(parser));

我的导入包括：

import java.lang.reflect.Method;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CodePointCharStream;
import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.ParserRuleContext;
import org.antlr.v4.runtime.Parser;

所有这些都需要你使用命令 java -jar yournaltrfile.jar yourgrammar.g4 生成必要的文件（如词法分析器、语法分析器等），然后编译所有的 *.java 文件。

- Konstantina Dritsa

---

为什么在编译时已有类/方法可用，还要使用反射？ - Thomas S.

你的导入中没有包含CPP14Parser或CPP14Lexer。我们是应该自己实现它还是你忘记了？ - citizenfour

Answer 4

我已经将Terrence Parr的书《语言实现模式》中关于“树语法”模式的代码（源代码位于tpdsl-code/walking/tree-grammar下）从antlr 3转换为antlr 4，使用了Visitor和“同质AST”模式。

以下是语法：

VecMath.g4

// START: header
grammar VecMath;
tokens { VEC }       // define imaginary token for vector literal
// END: header

// START: stat
prog:   stat+ ;              // build list of stat trees
stat:   ID assign='=' expr  #StatAssign // '=' is operator subtree root
    |   print='print' expr  #StatPrint  // 'print' is subtree root
    ;
// END: stat

// START: expr
expr: left=expr op=('*'|'.') right=expr #ExprMult // '*', '.' are roots
    | left=expr op='+' right=expr       #ExprAdd  // '+' is root node
    | '[' expr (',' expr)* ']'    #ExprVec  // VEC is root
    | INT                               #ExprInt
    | ID                                #ExprId
    ;
// END: expr

ID  :   'a'..'z'+ ;
INT :   '0'..'9'+ ;
WS  :   (' '|'\r'|'\n')+ -> skip ;

访问者

package walking.v4.vecmath_ast.impl;

import org.antlr.v4.runtime.CommonToken;

import walking.v4.vecmath_ast.antlr.VecMathBaseVisitor;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprAddContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprIdContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprIntContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprMultContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ExprVecContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.ProgContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.StatAssignContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.StatContext;
import walking.v4.vecmath_ast.antlr.VecMathParser.StatPrintContext;
import walking.v4.vecmath_ast.antlr.VecMathParser;


public class VecMathBuildASTVisitor extends VecMathBaseVisitor<AST> {
    @Override
    public AST visitProg(ProgContext ctx) {
        AST ast = new AST();
        for (StatContext stmt : ctx.stat()) {
            ast.addChild(visit(stmt));
        }
        return ast;
    }

    @Override
    public AST visitStatAssign(StatAssignContext ctx) {
        AST ast = new AST(ctx.assign);

        ast.addChild(new AST(ctx.ID().getSymbol()));
        ast.addChild(visit(ctx.expr()));
        return ast;
    }

    @Override
    public AST visitStatPrint(StatPrintContext ctx) {
        AST ast = new AST(ctx.print);
        ast.addChild(visit(ctx.expr()));
        return ast;
    }

    @Override
    public AST visitExprMult(ExprMultContext ctx) {
        AST ast = new AST(ctx.op);
        ast.addChild(visit(ctx.left));
        ast.addChild(visit(ctx.right));
        return ast;
    }

    @Override
    public AST visitExprAdd(ExprAddContext ctx) {
        AST ast = new AST(ctx.op);
        ast.addChild(visit(ctx.left));
        ast.addChild(visit(ctx.right));
        return ast;
    }

    @Override
    public AST visitExprVec(ExprVecContext ctx) {
        AST ast = new AST(new CommonToken(VecMathParser.VEC, "VEC"));
        for (ExprContext expr : ctx.expr()) {
            ast.addChild(visit(expr));
        }
        return ast;
    }

    @Override
    public AST visitExprId(ExprIdContext ctx) {
        AST ast = new AST(ctx.ID().getSymbol());
        return ast;
    }

    @Override
    public AST visitExprInt(ExprIntContext ctx) {
        AST ast = new AST(ctx.INT().getSymbol());
        return ast;
    }
}

抽象语法树（AST）

本质上只是相对于tpdsl-code/IR/Homo的原始版本调整了令牌。

package  walking.v4.vecmath_ast.impl;

import org.antlr.v4.runtime.CommonToken;
import org.antlr.v4.runtime.Token;

import walking.v4.vecmath_ast.antlr.VecMathParser;

import java.util.ArrayList;
import java.util.List;

// Homogenous AST node type 
public class AST {
   Token token;             // from which token do we create this node?
   List<AST> children;      // normalized list of children 

   public AST() { ; } // for making nil-rooted nodes

   public AST(Token token) { this.token = token; }

   /** Create node from token type; used mainly for imaginary tokens */
   public AST(int tokenType) { this.token = new CommonToken(tokenType); }

   /** external visitors execute the same action for all nodes
    * with same node type while walking
    */
    public int getNodeType() { return token.getType(); }

    public void addChild(AST t) {
        if (children == null) children = new ArrayList<>();
        children.add(t);
    }

    public List<AST> getChildren() { return children; }
    
    /** to represent flat lists. A list is a subtree w/o a root, which we simulate
     * with a nil root node. A nil node is a node with token == null.
     */
    public boolean isNil() { return token == null; }

    /** Compute string for single node */
    public String toString() { 
        String typeName = VecMathParser.VOCABULARY.getSymbolicName(getNodeType());
        typeName = typeName == null ? token.getText() : typeName;
        return token != null ? "<" +typeName +", '" + token.getText() +"'>": "nil"; 
    }

    /** Compute string for a whole tree */
    public String toStringTree() {
        if (children == null || children.size() == 0) return this.toString();

        StringBuffer buf = new StringBuffer();
        if (!isNil()) {
           buf.append('(');
           buf.append(this.toString());
           buf.append(' ');
        }
        for (int i = 0; i < children.size(); i++) {
            AST t = (AST) children.get(i); // normalized (unnamed) children
            if (i>0) buf.append(' ');
            buf.append(t.toStringTree());
        }
        if (!isNil()) buf.append(')');
        return buf.toString();
    }
}

测试类

package walking.v4.vecmath_ast;

import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;

import walking.v4.vecmath_ast.antlr.VecMathLexer;
import walking.v4.vecmath_ast.antlr.VecMathParser;

import walking.v4.vecmath_ast.impl.AST;
import walking.v4.vecmath_ast.impl.VecMathBuildASTVisitor;

public class Test {
    public static void main(String[] args) throws Exception {
        CharStream input = CharStreams.fromFileName(args[0]);
        VecMathLexer lexer = new VecMathLexer(input);

        CommonTokenStream tokens = new CommonTokenStream(lexer);
        VecMathParser parser = new VecMathParser(tokens);

        ParseTree tree = parser.prog();

        for (AST ast : new VecMathBuildASTVisitor().visit(tree).getChildren()) {
            System.out.println(ast.toStringTree());
        }
    } 
}

测试输入

x = 3 + 4
y = 3 + 4 + 5
a = 3 * 4
a = 3 * 4 * 5
c = 3 * 4 + 5
print x * [2, 3, 4]
print x * [2+5, 3, 4]

产生：

(<=, '='> <ID, 'x'> (<+, '+'> <INT, '3'> <INT, '4'>))
(<=, '='> <ID, 'y'> (<+, '+'> (<+, '+'> <INT, '3'> <INT, '4'>) <INT, '5'>))
(<=, '='> <ID, 'a'> (<*, '*'> <INT, '3'> <INT, '4'>))
(<=, '='> <ID, 'a'> (<*, '*'> (<*, '*'> <INT, '3'> <INT, '4'>) <INT, '5'>))
(<=, '='> <ID, 'c'> (<+, '+'> (<*, '*'> <INT, '3'> <INT, '4'>) <INT, '5'>))
(<print, 'print'> (<*, '*'> <ID, 'x'> (<VEC, 'VEC'> <INT, '2'> <INT, '3'> <INT, '4'>)))
(<print, 'print'> (<*, '*'> <ID, 'x'> (<VEC, 'VEC'> (<+, '+'> <INT, '2'> <INT, '5'>) <INT, '3'> <INT, '4'>)))

- jmkg