Промежуточное представление и байткод

Между деревом и машиной лежит промежуточный язык — компактные инструкции, которые легко исполнять.

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

Можно было бы вычислять выражение прямо обходом AST (как мы делали). Но реальные системы сначала переводят дерево в линейный список инструкций — байткод. Это удобнее хранить, оптимизировать и исполнять повторно.

Стековый байткод

Самый распространённый вид байткода — стековый. Инструкции работают с воображаемым стеком: PUSH n кладёт число, ADD снимает два верхних и кладёт их сумму. Так устроены байткоды Python и Java.

Для выражения 2 + 3 * 4 байткод выглядит так.

PUSH 2
PUSH 3
PUSH 4
MUL        ; снять 4 и 3, положить 12
ADD        ; снять 12 и 2, положить 14

Генерация байткода из AST

Генератор — это снова обход дерева. Для числа выдаём PUSH, для бинарной операции — сперва код левого поддерева, потом правого, потом саму операцию. Порядок «дети раньше операции» гарантирует, что к моменту операции операнды уже на стеке.

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

OPCODE = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}

def compile_node(node, out):
    if isinstance(node, Num):
        out.append(("PUSH", node.value))
    else:
        compile_node(node.left, out)
        compile_node(node.right, out)
        out.append((OPCODE[node.op],))

tree = BinOp("+", Num(2), BinOp("*", Num(3), Num(4)))
code = []
compile_node(tree, code)
for instr in code:
    print(instr)

Вывод:

('PUSH', 2)
('PUSH', 3)
('PUSH', 4)
('MUL',)
('ADD',)

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

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

Линейный байткод удобнее AST для исполнения: не нужно прыгать по дереву, инструкции идут подряд, как лента. Виртуальная машина просто читает их по порядку.

Зачем вообще IR

Главное преимущество — развязка языков и платформ. Один генератор IR работает для любого front-end, а оптимизации и кодогенераторы пишутся один раз поверх IR. Именно так устроен LLVM: десятки языков компилируются в единый LLVM IR, а дальше общий back-end генерирует код под любой процессор.

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

Первая — перепутать порядок операндов для некоммутативных операций. Для 10 - 3 нужно класть сначала 10, потом 3; SUB вычитает верхний из нижнего. Перепутаете — получите 3 - 10.

Вторая — думать, что байткод обязательно стековый. Бывают регистровые байткоды (как в Lua или Dalvik), где инструкции адресуют «регистры». Стековый просто проще для учебных целей.

Итог

IR — представление между AST и машинным кодом, удобное для исполнения и оптимизации.
Стековый байткод работает с воображаемым стеком: PUSH, ADD и т. п.
Генерация — обход дерева в постфиксном порядке (дети раньше операции).
IR развязывает языки и платформы, поэтому его используют LLVM, JVM, Python.