Разработка компиляторов: от теории к практике

Этот курс охватывает полный цикл создания компилятора, начиная с лексического анализа и заканчивая генерацией машинного кода. Вы изучите ключевые алгоритмы и структуры данных, необходимые для трансляции языков программирования в исполняемые файлы.

1. Введение в архитектуру компилятора и лексический анализ

Введение в архитектуру компилятора и лексический анализ

Добро пожаловать в курс «Разработка компиляторов: от теории к практике». Многие программисты воспринимают компилятор как «черный ящик»: вы подаете на вход исходный код, а на выходе получаете работающую программу. В этом курсе мы откроем крышку этого ящика и разберем, как именно текст превращается в инструкции процессора.

В первой статье мы рассмотрим общую архитектуру компилятора и детально изучим его первый этап — лексический анализ.

Что такое компилятор?

Компилятор — это программа, которая переводит текст, написанный на одном языке (исходный язык), в эквивалентный текст на другом языке (целевой язык). Чаще всего мы переводим языки высокого уровня (C++, Rust, Java) в машинный код или байт-код.

Важно отличать компиляторы от интерпретаторов. Компилятор переводит программу целиком до ее запуска, создавая исполняемый файл. Интерпретатор же читает и выполняет код построчно во время работы программы.

Архитектура компилятора: вид с высоты птичьего полета

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

  • Front-end (Анализ): Понимает, что написал программист. Проверяет синтаксис и семантику, строит промежуточное представление.
  • Back-end (Синтез): Оптимизирует код и генерирует инструкции для конкретной машины (x86, ARM и т.д.).

    • !Последовательность фаз работы классического компилятора

    Основные этапы Front-end'а:

    * Лексический анализ (Сканирование): Разбивает текст на слова (токены). * Синтаксический анализ (Парсинг): Строит дерево структуры программы (AST). * Семантический анализ: Проверяет смысл (типы данных, области видимости).

    Сегодня мы сосредоточимся на самом первом этапе.

    Лексический анализ (Scanning)

    Задача лексического анализатора (лексера) — прочитать поток символов исходного кода и сгруппировать их в осмысленные последовательности, называемые лексемами. Для каждой лексемы лексер создает объект — токен.

    Представьте, что вы читаете предложение на иностранном языке. Прежде чем понять смысл, вы сначала выделяете отдельные слова и знаки препинания. Лексер делает то же самое.

    Рассмотрим пример кода:

    Для компьютера это просто массив символов: ['x', ' ', '=', ' ', '1', '0', ' ', '+', ' ', '2']. Лексер преобразует это в поток токенов:

  • IDENTIFIER (значение: "x")
  • ASSIGN (значение: "=")
  • NUMBER (значение: "10")
  • PLUS (значение: "+")
  • NUMBER (значение: "2")

    • Обратите внимание: пробелы были проигнорированы, так как в данном контексте они не несут смысла.

    Структура токена

    Токен обычно представляет собой пару:

    Где: * — тип токена (например, число, идентификатор, ключевое слово if). * — (опционально) конкретное значение лексемы (например, само число 42 или имя переменной counter).

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

    Теоретическая база: Регулярные выражения

    Как объяснить компьютеру, что такое «число» или «идентификатор»? Для этого используется математический аппарат регулярных выражений.

    Регулярные выражения описывают множества строк (языки). Например, идентификатор в C-подобных языках можно описать так: «буква или подчеркивание, за которыми следует ноль или более букв, цифр или подчеркиваний».

    В математической нотации это выглядит так:

    Где: * — регулярное выражение для идентификатора. * — множество букв (Letters) . * — множество цифр (Digits) . * — операция объединения (или). * — операция конкатенации (следование друг за другом). — замыкание Клини (повторение 0 или более раз).

    Реализация: Конечные автоматы

    Чтобы превратить регулярное выражение в работающий код, мы используем Конечные Автоматы (Finite Automata). Это абстрактная машина, которая может находиться в одном из конечного числа состояний.

    Формально детерминированный конечный автомат (DFA) определяется как пятерка:

    Где: * — конечное множество состояний. * — входной алфавит (символы, которые мы читаем). * — функция переходов , которая говорит: «если мы в состоянии и видим символ , переходим в состояние ». * — начальное состояние (). * — множество допускающих (финальных) состояний ().

    !Граф переходов автомата, распознающего последовательность цифр

    Как это работает на практике?

    Лексер работает как «жадный» автомат. Он пытается считать максимально длинную последовательность символов, которая подходит под одно из правил.

    Простой алгоритм работы лексера:

  • Начинаем с первого символа.
  • Движемся по состояниям автомата, считывая символы.
  • Если мы пришли в тупик (нет перехода по текущему символу):
    • * Если мы находимся в финальном состоянии, токен найден. Возвращаем его и откатываем указатель чтения, если нужно. * Если мы не в финальном состоянии — это лексическая ошибка (например, символ @ в языке C).

    Пример простого лексера на Python

    Давайте напишем примитивный лексер, который понимает только числа и знаки плюс/минус.

    Этот код реализует логику конечного автомата вручную, используя условия if и циклы while. В промышленных компиляторах часто используют генераторы лексеров (например, Lex или Flex), которые сами строят таблицы переходов на основе регулярных выражений.

    Обработка ошибок

    Лексический анализ — это первый рубеж обороны. Ошибки здесь бывают простыми: «недопустимый символ» или «незакрытая строковая константа».

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

    Заключение

    Мы разобрали первый кирпичик в фундаменте компилятора. Лексический анализ преобразует хаос символов в порядок токенов, упрощая жизнь следующим этапам.

    В следующей статье мы перейдем к синтаксическому анализу: узнаем, как из плоского списка токенов построить иерархическое дерево, отражающее логику вашей программы.

    2. Синтаксический анализ: контекстно-свободные грамматики и построение AST

    Синтаксический анализ: контекстно-свободные грамматики и построение AST

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

    Сегодня мы займемся синтаксическим анализом (парсингом). Это этап, на котором компилятор перестает видеть код как строку и начинает видеть его как дерево.

    Зачем нам нужна грамматика?

    Представьте, что у вас есть список токенов: ID(x), ASSIGN(=), NUMBER(5), PLUS(+), NUMBER(3), SEMICOLON(;).

    Лексический анализатор (лексер) свою работу сделал: он распознал слова. Но он не знает, правильно ли они расставлены. Например, последовательность 5 + = x для лексера вполне валидна (это просто 4 токена), но бессмысленна с точки зрения логики языка.

    Синтаксический анализатор (парсер) решает две задачи:

  • Валидация: Проверяет, соответствует ли последовательность токенов правилам языка.
  • Построение структуры: Преобразует линейный поток токенов в дерево.

    • Почему мы не можем использовать регулярные выражения, как в лексере? Потому что регулярные выражения не умеют «считать» и работать с вложенностью. Они не могут гарантировать, что на каждую открывающую скобку найдется закрывающая, если вложенность скобок произвольная. Для описания синтаксиса нам нужен более мощный инструмент.

    Контекстно-свободные грамматики (КСГ)

    Для описания синтаксиса языков программирования чаще всего используются Контекстно-свободные грамматики (Context-Free Grammars, CFG). Это набор правил, описывающих, как из простых элементов строить сложные.

    Формально КСГ определяется как четверка:

    Где: * — множество нетерминалов. Это абстрактные символы, обозначающие синтаксические конструкции (например, «Выражение», «Инструкция», «Цикл»). * — множество терминалов. Это символы, которые реально встречаются в тексте программы, то есть наши токены (например, if, +, id). * — множество правил вывода (продукций). Каждое правило говорит, как нетерминал можно заменить на последовательность терминалов и других нетерминалов. * — стартовый символ (). Самый главный нетерминал, с которого начинается разбор всей программы.

    Пример грамматики

    Давайте опишем простейшую грамматику для арифметических выражений (сложение и умножение чисел).

    Пусть: * *

    Правила могут выглядеть так:

  • (Выражение — это выражение плюс слагаемое)
  • (Или просто слагаемое)
  • (Слагаемое — это слагаемое умножить на множитель)
  • (Или просто множитель)
  • (Множитель — это выражение в скобках)
  • (Или просто число)

    • Эта грамматика позволяет нам порождать (генерировать) строки. Например, чтобы получить 1 + 2 * 3, мы начинаем с и последовательно применяем правила.

    Деревья: CST и AST

    Результатом работы парсера является дерево. Но деревья бывают разные.

    Дерево конкретного синтаксиса (CST)

    CST (Concrete Syntax Tree), или дерево разбора, отражает точный процесс применения правил грамматики. Оно содержит абсолютно все токены, включая скобки, запятые и ключевые слова.

    Если мы построим CST для выражения 1 + 2, оно будет очень громоздким, с множеством промежуточных узлов (, , ), даже если они не несут смысловой нагрузки для вычислений.

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

    AST (Abstract Syntax Tree) — это то, ради чего мы всё это затеяли. Это сжатая, очищенная версия дерева, содержащая только суть операции.

    В AST для выражения (1 + 2): * Не будет узлов для скобок (структура дерева сама задает приоритет). * Не будет лишних переходов типа , если они не меняют смысл.

    [VISUALIZATION: Слева изображено сложное дерево CST для выражения

    3. Семантический анализ, проверка типов и таблицы символов

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

    Поздравляю! Если вы читаете эту статью, значит, ваш компилятор уже умеет читать исходный код (лексический анализ) и понимать его структуру (синтаксический анализ). У нас есть Абстрактное Синтаксическое Дерево (AST), которое красиво отражает вложенность операций.

    Но есть одна проблема: синтаксическая корректность не гарантирует, что программа имеет смысл.

    Рассмотрим знаменитый пример лингвиста Ноама Хомского: «Бесцветные зеленые идеи яростно спят». С точки зрения грамматики английского (и русского) языка это предложение безупречно: прилагательные стоят перед существительным, наречие перед глаголом. Но смысла в нем нет. Зеленое не может быть бесцветным, а идеи не могут спать.

    В программировании происходит то же самое. Выражение "hello" / 5 синтаксически верно (строка, оператор деления, число), но семантически абсурдно. Именно здесь в игру вступает семантический анализ.

    Задачи семантического анализа

    Семантический анализатор — это «полиция смысла» вашего компилятора. Он проходит по AST и проверяет правила, которые невозможно описать контекстно-свободной грамматикой.

    Основные задачи этого этапа:

  • Разрешение имен (Name Resolution): Связывание использования переменной с её объявлением.
  • Проверка типов (Type Checking): Убедиться, что операции выполняются над совместимыми типами данных.
  • Проверка областей видимости (Scope Checking): Убедиться, что переменная видна в том месте, где к ней обращаются.

    • Для решения этих задач нам потребуется главный инструмент семантического анализа — Таблица символов.

    Таблица символов (Symbol Table)

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

    !Визуализация связи исходного кода и структуры таблицы символов

    Что мы храним в таблице?

    Для каждой переменной нам обычно нужно знать:

    * Имя: Как программист назвал переменную. * Тип: Целое число, строка, массив и т.д. * Категория: Это переменная, константа, функция или тип? * Область видимости: Где эта переменная доступна. * Адрес/Смещение: Где она будет лежать в памяти (это пригодится позже, при генерации кода).

    Управление областями видимости (Scopes)

    В большинстве языков (C++, Java, Rust, Python) существуют вложенные области видимости. Переменная, объявленная внутри функции, не должна быть видна снаружи. Более того, локальная переменная может «затенять» (shadow) глобальную с тем же именем.

    Чтобы реализовать это, таблицу символов часто организуют как стек таблиц или дерево таблиц.

    Алгоритм работы с областями видимости:

  • При входе в новый блок (например, начало функции или цикл for) мы создаем новую пустую таблицу символов и помещаем её на вершину стека.
  • При объявлении переменной мы записываем её в таблицу на вершине стека.
  • При использовании переменной мы ищем её сначала в таблице на вершине. Если не нашли — спускаемся на уровень ниже, и так до глобальной области.
  • При выходе из блока мы удаляем верхнюю таблицу со стека.

    • Проверка типов (Type Checking)

    Это сердце семантического анализа. Система типов — это набор правил, которые приписывают типам (int, float, string) определенные свойства и определяют допустимые операции.

    Статическая и динамическая типизация

    * Статическая типизация (C++, Java, Go): Типы проверяются во время компиляции. Если вы попытаетесь сложить число и строку, компилятор выдаст ошибку и не создаст исполняемый файл. * Динамическая типизация (Python, JavaScript): Типы проверяются во время выполнения. Компилятор (или интерпретатор) пропустит ошибку, и программа упадет только тогда, когда дойдет до проблемной строки.

    В нашем курсе мы ориентируемся на создание компилятора со статической типизацией, так как это сложнее и интереснее с точки зрения разработки.

    Формализация правил типов

    В теории компиляторов правила типов часто записывают с помощью правил вывода. Давайте рассмотрим правило для сложения двух выражений.

    Где: * (Гамма) — это контекст (наша таблица символов). * — символ, означающий «выводимо» или «доказуемо». * — выражения (например, переменная a или число 5). * — означает «имеет тип integer». * Черта разделяет предпосылки (сверху) и заключение (снизу).

    Это правило читается так: «Если в контексте выражение имеет тип int И выражение имеет тип int, ТО выражение тоже имеет тип int».

    Если же у нас — это строка, а — число, то ни одно правило не сработает, и компилятор должен выбросить ошибку Type Mismatch.

    Реализация: Паттерн Visitor

    Как это реализовать в коде? У нас есть дерево AST. Нам нужно обойти его узлы и для каждого узла вычислить его тип.

    Идеальный паттерн проектирования для этого — Visitor (Посетитель). Мы создаем класс TypeChecker, который умеет «посещать» каждый тип узла AST.

    Пример логики на псевдокоде:

    Атрибутные грамматики

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

    Атрибуты бывают двух видов:

  • Синтезируемые (Synthesized): Значение вычисляется на основе дочерних узлов и передается вверх. Пример: тип выражения E вычисляется на основе типов его слагаемых E1 и E2.
  • Наследуемые (Inherited): Значение передается от родителя к детям. Пример: информация о том, находимся ли мы внутри цикла (чтобы разрешить оператор break), передается сверху вниз.

    • Где: * — родительский узел. * — дочерний узел. * — значение атрибута. * — функция вычисления. * — синтезируемый атрибут дочернего узла.

    Типичные ошибки семантики

    Ваш семантический анализатор должен уметь ловить следующие ситуации:

    * Undeclared Variable: Использование переменной x, которую забыли объявить. * Redeclaration: Попытка объявить int x дважды в одной функции. * Type Mismatch: Попытка присвоить строку в целочисленную переменную: int x = "text";. * Argument Count Mismatch: Вызов функции sum(a, b) с тремя аргументами. * Return Type Error: Функция заявлена как void, но пытается вернуть 5.

    Заключение

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

    Теперь у нас есть полностью проверенное, аннотированное типами дерево AST. Мы готовы к следующему большому шагу — генерации промежуточного кода (IR) и оптимизациям, о чем мы поговорим в следующей статье.

    4. Генерация промежуточного кода и базовые методы оптимизации

    Генерация промежуточного кода и базовые методы оптимизации

    Мы прошли долгий путь. Наш компилятор уже умеет читать текст (лексический анализ), понимать структуру (синтаксический анализ) и проверять смысл (семантический анализ). На выходе предыдущего этапа мы получили проверенное, аннотированное типами Абстрактное Синтаксическое Дерево (AST).

    Казалось бы, пора генерировать машинный код (ассемблер) и заканчивать работу? Не совсем. Прыжок от AST сразу к машинному коду слишком велик и неудобен. Вместо этого современные компиляторы делают промежуточный шаг — переводят программу в Промежуточное Представление (Intermediate Representation, IR).

    В этой статье мы разберем, что такое IR, как превратить дерево в линейный код и как сделать этот код быстрее еще до того, как он коснется процессора.

    Зачем нужен промежуточный код?

    Представьте, что вы хотите написать компиляторы для 5 разных языков программирования (C++, Java, Python, Rust, Go) под 3 разные архитектуры процессоров (x86, ARM, RISC-V).

    Если писать полный компилятор от начала до конца для каждой пары «язык-процессор», вам придется написать компиляторов. Это называется проблемой .

    Использование IR решает эту проблему. Front-end (анализатор) переводит исходный язык в общий IR. Back-end (генератор) переводит IR в машинный код.

    Где: * — количество исходных языков. * — количество целевых архитектур.

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

    Трехадресный код (Three-Address Code)

    Существует много видов IR, но самым популярным является Трехадресный код (3AC). Он называется так, потому что каждая инструкция в нем содержит не более трех операндов (адресов).

    Общий вид инструкции:

    Где: * — переменная, куда записывается результат. * — бинарная операция (плюс, минус, умножить и т.д.). * — операнды (переменные или константы).

    Это очень похоже на ассемблер, но с одним важным отличием: мы можем использовать бесконечное количество временных переменных (виртуальных регистров).

    Пример преобразования

    Рассмотрим выражение на языке высокого уровня:

    В AST это дерево. В трехадресном коде мы должны разбить это на элементарные операции, вводя временные переменные ():

  • t1 = c * d (Сначала умножение)
  • t2 = b + t1 (Затем сложение)
  • t3 = t2 - e (Затем вычитание)
  • a = t3 (Присваивание результата)

    • !Схема преобразования дерева AST в линейный трехадресный код

    Генерация IR из AST

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

    Рассмотрим упрощенный алгоритм на псевдокоде:

    Этот простой рекурсивный алгоритм «выпрямляет» дерево в список инструкций.

    Базовые блоки и Граф потока управления (CFG)

    Линейный список инструкций неудобен для анализа. В нем есть условные переходы (goto, if), которые нарушают последовательность выполнения. Чтобы навести порядок, код разбивают на Базовые блоки (Basic Blocks).

    Базовый блок — это последовательность инструкций, которая:

  • Имеет только одну точку входа (первая инструкция).
  • Имеет только одну точку выхода (последняя инструкция).
  • Выполняется всегда целиком: если выполнилась первая команда, то гарантированно выполнятся и все остальные до конца блока.

    • Блоки соединяются друг с другом дугами переходов, образуя Граф потока управления (Control Flow Graph, CFG).

    !Граф потока управления, состоящий из базовых блоков

    Независимые от машины оптимизации

    Теперь, когда у нас есть IR (и, возможно, CFG), мы можем попытаться улучшить код. Главная цель оптимизации — сделать программу быстрее или меньше, не изменив её поведение.

    Рассмотрим самые базовые методы, которые применяются почти во всех компиляторах.

    1. Свертка констант (Constant Folding)

    Если операнды инструкции известны во время компиляции, мы можем вычислить результат сразу, не заставляя процессор делать это во время выполнения.

    До:

    После:

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

    2. Распространение констант (Constant Propagation)

    Если мы знаем, что переменная x имеет значение 5, мы можем заменить все использования x на 5 в пределах области видимости, пока x не изменится.

    До:

    После:

    3. Удаление мертвого кода (Dead Code Elimination)

    Мертвый код — это инструкции, которые вычисляют значения, но эти значения нигде потом не используются, или код, который никогда не будет выполнен (например, после return).

    Пример 1 (Неиспользуемая переменная):

    Оптимизатор удалит первую строку.

    Пример 2 (Недостижимый код):

    Оптимизатор удалит вторую строку.

    4. Удаление общих подвыражений (Common Subexpression Elimination)

    Если одно и то же выражение вычисляется несколько раз и переменные, входящие в него, не менялись, нет смысла считать его заново.

    До:

    После:

    Алгебраические упрощения

    Это частный случай оптимизаций, основанный на математических свойствах операций.

    Примеры: * (Сложение с нулем) * (Умножение на единицу) * (Умножение на ноль) * (Замена умножения на сдвиг, что часто быстрее)

    Где: * — означает «заменяется на». * — операция побитового сдвига влево.

    Заключение

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

    В следующей, заключительной части курса, мы рассмотрим Back-end: распределение регистров и генерацию финального машинного кода для реального процессора.

    5. Генерация целевого машинного кода и управление памятью

    Генерация целевого машинного кода и управление памятью

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

    В этой статье мы рассмотрим Back-end компилятора: как превратить виртуальные инструкции в реальные, как распределить ограниченное количество регистров процессора и как организовать память во время выполнения программы.

    От IR к машинному коду

    Главная проблема этого этапа — семантический разрыв. Промежуточное представление (IR) обычно предполагает наличие бесконечного количества виртуальных регистров и идеализированную модель памяти. Реальный процессор (например, x86-64 или ARM) имеет:

  • Ограниченный набор регистров (например, 16 регистров общего назначения в x86-64).
  • Специфические инструкции (некоторые операции могут требовать, чтобы операнды лежали в конкретных регистрах).
  • Сложные режимы адресации памяти.

    • Процесс генерации кода можно разделить на три ключевые подзадачи:

  • Выбор инструкций (Instruction Selection): Сопоставление операций IR с инструкциями целевого процессора.
  • Распределение регистров (Register Allocation): Отображение бесконечного множества переменных IR на конечное множество физических регистров.
  • Планирование инструкций (Instruction Scheduling): Перестановка команд для эффективного использования конвейера процессора (мы коснемся этого лишь вскользь).

    • Выбор инструкций

    Представьте, что в вашем IR есть инструкция x = y + z. На процессоре x86 это может быть реализовано по-разному, в зависимости от того, где находятся данные.

    Если y и z уже в регистрах, это простая команда ADD. Если они в памяти, нам, возможно, придется сначала загрузить их (MOV). А если мы хотим обнулить регистр, то вместо MOV EAX, 0 эффективнее использовать XOR EAX, EAX, так как эта инструкция короче и быстрее.

    Современные компиляторы используют методы сопоставления с образцом (pattern matching) на деревьях или графах, чтобы покрыть IR минимальным количеством машинных инструкций.

    Распределение регистров: Граф несовместимости

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

    Но что делать, если переменных 100, а регистров всего 16? Нам нужно определить, какие переменные «живут» одновременно.

    Анализ живости переменных (Liveness Analysis)

    Переменная считается живой (live) на определенном участке кода, если она содержит значение, которое может быть прочитано в будущем.

    Для формализации этого используется уравнение потока данных. Пусть — это инструкция в программе.

    Где: — множество переменных, живых перед* выполнением инструкции . — множество переменных, которые читаются* (используются) в инструкции . * — операция объединения множеств. — множество переменных, живых сразу после* инструкции (обычно это следующих инструкций). — множество переменных, которые перезаписываются* (определяются) в инструкции .

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

    Раскраска графа

    Зная интервалы жизни всех переменных, мы строим Граф несовместимости (Interference Graph).

    * Вершины графа: переменные программы. Ребра: соединяют две переменные, если они живы одновременно*.

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

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

    !Визуализация задачи раскраски графа для распределения регистров

    Spilling (Сброс в память)

    Что делать, если граф требует 20 цветов, а у нас всего 16 регистров? Мы вынуждены выбрать наименее важные переменные и «вылить» (spill) их в оперативную память (обычно в стек).

    Компилятор вставляет инструкции STORE для сохранения значения в стек и LOAD для его восстановления перед использованием. Это замедляет программу, поэтому минимизация спиллинга — критически важная задача.

    Управление памятью: Runtime Environment

    Сгенерированный код не висит в вакууме. Ему нужна среда выполнения. Память процесса обычно делится на несколько сегментов:

  • Code (Text): Сами машинные инструкции (обычно только для чтения).
  • Static Data: Глобальные переменные и константы.
  • Stack (Стек): Локальные переменные, параметры функций и адреса возврата.
  • Heap (Куча): Динамически выделяемая память (через new или malloc).

    • Организация стека и кадры активации

    Каждый вызов функции создает на стеке новый блок данных, называемый кадром активации (Stack Frame) или записью активации.

    Типичный кадр стека содержит: * Аргументы функции (если они не поместились в регистры). * Адрес возврата (куда прыгнуть после return). * Сохраненный указатель на предыдущий кадр (Frame Pointer). * Локальные переменные функции. * Временные переменные (для спиллинга).

    Управление стеком осуществляется через два специальных регистра: * SP (Stack Pointer): Указывает на вершину стека (конец текущего кадра). * BP (Base Pointer / Frame Pointer): Указывает на начало текущего кадра. Локальные переменные адресуются как смещение относительно BP (например, [BP - 4], [BP - 8]).

    !Структура памяти процесса и устройство стекового кадра

    Соглашения о вызовах (Calling Conventions)

    Чтобы функции могли вызывать друг друга (даже если они написаны на разных языках), существует строгий контракт — Calling Convention. Он определяет:

    * Как передаются параметры (через регистры или через стек?). * Кто очищает стек после вызова (вызывающий или вызываемая функция?). * Какие регистры функция обязана сохранить (Callee-saved), а какие может менять без спроса (Caller-saved).

    Например, в популярном соглашении System V AMD64 ABI (используется в Linux) первые 6 целочисленных аргументов передаются через регистры RDI, RSI, RDX, RCX, R8, R9, а остальные — через стек.

    Генерация выходного файла

    После того как мы выбрали инструкции и распределили регистры, у нас есть список ассемблерных команд. Остался последний шаг — записать их в файл.

    Здесь есть два пути:

  • Генерация текста ассемблера (.s): Компилятор пишет текстовый файл (например, MOV EAX, 5), а затем вызывает внешний ассемблер (например, NASM или GAS) для создания бинарного файла.
  • Генерация объектного кода напрямую: Компилятор сам формирует бинарные инструкции и записывает их в формате объектного файла (ELF для Linux, PE для Windows, Mach-O для macOS).

    • Второй путь сложнее, но позволяет компилировать быстрее, так как пропускается этап парсинга текста ассемблера.

    Заключение курса

    Мы прошли полный путь разработки компилятора:

  • Лексический анализ: Текст Токены.
  • Синтаксический анализ: Токены AST.
  • Семантический анализ: Проверка типов и смысла.
  • IR и Оптимизация: Упрощение и ускорение кода.
  • Генерация кода: AST/IR Машинный код.

    • Создание компилятора — это вершина системного программирования. Оно объединяет теорию алгоритмов, архитектуру компьютеров и инженерию ПО. Теперь, когда вы понимаете, что происходит внутри «черного ящика», вы станете писать более эффективный код, лучше понимать ошибки компиляции и, возможно, однажды создадите свой собственный язык программирования.

    Спасибо за внимание к курсу!