Абстрактное синтаксическое дерево: представление, обход, паттерн Visitor

Парсер из прошлой статьи вернул дерево, и с этого момента текст программы больше никому не нужен: разрешение имён, проверка типов, свёртка констант и генерация кода работают не с символами, а с деревом. AST перестаёт быть «результатом парсинга» и становится внутренним API компилятора — а значит, его качество определяет, сколько боли будет в остальных статьях трека. Плохое дерево — это узел с полем kind: str и словарём атрибутов, потерянные позиции в исходнике, детали, выброшенные там, где были нужны. Хорошее — структура, по которой проход пишется за двадцать строк и который невозможно написать неполным: язык не даст. Дальше — как дерево представить, как обойти и как организовать двадцать проходов, чтобы они не стали двадцатью копиями одного isinstance-каскада; в конце — работающий AST-интерпретатор Mini, вычисляющий fib(10).

Что AST теряет намеренно

Дерево разбора (parse tree, CST) — буквальный протокол работы грамматики: каждое применённое правило порождает узел. AST — то же дерево без всего, что служило только разбору (картинки со сравнением были в 02).

Выбрасываем то, что уже выражено формой дерева. Скобки не нужны: (2 + 3) * 4 и 2 + 3 * 4 отличаются не токенами, а вложенностью, а вложенность записана. Не нужны запятые, точки с запятой, then, do, end — они были нужны, чтобы парсер понял, где кончается конструкция; парсер понял. Не нужны цепочки Expr → Term → Factor → Primary → 42, жившие ради приоритетов операторов.

Оставляем смысл и позиции. Смысл — оператор, операнды, имена, литералы, порядок инструкций. Позиции (span) — то, без чего компилятор скажет «ошибка типа», но не скажет где: сообщение об ошибке, подсветка в IDE, покрытие кода, отладочная информация и стек-трейс — всё это в итоге разворачивание диапазона символов из узла. Правило: новый узел не создаётся без span’а, и span родителя покрывает span всех потомков — инвариант, который стоит проверять тестами.

Инструментам разработчика нужно обратное — не терять ничего: форматтер обязан знать про пробелы, а рефакторинг — сохранить комментарии на местах. Такие деревья называют lossless syntax tree: у Roslyn это red-green trees, у rust-analyzer — rowan, в Python — LibCST. Правило индустрии: компилятору — AST, IDE — lossless-дерево.

Дизайн узлов: AST — это алгебраический тип данных

Формально AST — сумма произведений: «выражение — это ИЛИ литерал (число), ИЛИ имя (строка), ИЛИ бинарная операция (оператор, левый, правый), ИЛИ вызов (имя, список аргументов)» — буквально определение алгебраического типа. Языки со встроенными суммами (ML, Haskell, Rust, Scala, Swift) популярны у авторов компиляторов именно поэтому; взгляд на ту же структуру глазами разных парадигм помогает не считать Visitor единственным способом работать с деревом. Записать абстрактный синтаксис удобно в нотации, близкой к ASDL — на ней описан абстрактный синтаксис самого Python, а классы узлов генерируются из этого файла (? — необязательное поле, * — список):

expr  = IntLit(int value) | BoolLit(bool value) | Name(identifier ident)
      | Unary(op op, expr operand) | Binary(op op, expr left, expr right)
      | Call(identifier callee, expr* args)
stmt  = Let(identifier name, type? ann, expr value) | Return(expr? value)
      | If(expr cond, block then_br, block? else_br) | ExprStmt(expr expr)
block = Block(stmt* stmts)
decl  = FnDecl(identifier name, param* params, type? ret, block body)

Здесь принимается главное решение: выражения и инструкции разделены. В Mini if — инструкция, поэтому let x = if ... не выразится даже структурно; в Rust и Kotlin решили иначе, и там if — вариант expr. Такие вещи фиксируются формой дерева, а не проверками в коде: чем больше некорректных программ невозможно построить, тем меньше проверок писать потом.

Узлы Mini на Python

from __future__ import annotations
from dataclasses import dataclass, fields, replace
from typing import Iterator

node = dataclass(frozen=True, slots=True)   # общий декоратор для всех узлов

@node
class Span:
    start: int          # смещение первого символа в исходнике
    end: int            # смещение за последним

class Node: ...         # общий предок: нужен для isinstance и обобщённого обхода
class Expr(Node): ...
class Stmt(Node): ...

@node
class IntLit(Expr):
    value: int
    span: Span

@node
class Binary(Expr):
    op: str                      # "+" "-" "*" "/" "<" ">" "==" "!="
    left: Expr
    right: Expr
    span: Span

@node
class Call(Expr):
    callee: str
    args: tuple[Expr, ...]       # кортеж, а не список: узел неизменяем целиком
    span: Span

# Остальные узлы из ASDL выше — по тому же образцу: BoolLit(value), Name(ident), Unary(op, operand),
# Let(name, type_ann, value), If(cond, then_br, else_br), Return(value), ExprStmt(expr),
# Block(stmts), Param(name, type_ann), FnDecl(name, params, ret_type, body), Program(items).
# У каждого последнее поле — span; type_ann равен None, если тип не написан (выведем в статье 05).

Четыре решения здесь неслучайны:

• frozen=True — не догма из ФП, а защита: дерево читают десятки проходов, и «кто-то по дороге поменял поле» — худший класс багов в компиляторе. Преобразования строят новые узлы, переиспользуя неизменившиеся поддеревья, ровно как персистентные структуры.
• slots=True — узлов будет много: без слотов у экземпляра есть __dict__ (плюс около сотни байт), со слотами Binary занимает примерно 56 байт. На миллионе узлов это десятки мегабайт.
• Отдельный класс на вид узла вместо универсального с kind: str: универсальный гибок ровно до первой опечатки n.oprand, которая доедет до продакшна, — с классами её ловит mypy до запуска.
• Кортежи вместо списков: узел неизменяем целиком, а не наполовину.

В TypeScript, Rust, Swift и Kotlin ту же роль играет размеченное объединение — механика разобрана в TypeScript: фундамент. Его главное достоинство в том, что полноту разбора проверяет компилятор:

type Span = { start: number; end: number };

type Expr =
  | { kind: "IntLit"; value: number; span: Span }
  | { kind: "Binary"; op: "+" | "*"; left: Expr; right: Expr; span: Span };

function evalExpr(n: Expr): number {
  switch (n.kind) {
    case "IntLit": return n.value;
    case "Binary": {
      const a = evalExpr(n.left), b = evalExpr(n.right);
      return n.op === "+" ? a + b : a * b;
    }
    default: {
      const impossible: never = n;   // добавили вид узла и забыли ветку — ошибка компиляции
      throw new Error(`необработанный узел: ${JSON.stringify(impossible)}`);
    }
  }
}

В Python тот же эффект даёт match вместе с typing.assert_never.

Ещё один узел, без которого не бывает нормальной IDE, — узел-ошибка. Не сумев разобрать конструкцию, парсер не падает, а вставляет ErrorNode(span) и продолжает: тогда проверка типов увидит остальные 99% файла. Правило для последующих проходов — встретил ErrorNode, молча пропусти, диагностику уже выдал парсер. Про эргономику ошибок — 12.

Обход: три порядка

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

Pre-order (узел до детей) — когда информация течёт сверху вниз: собрать объявления, протащить текущую область видимости, пометить «мы внутри цикла». Post-order (узел после детей) — когда снизу вверх: вычислить значение, вывести тип, сгенерировать код. Post-order — рабочая лошадка компилятора: к моменту обработки узла результаты детей готовы, поэтому байткод стековой машины получается буквально печатью дерева в post-order (так и работал мини-компилятор из обзорной статьи, подробно — в 09). In-order нужен тем, кто печатает дерево обратно в текст: форматтеру, которому придётся ещё и восстановить скобки по приоритетам. Механика обходов разобрана в Деревьях и BST, а дерево как частный случай графа — в Обходе графов и Теории графов.

Обобщённый доступ к детям через интроспекцию датаклассов избавляет от перечисления полей руками в каждом проходе:

def children(node: Node) -> Iterator[Node]:
    """Дочерние узлы в порядке объявления полей (потому поля и объявляем как в исходнике)."""
    for f in fields(node):
        v = getattr(node, f.name)
        if isinstance(v, Node):
            yield v
        elif isinstance(v, tuple):
            for item in v:
                if isinstance(item, Node):
                    yield item

def walk(node: Node) -> Iterator[Node]:
    """Итеративный pre-order: стек в куче вместо кадров вызовов."""
    stack = [node]
    while stack:
        cur = stack.pop()
        yield cur
        stack.extend(reversed(list(children(cur))))   # reversed — чтобы дети шли слева направо

Сложность. Любой обход — O(n) по времени: каждое ребро проходится ровно один раз. Память — O(h), где h — глубина дерева, а не O(n): в стеке живёт только текущий путь от корня. Для рукописного кода h ≈ 10–30, для сгенерированного — тысячи, и вот тут рекурсивный обход ломается. Цепочка 1 + 1 + 1 + ... из 20 тысяч слагаемых даёт RecursionError в Python и падение процесса в C или Rust, а walk из примера выше проходит её спокойно. Случай не искусственный: таблицы констант, embedded-ресурсы, protobuf-дескрипторы и минифицированный JS регулярно дают такую глубину. Настоящие компиляторы ставят лимит вложенности как часть спецификации (у Clang это -fbracket-depth, по умолчанию 256 — ошибка «too deeply nested» честнее краша), проверяют запас стека перед спуском (rustc вызывает ensure_sufficient_stack из крейта stacker), используют явный стек или стартуют с увеличенным стеком. Совет для своего языка: пишите проходы рекурсивно, это на порядок читаемее, но заведите в парсере счётчик глубины и внятное сообщение при превышении — теория в Рекурсии и «разделяй и властвуй».

Паттерн Visitor

Первый проход по дереву всегда пишется каскадом if isinstance(n, IntLit) ... elif isinstance(n, Binary) .... Проблема не в красоте: таких функций будет двадцать — печать, разрешение имён, проверка типов, свёртка констант, кодогенерация, линтер, форматтер. Каждая повторяет тот же каскад, и при добавлении узла надо не забыть дописать все двадцать, а никто не напомнит: цепочка с else в конце молча проглотит новый вид узла.

Visitor переносит ветвление в одно место через двойную диспетчеризацию. Узел умеет одно — позвать у посетителя метод, соответствующий своему типу; посетитель реализует метод на каждый вид узла:

class IntLit(Expr):
    def __init__(self, value): self.value = value
    def accept(self, v): return v.visit_int(self)         # 1-я диспетчеризация: по типу узла

class Binary(Expr):
    def __init__(self, op, l, r): self.op, self.left, self.right = op, l, r
    def accept(self, v): return v.visit_binary(self)

class EvalVisitor:                                        # 2-я диспетчеризация: по типу посетителя
    def visit_int(self, n): return n.value
    def visit_binary(self, n):
        a, b = n.left.accept(self), n.right.accept(self)
        return a + b if n.op == "+" else a * b

Binary("+", IntLit(2), Binary("*", IntLit(3), IntLit(4))).accept(EvalVisitor())   # 14

Почему «двойная»: обычный вызов метода выбирает реализацию по одному типу — получателя. Здесь надо выбрать по двум: какой узел и какая операция. accept даёт первое измерение, вложенный visit_* — второе.

В Python (и в любом языке с интроспекцией) писать accept в каждом узле незачем: диспетчеризацию делает поиск метода по имени класса. Ровно так устроен ast.NodeVisitor из стандартной библиотеки:

class Visitor:
    def visit(self, node: Node):
        method = getattr(self, "visit_" + type(node).__name__, self.generic_visit)
        return method(node)

    def generic_visit(self, node: Node):
        """Поведение по умолчанию: просто спуститься к детям."""
        for child in children(node):
            self.visit(child)

Ключевая деталь — generic_visit: проход, которому интересны только вызовы функций, пишется как класс с единственным методом visit_Call, остальное дерево обходится само. Обратная сторона — потеря проверки полноты: забытый visit_* не ошибка, а молчаливое «обойти детей». Участники и ловушки паттерна разобраны в Поведенческих паттернах, механика двойной диспетчеризации — в ООП.

Expression problem: за что мы платим

Строки воображаемой таблицы — виды узлов, столбцы — операции над ними; разложить код по этой таблице можно ровно тремя способами.

Это expression problem в формулировке Уодлера: расширять систему в обоих измерениях, не трогая старый код и не теряя типобезопасность, в классическом ООП нельзя. Для компилятора выбор очевиден — набор видов узлов меняется редко, набор проходов постоянно, поэтому Visitor норма для компиляторов и антипаттерн для доменных моделей, где всё наоборот. Третья строка таблицы — причина, по которой в Rust, OCaml, Scala и современном Python Visitor часто не пишут вовсе:

def eval_match(n: Node, env: dict[str, int]) -> int:
    match n:
        case IntLit(value=v):                 return v
        case Name(ident=x):                   return env[x]
        case Binary(op="+", left=l, right=r): return eval_match(l, env) + eval_match(r, env)
        case _: raise TypeError(f"нечего вычислять: {type(n).__name__}")

Практический выбор: проход трогает 2–5 видов узлов и хочет обойти остальное по умолчанию — Visitor с generic_visit; проход обязан обработать все виды (проверка типов, кодогенерация) — match или switch с проверкой полноты. В одном компиляторе нормально иметь оба.

Работающий кусок: AST-интерпретатор Mini

Ниже — интерпретатор, который обходит дерево и выполняет программу: уже настоящий язык с переменными, условиями, функциями и рекурсией. Медленный, но работающий — многие DSL живут так и никогда не доходят до байткода.

class ReturnSignal(Exception):
    """Возврат из функции: раскручивает стек обхода до места вызова."""
    def __init__(self, value): self.value = value

BIN = {"+": lambda x, y: x + y,   "-": lambda x, y: x - y,
       "*": lambda x, y: x * y,   "/": lambda x, y: x // y,
       "<": lambda x, y: x < y,   ">": lambda x, y: x > y,
       "==": lambda x, y: x == y, "!=": lambda x, y: x != y}

class Interpreter(Visitor):
    def __init__(self) -> None:
        self.funcs: dict[str, FnDecl] = {}
        self.scopes: list[dict[str, object]] = [{}]     # черновые области видимости, см. статью 04

    def lookup(self, name: str):
        for scope in reversed(self.scopes):
            if name in scope:
                return scope[name]
        raise NameError(f"имя {name!r} не найдено")

    # --- выражения: возвращают значение, обрабатываются в post-order ---
    def visit_IntLit(self, n):  return n.value
    def visit_BoolLit(self, n): return n.value
    def visit_Name(self, n):    return self.lookup(n.ident)
    def visit_Unary(self, n):   v = self.visit(n.operand); return -v if n.op == "-" else not v

    def visit_Binary(self, n):
        a, b = self.visit(n.left), self.visit(n.right)   # дети вычисляются первыми
        return BIN[n.op](a, b)

    def visit_Call(self, n):
        args = [self.visit(a) for a in n.args]
        if n.callee == "print":
            print(*args)
            return None
        fn = self.funcs[n.callee]
        self.scopes.append({p.name: v for p, v in zip(fn.params, args)})   # кадр вызова
        try:
            self.visit(fn.body)
            return None                                  # функция без return
        except ReturnSignal as r:
            return r.value
        finally:
            self.scopes.pop()

    # --- инструкции: возвращают None, работают ради эффекта ---
    def visit_Let(self, n):      self.scopes[-1][n.name] = self.visit(n.value)
    def visit_ExprStmt(self, n): self.visit(n.expr)
    def visit_Return(self, n):   raise ReturnSignal(None if n.value is None else self.visit(n.value))

    def visit_Block(self, n):
        for s in n.stmts:
            self.visit(s)

    def visit_If(self, n):
        if self.visit(n.cond):
            self.visit(n.then_br)
        elif n.else_br is not None:
            self.visit(n.else_br)

    def visit_Program(self, n):
        for item in n.items:                             # 1-й проход: собрать функции
            if isinstance(item, FnDecl):
                self.funcs[item.name] = item
        for item in n.items:                             # 2-й проход: выполнить инструкции
            if not isinstance(item, FnDecl):
                self.visit(item)

На дереве программы из обзорной статьи — fn fib(n: Int) { if n < 2 { return n; } return fib(n - 1) + fib(n - 2); }, затем let limit: Int = 6 + 4; let result = fib(limit); print(result); — это печатает 55. Дерево той программы содержит 31 узел при глубине 8, что проверяется обобщённым обходом (sum(1 for _ in walk(prog))).

Три решения здесь типовые. Два прохода по Program — иначе fib не смог бы вызвать сам себя. return через исключение: обход это рекурсия, а выход из её середины — раскрутка стека; в машинном коде он станет обычным jmp. Выражения возвращают значение, инструкции нет — то же разделение, что в типах узлов, доведённое до конца. Области видимости наивные (список словарей, блок не создаёт своей области) — сознательный долг, который вернём в следующей статье. Цена такой интерпретации: каждый узел — виртуальный вызов, проверка типа объекта и разыменование указателей, порядка 10–50 нс на узел против единиц наносекунд на инструкцию байткода. AST-интерпретатор — отличный первый рантайм и плохой последний; переход к байткоду — 09.

Преобразование дерева: Transformer

Проход, который переписывает дерево, отличается одним: он возвращает узел. Базовый класс делает скучную часть — рекурсивно перестраивает детей и создаёт новый узел, только если что-то изменилось:

class Transformer:
    def transform(self, node: Node) -> Node:
        method = getattr(self, "tr_" + type(node).__name__, None)
        rebuilt = self.rebuild(node)              # сначала дети (post-order), потом сам узел
        return method(rebuilt) if method else rebuilt

    def rebuild(self, node: Node) -> Node:
        changes = {}
        for f in fields(node):
            v = getattr(node, f.name)
            if isinstance(v, Node):
                nv = self.transform(v)
                if nv is not v:
                    changes[f.name] = nv
            elif isinstance(v, tuple) and any(isinstance(x, Node) for x in v):
                nv = tuple(self.transform(x) if isinstance(x, Node) else x for x in v)
                if any(a is not b for a, b in zip(nv, v)):
                    changes[f.name] = nv
        return replace(node, **changes) if changes else node   # ничего не менялось — тот же объект

class ConstFold(Transformer):
    OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
           "*": lambda a, b: a * b, "/": lambda a, b: a // b}

    def tr_Binary(self, n: Binary):
        if isinstance(n.left, IntLit) and isinstance(n.right, IntLit) and n.op in self.OPS:
            if n.op == "/" and n.right.value == 0:
                return n                          # деление на ноль не сворачиваем: это ошибка рантайма
            return IntLit(self.OPS[n.op](n.left.value, n.right.value), n.span)
        return n

ConstFold().transform(prog) превращает let limit: Int = 6 + 4 в let limit: Int = 10, при этом узел FnDecl fib остаётся физически тем же объектом (folded.items[0] is prog.items[0] даёт True). Это структурное разделение: преобразование стоит O(k) по памяти, где k — число изменённых узлов и их предков, а не O(n); по времени проход — O(n). Три правила, экономящие часы отладки:

1. Не мутировать узлы на месте — если на дерево держит ссылку кто-то ещё (кэш IDE, предыдущая версия для сравнения), мутация испортит и его.
2. Сохранять span исходного узла в новом, иначе после десугаринга ошибка типов покажет на позицию ноль. Именно так у компиляторов появляются сообщения, указывающие «не туда».
3. Разделять десугаринг и оптимизацию. Десугаринг обязателен и уменьшает язык (for → while, a += b → a = a + b, унарный минус → вычитание из нуля), оптимизация необязательна и меняет только производительность. Смешение даёт компилятор, который «иногда неправильно считает». Про свёртку всерьёз, с переполнением и порядком вычислений, — 07.

В стандартной библиотеке Python есть готовые ast.NodeVisitor и ast.NodeTransformer с той же семантикой — полезно прочитать их целиком, там около сотни строк.

Проходы по дереву в настоящем компиляторе

Один проход — редкость. Фронтенд это цепочка проходов, где каждый либо перестраивает дерево, либо накапливает информацию сбоку:

Результаты анализа не записываются в узлы, а живут в отдельных таблицах с ключом-идентификатором узла. Соблазн сделать иначе велик — добавить в Binary поле resolved_type и заполнять на лету. Почему не стоит: дерево остаётся неизменяемым, а значит разделяемым между потоками и версиями; инкрементальная компиляция (rustc, Roslyn, TypeScript в watch-режиме) строится на возможности выбросить таблицу типов и пересчитать её, не трогая дерево; и не появляется полузаполненных узлов с полем Type | None, которое каждый следующий проход обязан обрабатывать, хотя после проверки типов None там быть не может. Промышленное решение той же задачи — отдельное представление: rustc понижает AST в HIR (dev guide), затем в THIR и MIR, и каждое следующее проще предыдущего; идея «под каждую задачу своё представление» — тема 06.

В IDE у дерева появляется ещё и жизненный цикл: файл правится каждые несколько сотен миллисекунд, поэтому «разобрать заново» означает переиспользовать неизменённые узлы старого дерева. Так работает tree-sitter, на котором держится подсветка в Neovim, GitHub и Zed: правка одной строки не стоит разбора всего файла. Инструментальная сторона — 13.

Память: почему промышленные AST выглядят иначе

На миллионе узлов (примерно 30–50 тысяч строк кода) представление начинает определять скорость компилятора.

Классика — узлы-объекты с указателями на детей — удобна и медленна: узлы разбросаны по куче, каждый спуск к ребёнку кандидат на промах кэша, освобождение дерева стоит обхода. Альтернатива — арена: один массив записей фиксированного размера, где дети адресуются 32-битными индексами.

typedef enum { N_INT, N_NAME, N_BINARY, N_CALL } NodeTag;

typedef struct {
    uint8_t  tag;        // NodeTag, упакованный в один байт
    uint8_t  op;         // код оператора для N_BINARY
    uint32_t lhs, rhs;   // индексы в арене, а не указатели: по 4 байта вместо 8
    uint32_t span_start;
} Node;                  // 16 байт с выравниванием против 40+ у «объектного» варианта

typedef struct { Node *data; uint32_t len, cap; } Arena;   // «указатель» на узел = индекс в data

Плюсы: узлы лежат подряд в порядке создания (то есть примерно в post-order), обход превращается в почти линейное чтение памяти, освобождение всего дерева — один free, индекс вдвое компактнее указателя (цена косвенности и промахов кэша). Минусы: код менее приятный, индекс не типизирован, отладчик показывает числа вместо структур. Так устроены rustc (AST и HIR в аренах), Zig (AST как структура массивов) и Carbon. Для учебного языка и почти любого DSL это преждевременно: начинайте с объектов, переходите к арене, когда профилировщик покажет, что время уходит на обход. Сделать сразу стоит другое — ввести тип NodeId, даже если он пока оборачивает обычную ссылку: на нём потом строятся таблицы атрибутов и инкрементальность.

Типичные ошибки

• Узел без span’а — вылезет через месяц, когда ошибку не к чему будет привязать.
• Универсальный узел с kind: str и children: list — гибко ровно до момента, когда надо понять, что означает children[2] у узла "for".
• Логика в узлах. Binary.evaluate(), Binary.emit_code(), Binary.check_types() — и через полгода класс узла зависит от рантайма, бэкенда и системы типов сразу.
• Мутация дерева проходами: проход A переписал n.left, проход B получил дерево, не соответствующее ни одному исходнику. Рекурсивный обход без предела глубины — на сгенерированном коде это краш.
• AST, повторяющее грамматику. Узлы AdditiveExpression → MultiplicativeExpression → … значат, что вы построили дерево разбора и назвали его AST.
• Смешение синтаксиса и семантики. Тип переменной на этапе AST — строка "Int" из исходника, а не объект типа; превращение одного в другое — работа 05.
• Два представления одной конструкции: если a.b иногда Field(a, "b"), а иногда Binary(".", a, b), каждый проход обязан знать оба варианта.

Где это встречается в реальной работе

AST — единственная фаза компилятора, с которой обычный разработчик работает напрямую, часто не осознавая. Правило ESLint — буквально Visitor: объект, где ключи задают виды узлов ESTree (спецификация), а значения — обработчики:

module.exports = {
  create(context) {
    return {
      BinaryExpression(node) {                    // ключ = вид узла, значение = visit_*
        if (["==", "!="].includes(node.operator) && node.right.name === "NaN") {
          context.report({ node, message: "Используйте Number.isNaN вместо сравнения с NaN" });
        }
      },
    };
  },
};

Babel-плагин — это Transformer из раздела выше, а jscodeshift одним проходом переписывает API во всём монорепозитории (в Python ту же роль играют кодмоды на LibCST). Форматтеры печатают AST обратно в текст — классическая основа тут статья Уодлера «A prettier printer», а пакеты go/ast и go/parser — причина, по которой в экосистеме Go столько кодогенераторов и линтеров. Планировщик запросов переписывает дерево SQL теми же приёмами (проталкивание предикатов, устранение подзапросов) — стык с Индексами и планами запросов. Наконец, термы λ-исчисления — это AST в чистом виде, а подстановка и β-редукция — преобразования дерева (синтаксис термов, подстановка): именно там видно, почему захват переменных — настоящая инженерная проблема.

Тестировать AST удобно снапшотами (напечатали дерево в S-выражения, сравнили с эталоном) и свойством обратимости: parse(print(ast)) должно давать структурно равное дерево — этот тест ловит сразу ошибки парсера, принтера и приоритетов.

Мини-итог

• AST — алгебраический тип: сумма видов узлов, каждый — произведение полей. Проектируйте так, чтобы некорректная программа не выражалась структурой.
• Выбрасывайте всё, что нужно было только парсеру; храните всё, что нужно диагностике, — прежде всего span’ы.
• Обход стоит O(n) времени и O(h) памяти. Post-order — рабочий порядок компилятора: результаты детей готовы к моменту обработки узла. Глубина — реальная угроза, ставьте предел.
• Visitor выносит ветвление по видам узлов в одно место: новые проходы дёшевы, новые виды узлов дороги (expression problem). Где есть match с проверкой полноты, он заменяет Visitor.
• Преобразования строят новое дерево, переиспользуя неизменённые поддеревья и сохраняя span’ы, а результаты анализа живут в таблицах по NodeId, а не в полях узлов.

Источники

• Robert Nystrom, Crafting Interpreters, главы «Representing Code» и «Evaluating Expressions» — craftinginterpreters.com/representing-code.html.
• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, главы 2 и 5; Appel, Modern Compiler Implementation in ML/Java/C — организация проходов.
• Документация ast и файл Python.asdl.
• Eric Lippert, «Roslyn’s Red-Green Trees» и Syntax in rust-analyzer — зачем IDE деревья без потерь.
• Philip Wadler, «The Expression Problem»; rustc dev guide: HIR.

Что дальше

Дерево есть, обходить мы его умеем, оно даже выполняется. Но интерпретатор выше падает с NameError уже во время выполнения — то есть ведёт себя как скриптовый язык, а не как компилятор. Хуже того, он не различает две разные переменные x в разных блоках и не знает, на какое объявление указывает конкретное вхождение имени. Следующий шаг — научить компилятор понимать имена до запуска программы: построить таблицу символов, реализовать области видимости и теневание, связать каждое использование с объявлением и выдавать честную ошибку с позицией.

Семантический анализ: области видимости, таблицы символов, разрешение имён