Java AST 遍历

Question

所以，我目前正在通过使用 ANTLR 和 Java 来实现 DSL。到目前为止，我已经基于 ANTLR 语法创建了自己的 AST 层次结构。为什么？因为不幸的是，ANTLR v4不支持output=AST。

无论如何，层次结构可以简化如下:

Expressions
-> BinaryExpressions(Expressions, Expressions)
    -> Multiplication(Expression, Expression)
    -> Addition(Expression, Expression)
    -> Greater_Equal(Expression, Expression)
    -> Less_Equal(Expression, Expression)

这样的例子不胜枚举。不管怎样，考虑到这一点，到目前为止我已经创建了一个组织良好的层次结构。例如 3 + (2 * 3) 会产生如下结果:

Addition(Integer(3), Multiplication(Integer(2), Integer(3))

其中对象的类是加法。

无论如何，鉴于此，我如何遍历这个层次结构？上面的示例只是总体复杂性的快速概述，但是如何使用递归函数对此进行迭代？因为例如，定义 for (ASTNode node : someNode) 不起作用，因为 ASTNode 的对象(顶级类 - 所有类的母体)无法迭代。

谢谢!

Answer 1

这实际上取决于您想要做什么。

例如，如果您想计算刚刚解析的公式，您可以通过定义接口(interface)为每个 AST 节点赋予一个 eval() 方法:

public interface Evaluable {
    Something eval();
}

此时，您可以定义所有节点的操作，例如:

public class Integer implements Evaluable {
    @Override
    public Something eval() {
        return value;
    }

    private final Something value;
}

然后:

public class Multiplication implements Evaluable {
    @Override
    public Something eval() {
        return left.eval().product(right.eval());
    }

    private final Expression left;
    private final Expression right;
}

等等。

此时，您在根节点上调用.eval()，该调用将递归传播，并将结果传播回顶部。

这只是一个快速解决方案。更精致(和复杂)的依赖于双重间接模式，其中 eval 方法传递一个 Evaluator，它为每种类型定义一个重载的 eval 方法并封装操作，从而将它们与 AST 节点分开。