Деревья разбора и вывод

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

Дерево разбора (parse tree) — дерево, листья которого читаются как выводимая строка, а внутренние узлы — нетерминалы, раскрытые по правилам грамматики.

От вывода к дереву

Один и тот же вывод можно записывать по-разному (раскрывать нетерминалы в разном порядке), но структуру вывода удобнее показывать деревом. Корень — стартовый символ S. Каждый внутренний узел — нетерминал, а его дети — символы правой части применённого правила (слева направо). Листья — терминалы; прочитанные слева направо, они дают исходную строку. Дерево абстрагируется от порядка подстановок: важно какие правила применены и к чему, а не в каком порядке.

Грамматика: E → E + E | num
Строка: num + num + num

          E
        / | \
       E  +  E
      /|\    |
     E + E  num
     |   |
   num  num

Листья слева направо: num + num + num ✓

Левый и правый вывод

Левый вывод на каждом шаге раскрывает самый левый нетерминал, правый — самый правый. Оба соответствуют одному и тому же дереву, если грамматика однозначна. Парсеры выбирают стратегию: LL-парсеры строят левый вывод сверху вниз, LR-парсеры — правый вывод снизу вверх (в обратном порядке). Дерево разбора — общий результат, к которому они приходят разными путями.

Строим и обходим дерево разбора

Распарсим простое выражение и построим дерево как вложенные кортежи, затем вычислим его значение обходом. Грамматика: выражение — сумма чисел.

tokens = "3 + 4 + 5".split()

# строим дерево разбора для E -> E + num | num (левоассоциативно)
def parse(tokens):
    tree = ("num", tokens[0])
    i = 1
    while i < len(tokens):
        op, num = tokens[i], tokens[i+1]
        tree = ("+", tree, ("num", num))  # вложение влево
        i += 2
    return tree

def show(node, depth=0):
    pad = "  " * depth
    if node[0] == "num":
        print(pad + "num " + node[1])
    else:
        print(pad + "(+)")
        show(node[1], depth+1)
        show(node[2], depth+1)

def value(node):
    if node[0] == "num":
        return int(node[1])
    return value(node[1]) + value(node[2])

tree = parse(tokens)
show(tree)
print("значение =", value(tree))

Вывод:

(+)
  (+)
    num 3
    num 4
  num 5
значение = 12

Дерево захватило структуру «((3+4)+5)» — левоассоциативную. Обход дерева снизу вверх даёт значение выражения: ровно так компилятор вычисляет или генерирует код по синтаксическому дереву.

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

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

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

Путать дерево разбора и порядок вывода. Разные порядки подстановок (левый/правый вывод) дают одно дерево в однозначной грамматике. Дерево — инвариант.

Игнорировать ассоциативность. Форма дерева задаёт, как группируются операции; «3-4-5» при левой и правой ассоциативности даёт разные значения.

Считать AST и parse tree одним и тем же. Parse tree повторяет грамматику дословно; AST — упрощённая, очищенная версия для семантики.

Итог

• Дерево разбора показывает структуру вывода: корень — S, внутренние узлы — нетерминалы, листья — выводимая строка.
• Левый и правый вывод раскрывают крайний левый/правый нетерминал; в однозначной грамматике дают одно дерево.
• Обход дерева задаёт семантику: вычисление выражения, генерацию кода; форма дерева кодирует приоритет и ассоциативность.
• AST — упрощённое дерево разбора, очищенное для нужд интерпретатора/компилятора.