Введение в разработку собственного языка и компилятора. Создаем на Rust!

© Андрей Невский, 2025

ISBN 978-5-0065-7882-1

Создано в интеллектуальной издательской системе Ridero

Предисловие

Здравствуйте, меня зовут Андрей.

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

Слова «компилятор» и «Rust» могут восприниматься как сложные для освоения. Мой опыт работы с Rust включает исследование языков программирования и систем их обработки, однако создание компиляторов остаётся областью, требующей углублённого изучения. Данная книга представляет собой систематическое изложение знаний, которые я накопил, и служит инструментом для их передачи читателям. Она предназначена для детального анализа процесса разработки компилятора, начиная с синтаксического анализа и заканчивая генерацией кода с использованием LLVM через библиотеку inkwell.

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

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

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

Назначение данной публикации и целевая аудитория

Эта публикация создана с целью предоставления систематического введения в разработку собственного языка программирования, основанного на идеях ML, с использованием Rust и библиотек nom и inkwell для интеграции с LLVM. Она предлагает пошаговое описание теоретических и практических аспектов создания компиляторов, включая анализ синтаксиса, семантику, проверку типов и генерацию кода.

Основные задачи публикации

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

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

Обзор современных инструментов: Читатель получит информацию о современных библиотеках, таких как nom для парсинга и inkwell для работы с LLVM, что позволяет использовать описанные подходы в профессиональной деятельности.

Целевая аудитория

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

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

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

Кто может не найти эту книгу подходящей

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

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

Рекомендации по использованию книги

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

Обратная связь: Ваши замечания, предложения и указание на ошибки или недочёты крайне важны. Пожалуйста, направляйте их на адрес электронной почты, указаный в Главе «Автор» для улучшения качества публикации.

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

Для получения дополнительной информации обращайтесь: по адресу электронной почты, указанный в Главе «Автор»

Глава I Давайте спроектируем собственный язык программирования!

Глава I

Что необходимо решить для того, чтобы создать собственный язык программирования?

Можно выделить множество аспектов, но в общем случае нужно определить синтаксис и семантику языка. Синтаксис определяет, как записываются программы, а семантика – что они означают и как выполняются. Эти два аспекта взаимосвязаны: синтаксис задает форму, а семантика наполняет её содержанием. Для этого необходимо понять, какие задачи должен выполнять язык и как это можно выразить.

Для упрощения мы будем проектировать язык, который реализует несколько базовых конструкций: сложение, вычитание, умножение и деление целых чисел, проверку на равенство, присваивание переменных, оператор if с ветками then и else, а также оператор print.

1.1 Семантика

Теперь давайте рассмотрим семантику нашего языка. Конечно, можно было бы разработать строгое определение семантики, как это сделано, например, в язык Standard ML, но для простоты в нашем случае мы будем использовать более общее и упрощенное определение. Для понимания семантики мы будем опираться на книгу «Основы языков программирования» [1], которая поможет нам лучше понять, как работает семантика в языках программирования.

1.1.1 Вычисления

Первое, что нужно рассмотреть, это смысл вычислений.

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

Начнем с вычислительных выражений. Мы будем реализовывать операции сложения (+), вычитания (-), умножения (*) и деления (/). Сравнение будет ограничено проверкой на равенство (==), которая проверяет, равны ли значения слева и справа.

Присваивание переменной означает, что в переменную записывается заданное значение.

Оператор if оценивает условие: если оно истинно, выполняется инструкция в ветке then, если ложно – инструкция в ветке else (если она есть).

Оператор print выводит результат вычисления заданного выражения.

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

1.1.2 Типы

В проектировании языка концепция типов является крайне важной. Почти все языки программирования, которые приходят на ум, включают концепцию типов. Почему же эта концепция была введена и стала широко использоваться? Для более подробного объяснения можно обратиться к книгам, таким как «Введение в системы типов» [2], но здесь мы кратко рассмотрим концепцию типов.

Роль типов заключается в том, чтобы классифицировать значения, с которыми работает программа. В большинстве языков программирования значению 1 будет присвоен тип, означающий целое число, например, integer или int.

Типы также выполняют роль гарантии правильности вычислений, основываясь на этой классификации.

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

Правила типов

Как же определяются правила типов?

Давайте рассмотрим, как можно определить правила для типов и какие типы присваиваются выражениям.

Запись и значение правил типов

Для записи правил типов в этой книге будет использоваться следующая запись если у выражения e тип τ, то это записывается как:

e:τ

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

предположения называют типовой средой. Для выражения e, чьё типовое предположение в среде Γ равно τ, запись будет выглядеть как:

Γ ⊢ e:τ

Пример:

Рассмотрим выражение 1. В языке, который мы проектируем, числа будут иметь тип int. Следовательно, тип этого выражения будет записан как:

1: int

Теперь рассмотрим тип переменной. Если типовая среда {x: τ} указывает, что переменная x имеет тип τ, то это будет записано как:

{x: τ} ⊢ x: τ

Типовая среда Γ, содержащая x: τ, будет записана как:

Γ ⊢ x: τ

Новая запись для правил:

Для описания правил типизации в книге будет использоваться следующая запись. Если выполняются условия A1, A2, …, An, то выполняется правило A0. Это будет записано как:

A₁, A₂, …, Aₙ

A₀

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

Определение правил типизации

Теперь давайте определим правила типизации для нашего собственного языка программирования.

Если в типовой среде Γ выражение e1 имеет тип int, а выражение e2 имеет тип int, то тип выражения a + b также будет int. Это можно записать следующим образом:

Γ ⊢ e1:int Γ ⊢ e2:int

Γ ⊢ e1+e2: int

Аналогично, для выражения e1 – e2 тип также будет int:

Γ ⊢ e1:int Γ⊢e2:int

int Γ ⊢e1 – e2: int

Для умножения e1 * e2

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 ∗ e2: int

Для деления e1 / e2

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 / e2: int

Теперь рассмотрим оператор сравнения на равенство. Мы будем использовать оператор == для проверки равенства целых чисел, и его тип будет bool. Это можно записать так:

Γ ⊢ e1:int Γ⊢e2:int

Γ ⊢ e1 == e2: int

Таким образом, мы можем типизировать основные выражения для арифметики и сравнения.

Пример:

Предположим, что у нас есть выражение x == (1 +2). Типовое заключение будет следующим:

1. Выражение 1 имеет тип int.

2. Выражение 2 имеет тип int.

3. В типовой среде Γ переменная x имеет тип int.

4. Выражение 1 + 2 имеет тип int.

5. Следовательно, выражение x == (1 + 2) будет иметь тип bool.

Это можно записать как (пример 1):

пример 1

Типизация с выводом типов

Типизация с выводом типов (type inference) – это процесс, при котором типы, явно не указанные в выражении, выводятся на основе контекста и других выражений.

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

В качестве примера рассмотрим язык Standard ML, который известен своей мощной системой вывода типов. Рассмотрим определение функции для сложения:

fun add a b = a + b;

Когда эта функция вводится в интерпретатор Standard ML of New Jersey (SML/NJ) [3], система типов автоматически выводит, что функция add принимает два аргумента типа int и возвращает значение типа int.

val add = fn: int -> int -> int

Это означает, что функция add принимает два аргумента типа int и возвращает значение типа int. В Standard ML функции каррируются, то есть, int -> int -> int эквивалентно int -> (int -> int).

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

Вопрос для размышления:

Хотя человеку достаточно просто понять, как работает вывод типов, как именно компьютер выполняет этот процесс и какие алгоритмы используются для вычисления вывода типов в таких языках, как Standard ML?

Вывод типов

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

Унификация – это процесс, при котором для двух терминов s и t находится такая замена, что, применяя её к этим терминам, мы получаем одинаковые термины.