CSE411: Introduction to Compilers

Visitor Pattern

Jooyong Yi (UNIST)

Our Situation

• A tree to traverse: parse tree and AST
• Visitors to perform various tasks: AST generation, type checking, IR generation

The Task in Essence

• How to invoke the correct visit method corresponding to the child node type?

class Visitor implements VisitorInterface {
    @Override
    public boolean visit(ReturnStatement node) { ... }

    @Override
    public boolean visit(BinaryExpression node) { ... }

    ...
}

Would this work?

class Visitor implements VisitorInterface {
    @Override
    public boolean visit(ReturnStatement node) { 
        ... 
        this.visit(childNode); 
        ...
    }

    @Override
    public boolean visit(BinaryExpression node) { ... }

    ...
}

Visitor Pattern

class Visitor implements VisitorInterface {
    @Override
    public boolean visit(ReturnStatement node) { 
        ... 
        childNode.accept(this);
        ...
    }
}

class BinaryExpression extends Expression {
    @Override
    void accept(VisitorInterface visitor) {
        visitor.visit(this);
    }
}

Multiple Dispatch

class Visitor implements VisitorInterface {
    @Override
    public boolean visit(ReturnStatement node) { 
        ... 
        this.visit(childNode); // this works fine if the language supports multiple dispatch (e.g., Groovy, Julia)
        ...
    }

    @Override
    public boolean visit(BinaryExpression node) { ... }

    ...
}

Alternative Approach

class Visitor implements VisitorInterface {
    ...
    public boolean visit(Expression node) {
        if (node instanceof BinaryExpression) {
            return visit((BinaryExpression) node);
        } else if (node instanceof UnaryExpression) {
            return visit((UnaryExpression) node);
        } else if (node instanceof ArrayAccess) {
            return visit((ArrayAccess) node);
        } else {
            throw new AssertionError("Unknown expression type: " + node.getClass().getName());
        }
    }
    ...
}

• What would happen if you add a new expression type such as TernaryExpression?

Visitor Pattern

interface VisitorInterface {
    boolean visit(UnaryExpression node);
    boolean visit(BinaryExpression node);
}

What would happen if we add the following?

class TernaryExpression extends Expression {
    @Override
    void accept(VisitorInterface visitor) {
        visitor.visit(this);
    }
}