Абстрактное синтаксическое дерево

Парсер должен не просто проверить синтаксис, а построить дерево, отражающее структуру выражения, — AST.

Абстрактное синтаксическое дерево (AST) — древовидное представление программы, где узлы — операции и значения, а несущественные детали синтаксиса опущены.

В прошлом уроке парсер лишь проверял корректность. Но чтобы вычислить или скомпилировать выражение, нужна его структура в удобной форме. Эта форма — AST.

AST против дерева разбора

Дерево разбора (parse tree) дословно повторяет грамматику: в нём есть узлы expr, term, factor, даже когда они ничего не добавляют. AST — «очищенная» версия: оно хранит только суть. Скобки, например, в AST исчезают — их роль уже выполнена формой дерева.

Выражение: 2 + 3 * 4

ДЕРЕВО РАЗБОРА            AST
   expr                   (+)
   /  \                   /  \
 term  +  term          2    (*)
  |       / \                / \
fact   fact fact          3    4
  |     |    |
  2     3    4

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

Представление узлов классами

В Python узлы AST удобно описать классами. Для калькулятора хватит двух типов: число и бинарная операция.

class Num:
    def __init__(self, value):
        self.value = value
    def __repr__(self):
        return str(self.value)

class BinOp:
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right
    def __repr__(self):
        return "(" + repr(self.left) + " " + self.op + " " + repr(self.right) + ")"

# построим вручную AST для 2 + 3 * 4
tree = BinOp("+", Num(2), BinOp("*", Num(3), Num(4)))
print(tree)

Вывод:

(2 + (3 * 4))

Видно, что умножение лежит глубже сложения — приоритет зашит в структуру дерева. Скобки в выводе появились лишь для наглядности, в самом дереве их нет как узлов.

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

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

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

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

Вторая — путать op как строку и как тип узла. Удобнее, когда тип операции — это либо строковое поле ("+"), либо отдельный класс узла на операцию. Смешивать оба подхода в одном дереве — источник багов.

Итог

AST хранит структуру программы, отбрасывая несущественный синтаксис.
Дерево разбора дословно повторяет грамматику, AST — его очищенная версия.
Узлы удобно описывать классами (Num, BinOp).
Приоритет операторов зашит в форму дерева: что глубже, то вычисляется раньше.