Бесплатный фрагмент - Введение в разработку собственного языка и компилятора

Предисловие

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

Благодарю вас за внимание к этой книге, посвящённой созданию компилятора для собственного языка программирования на языке 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):

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

Типизация с выводом типов (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 находится такая замена, что, применяя её к этим терминам, мы получаем одинаковые термины.

1.1.3 Унификация

Одним из ключевых инструментов для реализации системы вывода типов является алгоритм унификации, предложенный Джоном А. Робинсоном в 1965 году [5]. Этот алгоритм играет центральную роль в определении типов переменных и выражений, позволяя находить наименьшую общую подстановку (унификатор) для двух выражений или устанавливать, что такая подстановка невозможна. Он стал основой для логического программирования, например, в языке Prolog, а также для автоматических систем вывода в искусственном интеллекте, и может быть полезен при проектировании нашего собственного языка.

Как работает алгоритм унификации?

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

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

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

• Применение подстановок: Если в одном терме встречается переменная, а в другом — конкретное значение, алгоритм заменяет переменную этим значением. Например, если у нас есть переменная X и значение a, подстановка X -> a применяется ко всем вхождениям Х.

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

Рассмотрим пример унификации двух термов:

𝑓 (𝑎,𝑥) =𝑓 (y,b)

Алгоритм выполняет следующие шаги:

• Сравниваем корневые функции: обе стороны имеют функцию 𝑓 значит, структура совпадает, и мы продолжаем анализ аргументов.

• Сравниваем первый аргумент: а = y. Это предполагает подстановку y -> a

• Сравниваем второй аргумент: Это предполагает подстановку x-> b

• Итоговая подстановка: {y-> a, x-> b}. С этой подстановкой термы становятся идентичными: 𝑓 (𝑎,𝑏) =𝑓 (𝑎,𝑏) Таким образом, унификация успешна.

Когда алгоритм завершается с ошибкой?

Алгоритм не может найти унификатор, если термы имеют несовместимую структуру. Например, рассмотрим термы:

f (a) =g (b)

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

В языке, который мы проектируем, алгоритм унификации Робинсона может быть использован для вывода типов выражений, таких как x+1 или x == (1+2), где типы переменных могут неизвестными на момент анализа. Например, если переменная x используется в выражении x+1, алгоритм проверит, что оба операнда имеют тип int, и свяжет тип x с int, если это возможно. Такой подход позволит нашей системе типов автоматически определять типы, минимизируя необходимость явного их указания, и обеспечит строгую типизацию, как описано в разделе 1.1.2.

Этот алгоритм станет важным компонентом нашей системы вывода типов, особенно при реализации проверки типов и компиляции, которые мы рассмотрим в последующих главах. Для более глубокого понимания можно обратиться к работам Робинсона [5] и его последователи, включая улучшенные версии алгоритма, приложенные Мартелли и Монтанари [4] которые оптимизируют процесс унификации для более сложных выражений.

Алгоритм унификации Мартелли и Монтанари

В 1982 году Альберто Мартелли и Уго Монтанари предложили улучшенную версию алгоритма унификации Робинсона, адаптированную для работы с более сложными выражениями и множествами уравнений типов.

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

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

Из множества уравнений E выбирается одно уравнение. Если уравнение имеет форму X = t, где переменная X не появляется в других уравнениях множества E, оно не выбирается. Если множество E состоит из уравнений вида:

X1 = r1, X2 = r2, …, Xm = rm

и переменные X1, X2, …, Xm не появляются в терминах r1, r2, …, rm, то унификация завершена успешно.

Выбираем уравнение и выполняем следующие шаги:

· Если уравнение имеет форму f (l1, …, lk) = f (m1, …, mk), то оно удаляется из множества E, а уравнения l1 = m1, …, lk = mk добавляются в множество E.

· Если уравнение имеет форму f (l1, …, lk) = g (m1, …, mk), и f и g различны, то алгоритм завершится неудачей.

· Если уравнение имеет форму X = X, то оно удаляется из множества E.

· Если уравнение имеет форму X = t, и термин t не содержит переменной X, и X не появляется в другом уравнении, то применяется замена [t/X] ко всем остальным уравнениям в E.

· Если уравнение имеет форму X = t, и t содержит переменную X, алгоритм завершится неудачей (это называется проверкой на самопоявление — occurs check).

· Если уравнение имеет форму t = X, и t не является переменной, то уравнение t = X удаляется из множества E, и добавляется уравнение X = t (меняем местами левую и правую часть уравнения).

· Возвращаемся к множеству уравнений E.

Когда алгоритм завершится успешно, множество E будет иметь вид:

X1 = r1, X2 = r2, …, Xm = rm

И эта замена будет являться наиболее общим унификатором для множества уравнений E.

Рассмотрим следующий пример на языке Standard ML:

val x = 1;
val y = x +2;
val z = y * 3;
Пусть X — тип x, Y — тип y, Z — тип z. Тогда:
x = 1 → X = int
y = x +2 → Y = int (так как + требует int для x и 2)
z = y * 3 → Z = int (так как * требует int для y и 3)

Итог: X = int, Y = int, Z = int.

В этой программе тип очевиден только для числа 1, который имеет тип int. Чтобы выполнить вывод типов, заменим неизвестные части на переменные типов. Пусть тип переменной x будет X, тип переменной y — Y, а тип переменной z — Z. Тогда множество типовых уравнений E будет следующим:

E = {X = Y, Y = Z, Z = int}

Теперь проведем унификацию для типов Z и int. Поскольку они совпадают, замена [int/Z] будет применена. После этого множество уравнений будет выглядеть так:

E = {X = Y, Y = int, Z = int}

Далее, рассматривая типы Y и int, мы применяем замену [int/Y]. После применения этой замены множество уравнений становится:

E = {X = int, Y = int, Z = int}

Теперь мы можем сделать вывод, что тип переменной x (то есть X) — это int.

В языке, который мы проектируем, алгоритм Мартелли и Монтанари может быть использован для расширения системы вывода типов, особенно при обработке более сложных выражений, включающих несколько переменных и операций. Хотя наш язык ограничивается типами int и bool, этот подход позволит нам автоматически определять типы переменных и выражений, таких как x+y или x == (1+2), минимизируя необходимость явного указания типов. Такой механизм обеспечит строгую типизации и упростит разработку компилятора, который мы реализуем в последующих главах .

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

1.2 Синтаксис

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

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

1.2.1 Определение синтаксиса

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

Элементы, которые мы хотим реализовать, это: сложение, вычитание, умножение, деление, сравнение на равенство*¹, присваивание, оператор if с ветками then и else, а также оператор print.

Что касается сложения, вычитания, умножения и деления, то здесь нет необходимости сильно углубляться. Для двух выражений просто используем операторы +, -, * или / как инфиксные операторы.

Оператор if в большинстве языков позволяет создавать блоки и помещать несколько инструкций внутри одного оператора if. Но для нашего языка мы примем более простое решение: if будет принимать выражение и одну инструкцию для ветки then, а также опциональную инструкцию для ветки else, если она указана.

Пример синтаксиса:

if 1 == 1 then print 1 else print 0.

Оператор print уже был упомянут, и для него мы примем синтаксис, который принимает одно выражение.

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

Пример программы на созданном языке

a = 1 +2 * 3

if a == 6 then print 6 else print 0

Вот так будет выглядеть синтаксис, правильно?

1.2.2 Методы определения синтаксиса

Итак, как же нам определить синтаксис, о котором мы говорили до сих пор?

Для того чтобы программа могла быть разобрана компилятором, синтаксис должен быть определён достаточно строго, чтобы его можно было обработать компьютером. В этой книге мы будем использовать Extended Backus-Naur Form (расширенная форма Бэкуса-Наура), которая часто используется для определения синтаксиса собственных языков.

Введение в Extended Backus-Naur Form

Extended Backus-Naur Form (EBNF) — это метаязык для описания синтаксических правил, определённый в ISO/IEC 14977 [6]. В этой книге мы будем ссылаться на стандарт ISO/IEC 14977:1996 для определения синтаксиса. Здесь мы дадим краткое введение в EBNF, но если возникнут вопросы, рекомендуется ознакомиться с оригинальным документом. Кстати, помимо расширенной формы Бэкуса-Наура, существует также другая форма, которая может быть переведена как Augmented Backus-Naur Form (ABNF), и она определена в RFC 5234. Изучение ABNF также будет полезным.

Запись правил в EBNF проста и понятна. Давайте рассмотрим пример. Например, если мы хотим определить правило abc, которое соответствует только строке «ABC», это можно сделать следующим образом:

Определение правила abc в EBNF

Если мы хотим определить правило abc, которое соответствует только строке «ABC», то в EBNF это будет выглядеть так:

abc::= «ABC»;

• abc — это имя правила.

•::= — символ присваивания, означающий, что правило abc соответствует выражению справа от::=.

• «ABC» — строка, которая является значением этого правила. Обратите внимание, что строки в EBNF заключаются в двойные кавычки.

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

Правило, в котором строка ABC следует за строкой DEF:

abcdef::= «ABC» «DEF»;

• abcdef — это имя правила.

•::= — символ присваивания, который обозначает, что правило abcdef соответствует выражению справа от::=.

• «ABC» и «DEF» — строки, которые следуют одна за другой.

Это правило говорит, что abcdef будет соответствовать строке, состоящей из «ABC», за которой сразу следует «DEF».

Как видно, для объединения правил в EBNF используется пробел (или иногда запятая). В случае с примером, строки «ABC» и «DEF» объединяются непосредственно, без дополнительных символов, и это означает, что одно правило должно следовать за другим.

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

Для того чтобы создать правило, которое может принять как строку «ABCDEF», так и строку «DEF» (т.е. строка ABC является необязательной), в EBNF используется конструкция для опциональных элементов. Опциональные элементы в EBNF обычно заключаются в квадратные скобки.

Пример такого правила:

abc_optional::= «ABC» [«DEF»];

• abc_optional — это имя правила.

• «ABC» — обязательная часть правила.

• [«DEF»] — опциональная часть правила. Квадратные скобки обозначают, что строка «DEF» может быть, а может и не быть частью строки.

Таким образом, это правило принимает как строку «ABCDEF», так и строку «ABC», поскольку «DEF» является опциональным.

Правило, которое сочетает необязательное правило abc и строку DEF:

Чтобы создать правило, которое комбинирует необязательное правило abc и строку DEF, это можно записать в EBNF следующим образом:

abc_def_optional::= [«ABC»] «DEF»;

• [ "ABC" ] — означает, что строка "ABC" является необязательной (может быть или не быть).

• «DEF» — обязательная часть.

Такое правило примет строки как "DEF", так и "ABCDEF", где "ABC" является необязательной.

Теперь рассмотрим пример для повторяющихся элементов.

Правило abc, повторяющееся 0 или более раз:

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

abc_repeat::= {«ABC»};

• {«ABC»} — обозначает, что строка «ABC» может повторяться 0 или более раз.

Это правило будет принимать пустую строку (0 повторений), строку "ABC" (1 повторение), строку "ABCABC" (2 повторения) и так далее.

Таким образом, правило abc_repeat будет позволять строки, состоящие из одного или нескольких повторений "ABC".

Теперь рассмотрим правило для 1 и более повторений:

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

abc_repeat_once::= («ABC») +;

• («ABC») + — означает, что строка «ABC» должна повторяться как минимум 1 раз, но может повторяться и больше раз.

Это правило примет строки «ABC», «ABCABC», «ABCABCABC» и так далее, но не пустую строку.

Правило abc, повторяющееся 1 и более раз:

Для того чтобы выразить повторение правила abc один раз и более, можно использовать конструкцию с исключением, используя символ "-".

В EBNF исключение задается с помощью символа "-», который указывает, что данное правило не должно быть пустым (то есть исключается пустая строка). Таким образом, исключив пустое правило, мы гарантируем, что «ABC» будет повторяться хотя бы один раз.

abc_repeat_once::= {«ABC»} — «»;

• { "ABC" } — указывает, что строка "ABC" может повторяться 0 или более раз.

• — «» — исключает пустую строку, что означает, что повторение должно происходить хотя бы один раз, т.е. «ABC» повторяется 1 или более раз.

Таким образом, это правило будет соответствовать строкам «ABC», «ABCABC», «ABCABCABC» и так далее, но не пустой строке.

Для выражения точного количества повторений (например, ровно два раза) в EBNF используется следующее:

abc_repeat_exactly_twice::= «ABC» «ABC»;

• Это правило требует, чтобы строка «ABC» встречалась ровно дважды, то есть будет соответствовать только строкам «ABCABC».

На секунду остановимся, выдохнем и пойдем дальше, осталось не много!

Правило для 3 повторений abc

для указания точного количества повторений используется {элемент} для 0 или более повторений, (элемент) + для 1 или более, или явное повторение, как в abc_repeat_exactly_twice::= «ABC» «ABC»

abc_repeat_three::= «ABC» «ABC» «ABC»;

Правило abc или строка «DEF» могут быть выражены следующим образом:

Правило, которое может принять либо правило abc, либо строку DEF:

abc_or_def::= «ABC» | «DEF»;

• «ABC» | «DEF» — означает, что правило abc_or_def может быть либо «ABC», либо «DEF». Символ | используется для обозначения альтернатив, позволяя выбрать одно из двух значений.

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

Правило, которое принимает либо правило abc, либо строку DEF, заключенную в строку X:

abc_or_def_in_X::= «X» «ABC» «X» | «X» «DEF» «X»;

• "X" "ABC" "X" | "X" "DEF" "X" — это выражение, которое говорит, что правило может быть либо "ABC", либо "DEF", при этом каждая из этих строк заключена в символы "X".

• Символ | указывает на альтернативы, а строки «ABC» и «DEF» должны быть окружены символом «X» с обеих сторон.

x_abc_or_def::= «X» {«ABC» | «DEF»} «X»;

• "X" — символ, который должен быть в начале и в конце строки.

• { "ABC" | "DEF" } — это правило, которое указывает, что внутри строки может быть либо "ABC", либо "DEF".

• Символ | указывает на альтернативы (либо одно, либо другое).

• Квадратные скобки {} в EBNF показывают, что элементы могут повторяться 0 или более раз.

Это правило будет принимать строки вроде «XABCX» или «XDEFX».

Определение правил для арифметических выражений с использованием EBNF

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

Определение правил для четырёх арифметических операций

arithmetic = multiplication

| arithmetic, (»+" | "-»), multiplication;

multiplication = term

| multiplication, («*» | "/»), term;

term = number

|»(», arithmetic,»)»;

number = digit -«0», {digit}

| «0»;

digit = «0» | «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | «9»;

Объясним шаг за шагом:

1. digit — это правило для определения цифры. Оно принимает любой символ от «0» до «9».

2. number — это правило для чисел. Оно использует digit для определения чисел. Если первое число не равно 0, оно может быть последовательностью цифр, или числом 0.

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

4. multiplication — это правило для операций умножения и деления. Оно может быть либо term (простое число или выражение в скобках), либо выражением, состоящим из multiplication, знака умножения или деления, и term.

5. arithmetic — это правило для операций сложения и вычитания. Оно может быть либо multiplication (умножение/деление), либо выражением, состоящим из arithmetic, знака сложения или вычитания, и multiplication.

Приоритет операций

В этом определении multiplication и arithmetic разделены, чтобы указать приоритет операторов: умножение и деление имеют более высокий приоритет, чем сложение и вычитание. Это позволяет правильно обрабатывать арифметические выражения, например:

• 2 +3 * 4 будет интерпретироваться как 2 + (3 * 4) из-за приоритета умножения.

Правила для ассоциативности

В математике и программировании существует определённая ассоциативность для операций. Например, для вычитания в выражении 1 — 2 — 3 существует два возможных способа вычисления:

1. (1 — 2) — 3 — это слева направо (левосторонняя ассоциативность).

2. 1 — (2 — 3) — это справа налево (правосторонняя ассоциативность).

В большинстве языков программирования вычитание и сложение имеют левостороннюю ассоциативность. То есть выражение 1 — 2 — 3 обычно интерпретируется как (1 — 2) — 3.

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

Определение правил для сложения и вычитания

arithmetic = multiplication

| arithmetic, (»+" | "-»), multiplication;

В этом правиле, операторы + и — связаны с правилами arithmetic (сложение/вычитание) и multiplication (умножение/деление). Сначала применяется правило arithmetic, затем идет оператор (сложение или вычитание), и после этого снова применяется правило multiplication.

• arithmetic — это рекурсивное правило, которое включает в себя как операции сложения и вычитания, так и операции умножения и деления.

• Важно, что здесь операторы + и — связываются с выражениями слева, то есть соблюдается левосторонняя ассоциативность.

Если требуется правосторонняя ассоциативность:

Если вы хотите изменить ассоциативность на правостороннюю, можно переписать правило следующим образом:

arithmetic = multiplication

| (»+" | "-»), multiplication, arithmetic;

Что изменилось?

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

Определение правил для правой ассоциативности

arithmetic = multiplication

| multiplication, (»+" | "-»), arithmetic;

В этом правиле происходит сначала связывание с правой стороны, это правило правой ассоциативности.

В этом примере правило arithmetic представляет собой правую рекурсию, то есть сначала происходит связывание элементов с правой стороны. Это означает, что операции "+" или "-" связываются с выражениями, которые идут справа, и это создаёт правостороннюю ассоциативность.

Пример: выражение 1 — 2 — 3 будет интерпретироваться как 1 — (2 — 3), что означает, что операторы связываются с правой стороны.

Удаление левой рекурсии

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

Пример левой рекурсии

arithmetic = multiplication | arithmetic, (»+" | "-»), multiplication;

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

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

Простой пример левой рекурсии

ab = «A»| ab, «B»;

Здесь рекурсия правила ab находится слева, поэтому это левая рекурсия.

В этом случае очень просто удалить левую рекурсию. Правило ab в конечном итоге будет соответствовать правилу «A», после чего будет повторяться правило «B». Это можно выразить в форме без левой рекурсии следующим образом.

Пример простого удаления левой рекурсии

ab = «A», {«B»};

Здесь левая рекурсия была удалена, и правило теперь выражает ту же логику, но без рекурсии. Правило ab сначала соответствует «A», после чего может повторяться «B» несколько раз (или не повторяться вовсе).

Теперь давайте посмотрим на пример с арифметическими выражениями. Правило arithmetic можно выразить следующим образом:

Пример удаления левой рекурсии

arithmetic = multiplication, {(»+" | "-»), multiplication};

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

1.2.3 Определение синтаксических правил для собственного языка

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

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

Начнем с базовых элементов — чисел и идентификаторов.

Определение чисел в нашем языке

number = digit -«0», {digit} | «0»;

digit = «0» | «1» | «2» | «3» | «4» | «5» | «6» | «7» | «8» | «9»;

Здесь правило number определяет число следующим образом:

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

• Либо это просто «0».

Правило digit задаёт допустимые символы для чисел — любой символ от «0» до «9».

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

identifier = alphabet, {alphabet | digit | "_»};

alphabet = «a» | «b» | … | «z» | «A» | «B» | … | «Z»;

(Определение alphabet здесь опущено, но подразумевает набор допустимых букв и символов, составляющих имя.)

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

Определение выражений в нашем языке

expression = addsub | addsub, "==», addsub;

addsub = muldiv | addsub, (»+" | "-»), muldiv;

muldiv = term | muldiv, («*» | "/»), term;

term = identifier | number |»(», expression,»)»;

В этом определении:

• term представляет элементарное выражение — либо идентификатор, либо число, либо выражение, заключенное в круглые скобки.

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

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

• expression добавляет возможность сравнения на равенство с использованием оператора "==».

Чтобы устранить эту проблему, правило можно переписать в виде. Давайте перепишем только правило addsub следующим образом:

Устранение левой рекурсии

addsub = muldiv, {(»+" | "-»), muldiv};

muldiv = term, {(«*» | "/»), term};

Это выглядит хорошо.

Запись означает, что сначала анализируется term, а затем, если следует один или несколько операторов "+" или "-», за которыми идут дополнительные term, они объединяются в левостороннее выражение.