如何用 ANTLR4 创建 AST？

Question

我一直在搜索很多关于这个的东西，但我找不到任何真正帮助我构建 AST 的有用信息。我已经知道 ANTLR4 不像 ANTLR3 过去那样构建 AST。每个人都说："Hey, use visitors!"，但我找不到任何示例或更详细的解释，说明我该怎么做...

我有一个语法必须喜欢 C，但每个命令都是用葡萄牙语（葡萄牙语编程语言）编写的。我可以使用 ANTLR4 轻松生成解析树。我的问题是：我现在需要做什么来创建 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 中的 this tutorial，但我不知道如何使用 StringTamplate 而不是 ST...

正在阅读这本书The Definitive ANTLR 4 Reference我也找不到任何与 AST 相关的内容。

EDIT2: 现在我有一个 class 来创建 DOT 文件，我只需要弄清楚如何正确使用访问者

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 规则可以处理所有事情（优先规则等）。

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 classes）。我们现在必须将它们转换为 AST 节点。

访问者很容易做到这一点，ANTLR 为我们提供了 MathBaseVisitor<T> class，让我们开始吧。

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 class 的合适方法的快速方法） .

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

AST 访客

现在，让我们来玩一下 AST。我们必须构建一个 AST 访问者库 class 来遍历它。让我们做一些类似于 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();
        }
    }
}

现在我们终于可以玩了：

Answer 2

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

为了减小 AST 的大小，您可以使用一个 NodeFilter，您可以在其中添加您在构建 AST 时希望考虑的非终结符的生产规则名称。

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

希望这个工具有用;-)

Answer 3

我找到了两个简单的方法，重点放在antlr4的TestRig.java文件中可用的功能。

通过终端

这是我用对应的CPP14.g4语法文件解析C++的例子 java -cp .:antlr-4.9-complete.jar org.antlr.v4.gui.TestRig CPP14 translationunit -tree filename.cpp。如果您省略 filename.cpp，装备会从标准输入读取。 “translationunit”是我使用的CPP14.g4语法文件的起始规则名称。

通过Java

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

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 文件。

如何用 ANTLR4 创建 AST？

How to create AST with ANTLR4?

java

compiler-construction

antlr

abstract-syntax-tree

antlr4

语法

AST 节点

将 CST 转换为 AST

AST 访客

使用 AST

综合起来