Компиляторы: карта трека и что происходит между кодом и процессором

Вы пишете let x = 2 + 3 * 4;, нажимаете «запустить» и через долю секунды получаете 14. Между этими двумя событиями лежит одна из самых красивых инженерных конструкций в информатике: программа, которая читает другую программу, понимает её и переписывает на языке, понятном железу — и которой пользуются ежедневно, ни разу не заглянув внутрь.

Заглянуть стоит по трём причинам. Диагностическая: реплики компилятора перестают быть капризами, когда знаешь, какая фаза их произносит — unexpected token это парсер, undefined variable — разрешение имён, type mismatch — проверка типов, а segmentation fault уже рантайм, и компилятор тут ни при чём. Прикладная: планировщик запросов в PostgreSQL, babel, protobuf, движок регулярных выражений, конфиг-парсер, линтер, форматтер, шейдер-компилятор в видеокарте суть компиляторы, просто их так не зовут. Учебная: это лучший из существующих учебных проектов — он трогает автоматы и грамматики, деревья, графы, NP-полноту и лямбда-исчисление не в виде упражнений, а потому что иначе программа просто не заработает. Дальше по треку мы спускаемся в каждую фазу отдельно, а здесь проходим весь путь целиком и в конце собираем работающий мини-компилятор на сотне строк Python.

Что такое компилятор, если говорить точно

Компилятор — это функция из одного представления программы в другое, сохраняющая наблюдаемое поведение. Три слова здесь важны.

Представление. На входе не обязательно текст, на выходе не обязательно машинный код: TypeScript → JavaScript, SQL → план выполнения, Jinja-шаблон → функция рендеринга, регулярное выражение → конечный автомат — всё это компиляторы. Целевой язык может быть даже выше уровнем, чем исходный: суть в переводе, а не в «спуске вниз».

Сохраняющая. Единственное жёсткое требование и источник почти всех сложностей. Компилятор волен переписать x * 2 в x << 1, выбросить неиспользуемую переменную, переставить независимые инструкции — но результат обязан вести себя так, как предписывает семантика языка. Слово «наблюдаемое» — та самая лазейка, которой живут оптимизаторы: если разницу нельзя увидеть изнутри программы, её можно допустить. Отсюда же растёт неопределённое поведение в C: там, где стандарт говорит «не определено», компилятор считает, что этого не случится.

Функция. Настоящий компилятор — конвейер чистых функций: текст → токены → дерево → дерево с типами → IR → машинный код. Каждая стрелка тестируется отдельно, каждое промежуточное представление можно распечатать и посмотреть глазами — отсюда, помимо прочего, честные границы модулей.

Компилятор, интерпретатор, JIT, транспайлер — это спектр

Учебники любят делить языки на «компилируемые» и «интерпретируемые». Это неверно: компилируемость — свойство не языка, а реализации. Для C существуют интерпретаторы (cling), для Python — AOT-компиляторы (Nuitka, mypyc), а CPython делает и то и другое. Разница между стратегиями в том, когда переводим и сколько раз платим за анализ.

Прямой обход AST — не позор, а осознанный выбор: он пишется за вечер и идеален для конфигов, шаблонов и языков правил. JIT существует ради того, чтобы получить старт интерпретатора и скорость AOT, заплатив сложностью (статья 11); см. также «От кода к исполнению».

Конвейер: из чего собран любой компилятор

Канонический конвейер одинаков у учебного компилятора на 500 строк и у LLVM на несколько миллионов: меняется наполнение, не структура.

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

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

Почему фазы именно такие: немного теории

Разделение на лексер и парсер — не вкусовщина, а следствие иерархии Хомского (см. «Автоматы и формальные языки»).

• Идентификаторы, числа, строки — регулярный язык. Их распознаёт конечный автомат: память постоянна, проход один, время линейно. Это лексер (статья 01).
• Вложенные скобки и блоки — контекстно-свободный язык. Конечным автоматом невозможно: чтобы проверить баланс скобок неограниченной глубины, нужна память-стек. Это парсер (статья 02).
• «Переменная объявлена до использования», «типы аргументов совпадают» — вне контекстно-свободного класса. Грамматикой в разумном виде их не выразить, отсюда отдельные фазы семантического анализа и проверки типов (статьи 04 и 05).
• «Функция всегда завершается» — не проверяемо в принципе. Это проблема остановки, отсюда скромность любого статического анализа: он либо консервативен (ругается на корректный код), либо неполон (пропускает ошибки).

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

Отсюда практический вывод: cargo build медленный не из-за парсинга — парсинг это шум. Время съедают проверка заимствований, мономорфизация обобщений (каждая инстанциация даёт новый код), проходы оптимизации и линковка.

Сквозной проект трека: язык Mini

Читать про компиляторы бесполезно — их надо писать. Через весь трек мы ведём один язык, Mini, и на каждом шаге он остаётся работающим: от арифметики до языка с функциями, типами, байткодом и сборщиком мусора. Грамматика первого этапа в форме БНФ — ровно то, что мы реализуем сегодня:

program   := statement*
statement := "let" IDENT "=" expr ";"
           | "print" expr ";"
expr      := term (("+" | "-") term)*
term      := factor (("*" | "/") factor)*
factor    := NUMBER | IDENT | "(" expr ")"

Обратите внимание на форму: expr вызывает term, term вызывает factor. Приоритет операторов закодирован глубиной вложенности правил — чем глубже, тем сильнее связывает; отдельная таблица приоритетов не нужна, грамматика содержит её сама. Дорожная карта трека — каждая статья добавляет Mini одну способность:

Почему AST — центральная структура и при чём тут Visitor

Токены плоские, IR плоский, а между ними — дерево, и почти вся работа компилятора это обходы дерева. Проверка типов, разрешение имён, свёртка констант, генерация кода, форматирование, подсветка — разные операции над одним и тем же набором типов узлов; классический ответ на такую конфигурацию — паттерн Visitor (см. поведенческие паттерны и статью 03).

Компромисс Visitor стоит понимать заранее: он делает дешёвым добавление операций (новый проход — новый класс, узлы не трогаем) и дорогим добавление узлов (новый вид узла — правка всех визиторов). Для компилятора это правильный размен: операций десятки и их число растёт, видов узлов — фиксированный набор из грамматики. В языках с алгебраическими типами и сопоставлением с образцом (Rust, OCaml, Scala) Visitor не нужен: match по конструкторам даёт то же самое, и компилятор ещё проверит, что вы не забыли ветку — паттерн одного языка оказывается синтаксисом другого, о чём и говорит трек парадигм.

Средний слой: почему нельзя переводить дерево прямо в машинный код

Можно — и для учебного компилятора это правильный первый шаг. Но у прямого перевода «дерево → инструкции» жёсткий предел масштабирования: при M языках и N архитектурах бэкендов нужно M × N — добавили язык, пишете N генераторов; добавили процессор, правите M компиляторов.

Промежуточное представление превращает M × N в M + N. Это и есть главная идея LLVM: IR там не деталь реализации, а продукт со стабильным текстовым форматом (LLVM Language Reference), собственным набором инструментов и десятками фронтендов — Clang, Rust, Swift, Julia, Zig.

Вторая причина существования среднего слоя — оптимизации. На AST удобны локальные преобразования (свёртка констант это десяток строк, мы напишем её ниже), но серьёзный анализ требует плоской последовательности простых операций, где явно видны поток управления и поток данных: трёхадресный код (t1 = mul 3, 4), базовые блоки, граф потока управления и SSA — форма, в которой каждая переменная получает значение ровно один раз. SSA превращает вопрос «откуда пришло это значение» из анализа в чтение: у каждого использования ровно одно определение. Статьи 06 и 07.

Рантайм: жизнь программы после компиляции

Компилятор заканчивает работу — программа только начинает. Всё, что дальше, это рантайм, и на него приходится половина трека. Виртуальная машина (статья 09) — интерпретатор байткода; стековые ВМ (JVM, CPython, WebAssembly) компактнее и проще генерируются, регистровые (Lua 5, Dalvik) выполняют меньше инструкций на ту же работу. Сборщик мусора (статья 10) — от подсчёта ссылок до поколенческих и конкурентных сборщиков; здесь теория упирается в иерархию памяти и виртуальную память ОС, потому что современные сборщики оптимизируют не число операций, а локальность и длину пауз. JIT (статья 11) — самая контринтуитивная часть: у него есть то, чего у AOT нет никогда, — знание фактических типов и ветвлений. Он может заинлайнить статически полиморфный вызов, а потом обязан уметь откатиться, если предположение нарушилось; этот откат и называется деоптимизацией.

Практическое следствие: бенчмарк без прогрева на JIT-платформе измеряет не то, что вы думаете. Первые тысячи итераций идут через интерпретатор, потом код перекомпилируется, потом может деоптимизироваться обратно — отсюда JMH в Java. Тот же эффект объясняет, почему функция в Node.js внезапно становится в разы медленнее после аргумента нового типа: сломалась спекуляция, метод откатили в интерпретатор.

Работающий кусок: весь конвейер на сотне строк Python

Теория закончилась. Ниже — компилятор Mini целиком: лексер, парсер, оптимизатор, кодогенератор и ВМ; код запускается как есть.

import re

# ---------- 1. ЛЕКСЕР: текст -> плоский список токенов (вид, текст, позиция) ----------
SPEC = [("NUM", r"\d+"), ("ID", r"[A-Za-z_]\w*"), ("OP", r"[-+*/=();]"), ("WS", r"\s+")]
MASTER = re.compile("|".join(f"(?P<{name}>{pat})" for name, pat in SPEC))
KEYWORDS = {"let", "print"}

def tokenize(src):
    pos, out = 0, []
    while pos < len(src):
        m = MASTER.match(src, pos)             # именно match, а не search: дыр быть не должно
        if m is None:
            raise SyntaxError(f"неизвестный символ {src[pos]!r} на позиции {pos}")
        kind, text, pos = m.lastgroup, m.group(), m.end()
        if kind == "WS":
            continue                           # пробелы до парсера не доходят
        if kind == "ID" and text in KEYWORDS:
            kind = text.upper()                # let/print — ключевые слова, а не имена
        out.append((kind, text, m.start()))
    return out + [("EOF", "", pos)]            # страж: парсеру не нужны проверки границ

Здесь два приёма из статьи 01. Ключевые слова распознаются как идентификаторы, а потом переклассифицируются — иначе letter разберётся как let плюс ter. И каждый токен несёт позицию: без неё не будет ни человеческих сообщений об ошибках, ни отладчика.

# ---------- 2. ПАРСЕР: токены -> AST методом рекурсивного спуска ----------
class Parser:                                      # одна функция на уровень приоритета
    def __init__(self, toks): self.t, self.i = toks, 0
    def peek(self): return self.t[self.i]
    def eat(self, kind, val=None):
        k, v, p = self.t[self.i]
        if k != kind or (val is not None and v != val):
            raise SyntaxError(f"ожидалось {val or kind!r}, встречено {v!r} на позиции {p}")
        self.i += 1
        return v
    def program(self):
        out = []
        while self.peek()[0] != "EOF": out.append(self.stmt())
        return out
    def stmt(self):
        if self.peek()[0] == "LET":
            self.eat("LET"); name = self.eat("ID"); self.eat("OP", "=")
            node = ("let", name, self.expr())
        else:
            self.eat("PRINT"); node = ("print", self.expr())
        self.eat("OP", ";")
        return node
    def expr(self):                                          # приоритет 1: сложение и вычитание
        node = self.term()
        while self.peek()[:2] in (("OP", "+"), ("OP", "-")):
            node = ("bin", self.eat("OP"), node, self.term())     # цикл => левая ассоциативность
        return node
    def term(self):                                          # приоритет 2: умножение и деление
        node = self.factor()
        while self.peek()[:2] in (("OP", "*"), ("OP", "/")):
            node = ("bin", self.eat("OP"), node, self.factor())
        return node
    def factor(self):
        k, v, p = self.peek()
        if k == "NUM": self.eat("NUM"); return ("num", int(v))
        if k == "ID":  self.eat("ID");  return ("var", v)
        if (k, v) == ("OP", "("):
            self.eat("OP", "("); node = self.expr(); self.eat("OP", ")")
            return node                                      # скобки следа в дереве не оставляют
        raise SyntaxError(f"неожиданный токен {v!r} на позиции {p}")

Цикл while внутри expr даёт левую ассоциативность: 1 - 2 - 3 собирается как (1 - 2) - 3. Написали бы рекурсию вместо цикла — получили бы правую, и то же выражение дало бы 2 вместо -4; ловится только тестами.

# ---------- 3. ОПТИМИЗАЦИЯ: свёртка констант прямо на дереве ----------
ARITH = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
         "*": lambda a, b: a * b, "/": lambda a, b: a // b}

def fold(node):                                    # поддерево из одних литералов -> готовое число
    tag = node[0]
    if tag == "bin":
        left, right = fold(node[2]), fold(node[3])
        if left[0] == "num" and right[0] == "num":
            return ("num", ARITH[node[1]](left[1], right[1]))
        return ("bin", node[1], left, right)
    if tag == "let":   return ("let", node[1], fold(node[2]))
    if tag == "print": return ("print", fold(node[1]))
    return node

# ---------- 4. КОДОГЕНЕРАЦИЯ: AST -> байткод стековой машины ----------
def gen_expr(node, code, slots):
    if node[0] == "num": code.append(("PUSH", node[1]))
    elif node[0] == "var":
        if node[1] not in slots:                   # зачаток семантического анализа
            raise NameError(f"переменная {node[1]!r} не объявлена")
        code.append(("LOAD", slots[node[1]]))
    else:                                          # обратная польская запись: сначала операнды
        gen_expr(node[2], code, slots)
        gen_expr(node[3], code, slots)
        code.append(("BIN", node[1]))

def compile_program(stmts):
    code, slots = [], {}                           # slots — примитивная таблица символов
    for s in stmts:
        if s[0] == "let":
            gen_expr(s[2], code, slots)
            slots.setdefault(s[1], len(slots))     # имя -> номер ячейки; имён в рантайме нет
            code.append(("STORE", slots[s[1]]))
        else:
            gen_expr(s[1], code, slots); code.append(("PRINT",))
    return code, slots

# ---------- 5. ВИРТУАЛЬНАЯ МАШИНА: цикл выборки и диспетчеризации ----------
def run(code, nslots):
    stack, mem, ip = [], [0] * nslots, 0
    while ip < len(code):
        op = code[ip]; ip += 1
        if op[0] == "PUSH":    stack.append(op[1])
        elif op[0] == "LOAD":  stack.append(mem[op[1]])
        elif op[0] == "STORE": mem[op[1]] = stack.pop()
        elif op[0] == "BIN":
            b, a = stack.pop(), stack.pop()        # порядок важен: сверху лежит правый операнд
            stack.append(ARITH[op[1]](a, b))
        elif op[0] == "PRINT": print(stack.pop())

SRC = "let x = 2 + 3 * 4; let y = x * (x - 4); print y + 1;"
ast = [fold(s) for s in Parser(tokenize(SRC)).program()]
code, slots = compile_program(ast)
run(code, len(slots))                              # печатает 141

Что здесь стоит увидеть. Приоритет операторов нигде не проверяется явно — он вытекает из того, что term вызывается из expr: разбор 2 + 3 * 4 кладёт умножение глубже в дерево; статья 02 добавит унарные операторы, правую ассоциативность и Pratt-парсинг. Свёртка констант — двенадцать строк, и она уже настоящая: let x = 2 + 3 * 4; компилируется в одну инструкцию PUSH 14; тот же принцип в LLVM работает на IR и с сотней других проходов рядом (статья 07). Имён переменных в скомпилированном коде нет — только номера ячеек; словарь slots это эмбрион таблицы символов, который с появлением вложенных областей и функций превратится в стек областей и фреймы вызовов (статья 04). Стековая ВМ обходится без регистров: BIN не знает, откуда взялись операнды, — поэтому байткод так легко генерировать и переносить. И главное: ошибки возникают на трёх разных фазах — let x = 2 @ 3; ловит лексер, let x = 2 + ; — парсер, print z + 1; — кодогенератор в роли семантического анализа. Сложность конвейера — O(n) по длине исходника.

Где эти навыки применяются на самом деле

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

• Планировщик SQL. Парсер строит дерево запроса, «семантический анализ» разрешает имена таблиц, оптимизатор переписывает дерево по правилам и статистике, исполнитель — та же виртуальная машина. EXPLAIN это дамп IR; см. «Индексы и планы запросов».
• Фронтенд-сборка. Babel, esbuild, SWC — компиляторы с AST-трансформациями; tree shaking это устранение мёртвого кода, минификация — переименование и свёртка. См. «Инструменты сборки».
• ORM, валидаторы схем, регулярные выражения. Построение запроса из выражения на языке-хозяине — типичный встроенный DSL; компиляция шаблона регулярки в NFA и DFA — учебник по лексерам целиком.
• ML-фреймворки. torch.compile, XLA, TVM: граф вычислений это IR, слияние ядер — оптимизирующий проход, генерация CUDA — бэкенд.
• Инфраструктура как код. HCL, конфиги CI, правила алертов — языки с ужасными сообщениями об ошибках именно потому, что их авторы не читали про восстановление после ошибок; статья 12.

Отдельно: чтение чужого IR — сильнейший инструмент оптимизации кода. godbolt.org показывает, во что превратился ваш C++, python -m dis — байткод CPython, go tool compile -S — ассемблер Go; гипотеза «здесь компилятор всё выбросит» проверяется за тридцать секунд вместо часового спора.

Немного истории

Показательна дуга FORTRAN: команда Бэкуса потратила 18 человеко-лет в основном на то, чтобы доказать скептикам, что сгенерированный код не уступает рукописному ассемблеру. Тот же спор повторился с C, с Java, с JIT — и каждый раз заканчивался одинаково.

Типичные ошибки на входе в тему

• «Компилятор — это про ассемблер». Ассемблер — одна фаза из десяти, и в учебном компиляторе её может не быть вовсе: байткод и стековая ВМ дают полноценный работающий язык.
• Пропустить AST и генерировать код прямо из парсера. Работает ровно до первой оптимизации и первой проверки типов. Дерево — точка, где программа впервые становится данными, которые можно анализировать.
• Начинать с генератора парсеров. ANTLR и bison полезны, но пока вы не написали рекурсивный спуск руками, их вывод — магия, а конфликты грамматики — непереводимая брань.
• Оптимизировать до того, как заработало. Компилятор, выдающий правильный медленный код, бесконечно ценнее компилятора, выдающего быстрый неправильный.
• Считать, что типы нужны только для проверок. Типы — источник информации для генерации кода: раскладка структур, размеры полей, статическая диспетчеризация, выбор инструкции. Смотрите типизированное лямбда-исчисление.

Чтобы идти по треку, достаточно уверенно читать код на Python или TypeScript и не бояться рекурсии. Полезно, но не обязательно до начала: структуры данных (рекурсия и деревья), парадигмы программирования и «Как работает процессор».

Источники

• Robert Nystrom, Crafting Interpreters — лучший современный вход в тему, доступен целиком бесплатно: craftinginterpreters.com; два интерпретатора — обход AST и байткодовая ВМ.
• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools («Драконья книга») — канон по теории разбора и анализа потоков данных; Cooper, Torczon, Engineering a Compiler — современнее в части SSA, оптимизаций и распределения регистров; Thorsten Ball, Writing a Compiler in Go (interpreterbook.com) — практика без теории.
• LLVM Kaleidoscope Tutorial — llvm.org/docs/tutorial и LLVM Language Reference — llvm.org/docs/LangRef.html: свой язык поверх промышленной инфраструктуры и то, как выглядит IR, которым пользуются Clang, Rust и Swift.
• PEP 617 — peps.python.org/pep-0617: переход CPython с LL(1) на PEG-парсер; модуль dis — docs.python.org/3/library/dis.html: байткод CPython вживую.
• Блог V8 — v8.dev/blog: как устроены Ignition, Sparkplug и TurboFan, лучший открытый источник про многоуровневый JIT.

Мини-итог

Компилятор — конвейер преобразований представлений программы, сохраняющий её наблюдаемое поведение. Фронтенд отвечает за язык, бэкенд — за машину, средний слой не знает ни того, ни другого и потому переиспользуется всеми: так M × N бэкендов превращаются в M + N. Деление на фазы продиктовано теорией: регулярные языки → лексер, контекстно-свободные → парсер, контекстно-зависимые условия → семантика и типы, неразрешимые вопросы → консервативные приближения. Дерево — структура, вокруг которой живут все проходы; IR — форма, в которой живут оптимизации; рантайм — половина работы. Мини-компилятор из этой статьи уже проходит весь путь: дальше мы его не переписываем, а наращиваем.

Что дальше

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

Лексический анализ: токены, регулярные языки, свой лексер с нуля