Обход AST

Дерево само по себе бесполезно — ценность появляется, когда мы умеем его обходить.

Обход дерева — рекурсивный проход по всем узлам AST, при котором для каждого узла выполняется нужное действие в зависимости от его типа.

AST построено — что дальше? Любая фаза после парсера сводится к обходу дерева: вычислить значение, проверить типы, напечатать, сгенерировать код. Освоив обход, вы получаете универсальный инструмент.

Рекурсивный обход

Идея проста: чтобы обработать узел, сначала рекурсивно обработай его детей, затем сам узел. Для бинарной операции — обойди левое поддерево, правое, потом примени операцию.

class Num:
    def __init__(self, value): self.value = value
class BinOp:
    def __init__(self, op, left, right):
        self.op = op; self.left = left; self.right = right

def evaluate(node):
    if isinstance(node, Num):
        return node.value
    left = evaluate(node.left)
    right = evaluate(node.right)
    if node.op == "+": return left + right
    if node.op == "-": return left - right
    if node.op == "*": return left * right
    if node.op == "/": return left / right

tree = BinOp("+", Num(2), BinOp("*", Num(3), Num(4)))
print(evaluate(tree))

Вывод:

14

Это и есть интерпретатор в зародыше! Функция evaluate спускается до листьев (чисел), а на обратном пути собирает результат снизу вверх. Узел (3 * 4) вычисляется в 12 прежде, чем сложение его использует.

Паттерн visitor

Когда типов узлов много, цепочка if isinstance разрастается. Паттерн visitor предлагает по методу на тип узла, а диспетчеризацию делать по имени класса.

class Num:
    def __init__(self, v): self.value = v
class BinOp:
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r

class Evaluator:
    def visit(self, node):
        name = "visit_" + type(node).__name__
        return getattr(self, name)(node)
    def visit_Num(self, node):
        return node.value
    def visit_BinOp(self, node):
        l, r = self.visit(node.left), self.visit(node.right)
        return {"+": l + r, "-": l - r, "*": l * r, "/": l / r}[node.op]

tree = BinOp("-", BinOp("+", Num(10), Num(5)), Num(3))
print(Evaluator().visit(tree))

Вывод:

12

Как работает под капотом

Метод visit по имени класса узла (type(node).__name__) находит нужный метод visit_Num или visit_BinOp через getattr. Добавить новый тип узла — значит просто дописать новый метод visit_..., не трогая остальной код. Именно так устроены настоящие интерпретаторы и компиляторы, например модуль ast в стандартной библиотеке Python.

Печать дерева разными способами

Меняя момент обработки узла, получаем разные порядки. Если печатать оператор между детьми — это инфиксная запись; до детей — префиксная (польская); после — постфиксная (обратная польская).

class Num:
    def __init__(self, v): self.value = v
class BinOp:
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r

def postfix(node):
    if isinstance(node, Num): return str(node.value)
    return postfix(node.left) + " " + postfix(node.right) + " " + node.op

tree = BinOp("+", Num(2), BinOp("*", Num(3), Num(4)))
print(postfix(tree))

Вывод:

2 3 4 * +

Частые ошибки

Главная — забыть рекурсивно обойти детей и попытаться обработать узел «сразу». Без рекурсии вы не доберётесь до листьев, и значения вложенных операций потеряются.

Вторая — в visitor забыть метод для какого-то типа узла. Тогда getattr не найдёт visit_... и упадёт с AttributeError. Полезно добавить запасной метод generic_visit с понятной ошибкой.

Итог

• Обход AST — рекурсивный проход: сначала дети, потом сам узел.
• Вычисление выражения — это обход дерева, собирающий результат снизу вверх.
• Паттерн visitor даёт по методу на тип узла и легко расширяется.
• Порядок обработки узла относительно детей задаёт инфиксную, префиксную или постфиксную запись.