Как написать свой компилятор на python

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

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

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

После парсинга код преобразуется в абстрактное синтаксическое дерево (AST). В Python достаточно определить классы для узлов дерева: операции, выражения, условия. Это дерево служит промежуточным представлением, которое упрощает генерацию итогового кода.

На завершающем этапе реализуется генерация машинного или байт-кода. Для практических экспериментов можно транслировать AST в байт-код Python с использованием модуля ast и встроенной функции compile(). Более сложный вариант – написать собственный генератор кода для виртуальной машины, реализованной на Python.

Разбор исходного кода: построение лексера

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

Этапы построения лексера:

1. Определить набор токенов. Например:
   • Ключевые слова: if, else, while.
   • Операторы: +, -, *, /.
   • Разделители: (, ), ;.
   • Идентификаторы: имена переменных и функций.
   • Литералы: числа и строки.
2. Составить регулярные выражения для каждого типа. Примеры:
   • Идентификатор: [a-zA-Z_][a-zA-Z0-9_]*
   • Целое число: \d+
   • Строка: "[^"]*"
3. Реализовать сканирование текста посимвольно. При совпадении с регулярным выражением фиксировать токен.
4. Игнорировать пробелы и комментарии, не добавляя их в поток токенов.

Минимальная структура токена:

class Token:
def __init__(self, type_, value, position):
self.type = type_
self.value = value
self.position = position

Рекомендации:

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

Создание таблицы токенов и обработка ошибок

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

Пример структуры токена на Python:

from collections import namedtuple
Token = namedtuple("Token", ["type", "value", "line", "column"])
tokens = []

При разборе текста лексер должен добавлять объект Token в таблицу сразу после успешного распознавания лексемы. Это позволяет не только контролировать корректность разбора, но и упрощает дальнейший синтаксический анализ.

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

Пример добавления ошибки в таблицу:

def add_error(char, line, column):
tokens.append(Token("ERROR", char, line, column))

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

Построение синтаксического дерева с помощью парсера

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

Для реализации парсера в Python удобно использовать рекурсивный спуск. Каждая функция парсера отвечает за разбор одной грамматической конструкции. Например, функция parse_expression() разбирает выражения, а parse_statement() – операторы.

Пример фрагмента кода на Python для бинарных операций:

def parse_binary_op(tokens, parse_atom, operators):
left = parse_atom(tokens)
while tokens and tokens[0].type in operators:
op = tokens.pop(0)
right = parse_atom(tokens)
left = BinaryOpNode(left, op.value, right)
return left

Результатом работы парсера является дерево, где можно выполнять дальнейшую оптимизацию и генерацию кода. Например, выражение 2 + 3 * 4 превращается в узел BinaryOpNode(NumberNode(2), '+', BinaryOpNode(NumberNode(3), '*', NumberNode(4))), сохраняя приоритет операций.

Реализация проверки грамматики и приоритетов операций

После построения лексера необходимо формализовать грамматику языка в виде набора правил. Удобнее всего описывать её в форме контекстно-свободной грамматики, где каждое правило сопоставляет нетерминал с последовательностью терминалов и других нетерминалов. Например: Expr → Term ((+ | -) Term)*, Term → Factor ((* | /) Factor)*, Factor → NUMBER | (Expr). Такая структура сразу задаёт приоритет: операции умножения и деления будут обрабатываться глубже по дереву, чем сложение и вычитание.

Для проверки корректности выражений используется рекурсивный спуск или генерация парсера по правилам. При рекурсивном спуске каждая функция отвечает за один нетерминал и возвращает поддерево. Если на вход подано выражение 2+3*4, алгоритм сначала разберёт Term как 3*4, затем включит результат в Expr, сохранив верный приоритет без дополнительных ухищрений.

Важный момент – предотвращение левой рекурсии, которая может привести к бесконечной рекурсии. Например, правило Expr → Expr + Term необходимо переписать в форму Expr → Term ((+ | -) Term)*. Это упрощает реализацию и исключает зацикливание.

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

Если требуется поддержка новых операций, их можно добавить в отдельный уровень правил. Например, унарные операции (-Factor) выносятся в правило выше по приоритету, чем бинарные. Таким образом, дерево разбора всегда отражает истинный порядок вычислений.

Добавление семантического анализа и проверки типов

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

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

Пример структуры для проверки:

class SymbolTable:
def __init__(self):
self.scopes = [{}]
def enter_scope(self):
self.scopes.append({})
def exit_scope(self):
self.scopes.pop()
def declare(self, name, type_):
self.scopes[-1][name] = type_
def lookup(self, name):
for scope in reversed(self.scopes):
if name in scope:
return scope[name]
return None

1. При разборе объявления переменной вызвать declare с именем и типом.
2. При встрече идентификатора проверять его через lookup.
3. При вычислении выражений передавать типы вверх по дереву и сверять операции.

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

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

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

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

Пример упрощённого IR для выражения a = b + c * d может выглядеть так:

t1 = c * d
t2 = b + t1
a = t2

Для построения IR удобно создать отдельный класс IRBuilder, который принимает узлы AST и по шагам генерирует инструкции. Такой класс хранит список временных переменных и предоставляет методы вида emit(op, arg1, arg2, result), формирующие новые элементы IR.

Практически полезно разделить IR на три уровня:

• Высокоуровневое IR (структурированные выражения, циклы, условия);
• Среднеуровневое IR (трёхадресные инструкции, линейный поток);
• Низкоуровневое IR (псевдокод, близкий к ассемблеру).

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

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

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

Простейший способ – сопоставление операторов промежуточного кода с шаблонами целевого языка. Например, арифметическая операция ADD a, b в Python может транслироваться в строку result = a + b. При этом важно учитывать различия в соглашениях: в некоторых языках требуется явное объявление переменных или строгая типизация.

Для управления процессом удобно использовать таблицу соответствий, где каждой инструкции промежуточного кода ставится в соответствие функция генерации. Такой подход облегчает расширение набора операторов и минимизирует дублирование логики.

При генерации кода следует обращать внимание на оптимизацию. Например, вместо последовательных присваиваний можно объединять выражения: промежуточные инструкции T1 = a + b, T2 = T1 * c превращаются в result = (a + b) * c, что уменьшает количество лишних переменных.

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

Практическая реализация в Python может выглядеть как класс CodeGenerator с методами emit_add, emit_sub, emit_mul и т.п., которые принимают операнды и возвращают готовые строки кода. Такой подход позволяет пошагово контролировать процесс генерации и тестировать отдельные части.

Организация запуска и отладки готового компилятора

Для запуска компилятора на Python достаточно предоставить входной файл и указать путь к выходному объектному или промежуточному коду. Удобно оформить точку входа через if __name__ == «__main__»:, чтобы можно было использовать как модуль и как самостоятельную программу. Аргументы командной строки обрабатываются через argparse, позволяя указать исходный файл, директорию для результата и дополнительные опции.

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

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

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

Вопрос-ответ:

Можно ли написать компилятор на Python без глубоких знаний теории компиляторов?

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

С чего лучше начать: с лексического анализа или сразу с парсера?

Обычно начинают с лексера. Его задача — превратить исходный текст в поток токенов: идентификаторы, ключевые слова, числа, скобки, операторы. Это сильно упрощает дальнейшую работу, ведь парсеру удобнее работать с упорядоченными объектами, а не с «сырым» текстом. Когда у вас есть простой лексер, следующий шаг — построить парсер, который будет распознавать структуру программы и строить абстрактное синтаксическое дерево.

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

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

Нужно ли реализовывать собственный генератор машинного кода или можно ограничиться переводом в Python/JavaScript?

Для учебных проектов и первых экспериментов нет необходимости сразу работать с машинным кодом. Чаще делают трансляцию в уже существующий язык с широким набором инструментов. Например, вы пишете компилятор, который принимает свой синтаксис, а на выходе выдаёт Python-код. Такой подход проще, но при этом на практике демонстрирует всю цепочку «текст → токены → дерево → готовая программа». Если же хочется глубже, можно изучать генерацию байткода для виртуальной машины или LLVM IR.