CODEWITHSUNDEEP
javaantlrtraversalabstract-syntax-tree
Dominik Safaric
Dominik Safaric

Reputation: 38

Java AST traversal

so, I'm currently working on a DSL implementation by using ANTLR with Java. By so far, I've created my own AST hierarchy based on the ANTLR grammar. Why? Because unfortunately, ANTLR v4 doesn't support output=AST.

Anyway, the hierarchy can be simplified as the following:

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

and the list goes on. Anyway, given this, I produce a quite well organised hierarchy so far. So for example 3 + (2 * 3) would produce something like:

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

where the class of the object is addition.

Anyway, given this, how can I traverse over this hierarchy? The example above is just a quick overview of the overall complexity, but how can I by using recursive functions iterate over this? Because for instance, defining for (ASTNode node : someNode) doesn't work because the object of ASTNode (top level class - the mother of all classes) cannot be iterated.

Thanks!

Upvotes: 1

Views: 780

Answers (1)

Stefano Sanfilippo
Stefano Sanfilippo

Reputation: 33046

It depends on what you are trying to do, really.

For instance, if you want to evaluate the formula you just parsed, you could endow each AST node with a eval() method, by defining an interface:

public interface Evaluable {
    Something eval();
}

at this point, you can define the operation for all nodes, like:

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

    private final Something value;
}

and then:

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

    private final Expression left;
    private final Expression right;
}

and so on.

At this point, you call .eval() on the root node and the call will be recursively propagated, and the result propagated back to the top.

This is just a quick solution. More refined (and complicated) ones rely on a double indirection pattern, in which the eval method is passed an Evaluator, which defines an overloaded eval method for each type and encapsulates the operations, thus separating them from the AST nodes.

Upvotes: 1

Related Questions