Practice: Should This Compiler Use a Visitor?

A fixed set of syntax node types, and new checks added every release.

A compiler that gains new checks every release is a candidate for the Visitor pattern, and this exercise asks you to judge whether it fits, then sketch it. Read the scenario and answer before opening the solution.

A team maintains a compiler for a small arithmetic language. Its parser produces trees of node classes: Number and Divide today, and the language specification has not changed in three years. Each release adds new checks over those trees, such as warning about division by a literal zero, and the next release plans three more.

Does Visitor fit? Name the change that is expected often and the one that is expected rarely.
Sketch a visitor that warns about division by a literal zero. Which methods does it need?
The tree for (8 / 0) / 2 has a division nested inside another. How does your visitor reach the inner one?

Show a solution

Visitor fits. New checks, which are new operations, arrive every release; new node classes depend on the specification, which rarely changes. That is the direction Visitor makes cheap. Each check becomes one visitor, and the node classes keep only accept.

from __future__ import annotations

from abc import ABC, abstractmethod
from dataclasses import dataclass


class NodeVisitor(ABC):
    @abstractmethod
    def visit_number(self, node: Number) -> None: ...

    @abstractmethod
    def visit_divide(self, node: Divide) -> None: ...


@dataclass(frozen=True)
class Number:
    value: int

    def accept(self, visitor: NodeVisitor) -> None:
        visitor.visit_number(self)


@dataclass(frozen=True)
class Divide:
    left: Number | Divide
    right: Number | Divide

    def accept(self, visitor: NodeVisitor) -> None:
        visitor.visit_divide(self)


class DivisionByZeroCheck(NodeVisitor):
    def __init__(self) -> None:
        self.warnings: list[str] = []

    def visit_number(self, node: Number) -> None:
        pass

    def visit_divide(self, node: Divide) -> None:
        if node.right == Number(0):
            self.warnings.append(f"division by zero: {node.left} / 0")
        node.left.accept(self)
        node.right.accept(self)


program = Divide(Divide(Number(8), Number(0)), Number(2))
check = DivisionByZeroCheck()
program.accept(check)
print(check.warnings)

OutputRan with python:3.12-slim (Python 3.12.13)

['division by zero: Number(value=8) / 0']

The check reports the inner division and then visits both children.

The visitor needs one method per node class: visit_number does nothing, and visit_divide checks its right operand. It reaches the inner division by calling accept on both children, so the walk follows the tree. The outer division by 2 is not reported, and the inner one is.

If the specification later added Multiply, every check would need a visit_multiply, which is the cost the team is accepting.

← → move through sections and cards