Основы разработки компиляторов: от теории к практике

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

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

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

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

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

Существует важное отличие между компиляторами и интерпретаторами:

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

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

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

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

Front-end (Анализ): Понимает, что написал программист. Проверяет синтаксис, семантику и строит внутреннее представление кода.

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

!Этапы работы классического компилятора

Давайте кратко пройдемся по основным этапам, чтобы понимать контекст:

Лексический анализ (Сканирование): Разбивает текст на слова (токены).

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

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

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

Оптимизация: Улучшает код (удаляет лишнее, ускоряет циклы).

Генерация целевого кода: Превращает IR в инструкции процессора.

Сегодня мы фокусируемся на первом шаге — лексическом анализе.

Лексический анализ: от текста к токенам

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

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

Основные понятия

* Лексема: Фактическая последовательность символов в исходном коде (например, if, count, 123). * Токен: Пара, состоящая из имени токена (типа) и, опционально, значения атрибута. Это абстрактный символ, который будет использовать синтаксический анализатор. * Шаблон (Pattern): Правило, описывающее множество лексем, которые могут представлять конкретный токен.

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

Для лексера это просто строка символов. После обработки он выдаст поток токенов:

`<IDENTIFIER,

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

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

Например, последовательность токенов int, x, =, ;, 5 состоит из правильных слов, но не имеет смысла в языке C++. А вот int x = 5; — имеет. Различием между бессмысленным набором слов и правильным предложением занимается синтаксический анализатор (или парсер).

В этой статье мы изучим теоретическую основу парсинга — контекстно-свободные грамматики, и перейдем к практике — построению Абстрактного Синтаксического Дерева (AST).

Роль синтаксического анализатора

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

Если лексер отвечает на вопрос «Какие слова написаны?», то парсер отвечает на вопрос «Как эти слова образуют предложения?».

Основные задачи парсера:

Проверка синтаксиса: Убедиться, что токены следуют правилам грамматики языка.

Восстановление структуры: Понять вложенность операций (например, что умножение выполняется раньше сложения).

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

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

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

КСГ достаточно мощны, чтобы описать вложенные структуры (скобки, блоки кода if-else), но при этом достаточно просты, чтобы для них существовали эффективные алгоритмы разбора.

Формальное определение

Математически контекстно-свободная грамматика определяется как четверка:

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

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

Рассмотрим простую грамматику для арифметических выражений. Пусть у нас есть числа и операции сложения и умножения.

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

Expr Expr + Term

Expr Term

Term Term * Factor

Term Factor

Factor ( Expr )

Factor number

Здесь Expr, Term, Factor — это нетерминалы (), а +, *, (, ), number — терминалы ().

Такая структура правил неслучайна. Разделение на Expr (выражение), Term (сшагаемое) и Factor (множитель) позволяет задать приоритет операций. Умножение находится «глубже» в правилах, поэтому оно будет выполнено раньше сложения.

Деревья вывода и неоднозначность

Процесс применения правил грамматики к строке токенов называется выводом. Результат этого процесса можно представить в виде Дерева Конкретного Синтаксиса (Concrete Syntax Tree, CST) или дерева разбора.

!Дерево конкретного синтаксиса для выражения 1 + 2 * 3, демонстрирующее приоритет операций

Проблема неоднозначности

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

Пример плохой (неоднозначной) грамматики: Expr Expr + Expr | number

Для выражения 1 + 2 + 3 мы можем сначала сгруппировать (1+2)+3 или 1+(2+3). Для сложения это не критично (ассоциативность), но для вычитания 1 - 2 - 3 разница огромна: (1-2)-3 = -4, а 1-(2-3) = 2.

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

От CST к AST: Убираем лишнее

Дерево конкретного синтаксиса (CST) содержит полную информацию о выводе, включая все скобки, запятые и промежуточные нетерминалы (Term, Factor), которые нужны были только для соблюдения правил грамматики. Для дальнейшей работы (анализа типов, генерации кода) эта информация избыточна.

Поэтому мы строим Абстрактное Синтаксическое Дерево (Abstract Syntax Tree, AST).

AST — это сжатое представление структуры программы, где: * Внутренние узлы — это операторы (сложение, присваивание, цикл). * Листья — это операнды (переменные, числа). * Синтаксический «шум» (скобки, точки с запятой) удален, так как структура дерева уже однозначно задает порядок выполнения.

Сравнение CST и AST

Рассмотрим выражение: x = (a + b)

CST (Громоздкое):

AST (Лаконичное):

!Визуальное сравнение Дерева Конкретного Синтаксиса (слева) и Абстрактного Синтаксического Дерева (справа)

Алгоритмы синтаксического анализа

Существует два основных подхода к построению деревьев:

Top-Down (Сверху-вниз): Мы начинаем со стартового символа и пытаемся раскрыть его правила так, чтобы получить входную строку токенов. Мы строим дерево от корня к листьям.

Пример:* Метод рекурсивного спуска (Recursive Descent).

Bottom-Up (Снизу-вверх): Мы берем токены и пытаемся «свернуть» их обратно в стартовый символ . Мы строим дерево от листьев к корню.

Пример:* LR-парсеры (используются в генераторах типа Yacc/Bison).

В нашем курсе мы будем ориентироваться на Метод рекурсивного спуска. Он интуитивно понятен, легко пишется вручную и используется во многих промышленных компиляторах (например, GCC для C++, V8 для JavaScript).

Практика: Проектирование узлов AST

Прежде чем писать код парсера, нужно определить структуру данных для AST. В объектно-ориентированном подходе (C++, Java, C#) это обычно иерархия классов.

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

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

Заключение

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

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

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

Поздравляю! Если вы читаете эту статью, значит, вы уже прошли два сложнейших этапа создания компилятора. Ваш лексер научился разбивать текст на слова (токены), а парсер успешно строит из них грамматические деревья (AST). Казалось бы, дело сделано: компьютер «понял» структуру кода. Но так ли это?

Взгляните на это предложение: «Зеленые бесцветные идеи яростно спят».

С точки зрения грамматики русского языка здесь все идеально: есть подлежащее, сказуемое, определения и обстоятельство. Но с точки зрения смысла — это абсурд. Точно так же и в программировании. Парсер может пропустить конструкцию результат = "текст" / 5;, потому что грамматически это верное выражение (переменная присваивает результат деления). Однако попытка разделить строку на число лишена смысла.

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

Что такое семантический анализ?

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

Если синтаксис отвечает на вопрос «Как это написано?», то семантика отвечает на вопрос «Что это значит и допустимо ли это?».

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

Связывание имен (Name Resolution): Понять, на какую именно переменную ссылается идентификатор x в конкретном месте кода.

Проверка типов (Type Checking): Убедиться, что операции выполняются над совместимыми данными.

Проверка контекстных условий: Например, убедиться, что break используется только внутри цикла, а функция возвращает значение заявленного типа.

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

Таблица символов: сердце компилятора

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

Каждая запись в таблице обычно содержит: * Имя: (например, count). * Тип: (например, int). * Область видимости: (где эта переменная доступна). * Местоположение: (смещение в памяти, если мы уже генерируем код, или номер строки для вывода ошибок).

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

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

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

!Иерархия областей видимости: поиск переменной начинается с текущего блока и идет вниз до глобального уровня

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

Вход в блок (функцию, цикл): Создаем новую пустую таблицу символов и помещаем её на вершину стека. Эта таблица ссылается на предыдущую (родительскую).

Объявление переменной: Добавляем запись в таблицу, находящуюся на вершине стека. Если переменная с таким именем уже есть в текущей таблице — это ошибка «повторное объявление».

Использование переменной: Ищем имя в текущей таблице. Если не нашли — переходим в родительскую. Повторяем, пока не найдем или не дойдем до конца. Если не нашли нигде — ошибка «необъявленная переменная».

Выход из блока: Удаляем верхнюю таблицу со стека. Локальные переменные «забываются».

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

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

Существует два основных вида типизации: * Статическая: Типы проверяются во время компиляции (C++, Java, Rust). Это безопаснее и быстрее при исполнении. * Динамическая: Типы проверяются во время выполнения (Python, JavaScript). Это гибче, но чревато ошибками в рантайме.

Мы, как создатели компилятора, фокусируемся на статической проверке.

Как работает проверка типов?

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

Рассмотрим формальное правило для сложения двух чисел. В теории типов это записывается так:

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

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

Пример обхода AST

Представьте выражение: x = y + 5, где x и y — целые числа (int).

Узел 5 (Literal): Компилятор видит число. Тип: int.

Узел y (Identifier): Компилятор идет в таблицу символов, ищет y. Находит, что y — это int. Тип: int.

Узел + (BinaryOp): Компилятор проверяет левый (y) и правый (5) операнды. Оба int. Правило сложения соблюдено. Результат операции — int. Тип: int.

Узел x (Identifier): Ищем x в таблице. Находим int. Тип: int.

Узел = (Assignment): Компилятор проверяет: можно ли присвоить значение типа int (справа) переменной типа int (слева)? Да. Ошибок нет.

Если бы x был строкой (string), на шаге 5 мы бы получили ошибку: Type Mismatch: cannot assign 'int' to 'string'

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

С программной точки зрения, семантический анализатор удобнее всего реализовать с помощью паттерна проектирования Visitor (Посетитель).

У вас уже есть классы узлов AST (BinaryOp, Number, IfStatement). Вы создаете отдельный класс SemanticAnalyzer, который содержит методы visit для каждого типа узла.

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

Вывод типов (Type Inference)

Современные языки (Go, Rust, Swift, Kotlin, современные C++ и Java) умеют сами догадываться о типах. Это называется выводом типов.

Вместо int x = 5; вы пишете var x = 5;.

Как это работает? Компилятор смотрит на правую часть выражения. Он видит 5, знает, что это int, и делает вывод: «Ага, значит переменная x тоже должна быть int`». Это упрощает жизнь программисту, но усложняет работу семантического анализатора, так как ему приходится решать уравнения типов.

Заключение

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

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

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

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

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

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

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

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

Если писать прямой переводчик для каждой пары «язык-язык», вам придется написать различных программ. Это называется проблемой , где — количество исходных языков (frontend), а — количество целевых архитектур (backend).

Решение — использовать промежуточный язык (например, эсперанто или упрощенный английский). Тогда вам нужно написать всего 5 переводчиков в промежуточный язык и 5 переводчиков из него. Итого программ.

В компиляторах роль такого «эсперанто» играет IR. Это позволяет:

Модульность: Можно подключить новый язык (например, Rust) к существующему бэкенду (например, LLVM), просто написав генератор IR.

Оптимизация: Можно написать алгоритмы оптимизации один раз для IR, и они будут работать для любого языка, который компилируется в этот IR.

!Иллюстрация того, как промежуточное представление связывает множество языков с множеством архитектур процессоров

Виды промежуточных представлений

IR бывает разным, в зависимости от целей компилятора:

* Древовидное (Tree-based): Очень похоже на AST, но упрощенное. Удобно для высокоуровневых оптимизаций. * Стековое (Stack-based): Код выглядит как инструкции для стековой машины. Пример: Java Bytecode или .NET CIL. * Линейное (Linear): Похоже на ассемблер, но с бесконечным количеством регистров. Самый популярный формат для оптимизирующих компиляторов.

Мы сосредоточимся на линейном представлении, а именно на Трехадресном коде.

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

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

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

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

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

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

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

Более сложный пример с условием:

В 3AC появляются метки (Labels) и переходы (Jumps):

Такой код намного проще анализировать машине, чем вложенные конструкции if-else или циклы while.

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

Для анализа программы линейный список инструкций разбивают на Базовые блоки (Basic Blocks).

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

Когда мы соединяем эти блоки стрелками (переходами), получается Граф потока управления (Control Flow Graph, CFG).

!Граф потока управления, показывающий логическую структуру программы

CFG — это карта программы, по которой «путешествуют» алгоритмы оптимизации.

SSA: Статическая форма единственного присваивания

Современные компиляторы (GCC, LLVM, Go) используют улучшенную версию 3AC, которая называется SSA (Static Single Assignment).

Главное правило SSA: Каждой переменной значение присваивается ровно один раз.

Если в исходном коде мы меняем переменную:

То в SSA мы создаем новые версии этой переменной:

Где: * — первая версия переменной . * — вторая версия переменной . * — первая версия переменной .

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

Но что делать с ветвлениями? Если меняется и в if, и в else?

В SSA вводится специальная -функция (Фи-функция). Она «выбирает» правильную версию переменной в зависимости от того, откуда пришло управление.

Где означает: «Если мы пришли по левой ветке графа, возьми , если по правой — ». Результат записывается в новую версию .

Основы оптимизации

Имея IR (особенно в форме SSA), мы можем применять алгоритмы оптимизации. Оптимизации делятся на локальные (внутри одного базового блока) и глобальные (во всей функции).

Рассмотрим самые популярные и простые методы.

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

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

До:

После:

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

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

До:

После:

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

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

До:

После:

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

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

До:

После:

Где и — переменные, значения которых не менялись между операциями.

Заключение

Генерация промежуточного кода — это поворотный момент в жизни компилятора. Мы уходим от синтаксиса конкретного языка и переходим к универсальной логике вычислений. Использование IR и форм типа SSA позволяет нам применять мощные математические алгоритмы для улучшения кода.

Теперь, когда наш код оптимизирован и «причесан», он готов к финальному этапу — превращению в инструкции конкретного процессора. В следующей статье мы поговорим о генерации целевого кода и распределении регистров.

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

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

Чтобы программа действительно заработала, её нужно перевести на язык, который понимает процессор — в машинный код. В этой статье мы разберем, как превратить абстрактный IR в конкретные инструкции процессора (x86, ARM или RISC-V), как эффективно использовать ограниченное количество регистров и как организовать память во время выполнения программы.

Архитектура Backend-а

Эту часть компилятора называют Backend (бэкенд). Если Frontend занимается анализом исходного языка, то Backend занимается синтезом целевого кода. Основные задачи этого этапа:

Выбор инструкций (Instruction Selection): Сопоставление операций IR с командами конкретного процессора.

Распределение регистров (Register Allocation): Замена бесконечного числа виртуальных переменных на ограниченный набор физических регистров.

Планирование инструкций (Instruction Scheduling): Изменение порядка команд для более эффективной работы конвейера процессора.

Генерация кода: Запись результата в выходной файл (ассемблер или бинарный объектный файл).

Выбор инструкций: от абстракции к железу

В промежуточном коде (IR) мы использовали абстрактные операции. Например, операция a = b + c выглядит просто. Однако на реальном процессоре одной такой команды может не существовать.

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

Типичный шаблон преобразования для a = b + c:

Процесс выбора инструкций часто реализуется методом покрытия дерева (Tree Covering) или сопоставления с образцом (Pattern Matching).

Представьте, что каждая машинная инструкция — это «плитка» определенной формы, которая может покрыть часть вашего дерева выражений. Задача компилятора — покрыть всё дерево минимальным количеством плиток (самыми эффективными инструкциями).

!Визуализация процесса покрытия дерева (Tree Tiling): узлы IR группируются в шаблоны, соответствующие реальным машинным инструкциям.

CISC против RISC

Сложность выбора инструкций зависит от архитектуры процессора:

* RISC (Reduced Instruction Set Computer): Набор команд упрощен (ARM, RISC-V). Обычно операции выполняются только над регистрами. Это упрощает выбор инструкций, но увеличивает их количество. * CISC (Complex Instruction Set Computer): Набор команд сложен (x86). Одна инструкция может делать много действий (например, загрузить из памяти, сложить и сохранить). Компилятору сложнее выбрать «самую мощную» инструкцию из множества вариантов.

Распределение регистров: самая сложная задача

В нашем промежуточном представлении (IR) мы использовали столько переменных, сколько хотели (виртуальные регистры). Но у физического процессора регистров мало. Например, у x86-64 всего 16 регистров общего назначения (RAX, RBX, RCX и т.д.).

Задача распределения регистров сводится к тому, чтобы уместить тысячи переменных программы в эти 16 слотов. Если переменных слишком много, лишние приходится сохранять в оперативную память (в стек). Этот процесс называется спиллинг (spilling, от англ. «проливание»).

Анализ времени жизни переменных

Чтобы понять, какие переменные могут делить один и тот же регистр, нужно знать их интервал жизни (Liveness Interval). Переменная «жива» от момента первого присваивания до момента последнего использования.

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

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

Классический алгоритм распределения регистров, предложенный Грегори Хайтиным, сводит эту задачу к раскраске графа.

Мы строим граф интерференции (Interference Graph), где: * Вершины — это переменные. * Ребра соединяют те переменные, которые «живы» одновременно (конфликтуют).

Задача: раскрасить вершины графа в цветов так, чтобы никакие две смежные вершины не имели одинаковый цвет.

Где — количество доступных цветов, а — количество физических регистров процессора.

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

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

Управление памятью: Стек и Куча

Сгенерированный код должен где-то хранить данные во время выполнения. Для этого используется среда выполнения (Runtime Environment). Память программы обычно делится на несколько сегментов:

Код (Text): Сами инструкции программы (только для чтения).

Статические данные (Data): Глобальные переменные и константы.

Стек (Stack): Локальные переменные, параметры функций и адреса возврата.

Куча (Heap): Динамически выделяемая память (через new или malloc).

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

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

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

Для доступа к данным внутри кадра используются два регистра: * SP (Stack Pointer): Указывает на вершину стека (конец текущего кадра). * BP (Base Pointer): Указывает на начало текущего кадра (фиксированная точка).

Адрес локальной переменной обычно вычисляется как смещение относительно BP:

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

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

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

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

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

Генерация ассемблерного кода

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

Пример того, как простая функция на C превращается в ассемблер:

Исходный код (C):

Сгенерированный ассемблер (x86-64, синтаксис Intel):

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

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

Лексический анализ: Разбили текст на слова.

Синтаксический анализ: Поняли структуру предложений и построили AST.

Семантический анализ: Проверили смысл и типы.

IR и Оптимизация: Упростили и ускорили код.

Генерация кода: Перевели результат на язык процессора.

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