Создаем свой язык программирования с блэкджеком и компилятором

3
8754
Добавить в избранное

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

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

Введение

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

Системные требования

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

Таким образом, к системе предъявляются следующие требования:

  • Среда Anaconda (более простой способ для инсталляции LLVMlite – conda, а не классический pip)
  • LLVMlite

  • RPLY (то же, что PLY, но с более хорошим API)

  • LLC (статический компилятор LLVM)
  • GCC

Свой язык программирования: с чего начать?

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

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

Как для этой однострочной программы формально описать грамматику языка? Чтобы это сделать, необходимо использовать расширенную Бэкус – Наурову форму (РБНФ) (англ. Extended Backus–Naur Form (EBNF)). Это формальная система определения синтаксиса языка. Воплощается она при помощи метаязыка, определяющего в одном документе всевозможные грамматические конструкции. Чтобы в деталях разобраться с тем, как работает РБНФ, прочтите эту публикацию.

Создаем РБНФ (EBNF)

Создадим РБНФ, которая опишет минимальный функционал нашей микропрограммы. Начнем с операции суммирования:

Соответствующая РБНФ будет выглядеть следующим образом:

Дополним язык операцией вычитания:

В соответствующем РБНФ изменится первая строка:

Наконец, опишем функцию print:

В этом случае в РБНФ появится новая строка, описывающая работу с выражениями:

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

Компилятор

Компилятор – это программа, переводящая текст ЯП на машинный или другие языки. Программы на TOY в этом руководстве будут компилироваться в промежуточное представление LLVM IR (IR – сокращение от Intermediate Representation) и затем в машинный язык.

Использование LLVM позволяет оптимизировать процесс компиляции без изучения самого процесса оптимизации. У LLVM действительно хорошая библиотека для работы с компиляторами.

Наш компилятор можно разделить на три составляющие:

  • лексический анализатор (лексер, англ. lexer)
  • синтаксический анализатор (парсер, англ. parser)
  • генератор кода

Для лексического анализатора и парсера мы будем использовать RPLY, очень близкий к PLY. Это библиотека Python с теми же лексическими и парсинговыми инструментами, но с более качественным API. Для генератора кода будем использовать LLVMLite – библиотеку Python для связывания компонентов LLVM.

1. Лексический анализатор

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

Воспользуемся последней структурой из примера для РБНФ и найдем токены. Рассмотрим команду:

Наш лексический анализатор должен разделить эту строку на следующий список токенов:

Напишем код компилятора. Для начала создадим файл lexer.py, в программном коде которого будут определяться токены. Для создания лексического анализатора воспользуемся классом LexerGenerator библиотеки RPLY.

Создадим основной файл программы main.py. В этом файле мы впоследствии объединим функционал трех компонентов компилятора. Для начала импортируем созданный нами класс Lexer и определим токены для нашей однострочной программы:

При запуске main.py мы увидим на выходе вышеописанные токены. Вы можете изменить названия своих токенов, но для простоты согласования с функциями парсера их лучше оставить как есть.

2. Синтаксический анализатор

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

 

Чтобы воплотить в жизнь синтаксический анализатор, будем использовать структуру, созданную на этапе РБНФ. К счастью, анализатор RPLY использует формат, схожий с РБНФ. Самое сложное – присоединить синтаксический анализатор к АСД, но когда вы поймете идею, это действие станет действительно механическим.

Во-первых, создадим файл ast.py. Он будет содержать все классы, которые могут быть вызваны парсером, и создавать АСД.

Во-вторых, нам необходимо создать сам анализатор. Для этого в новом файле parser.py аналогично лексеру используем класс ParserGenerator из библиотеки RPLY:

Наконец, обновляем файл main.py, чтобы объединить возможности синтаксического и лексического анализаторов:

Теперь при запуске main.py мы получим значение 6. и оно действительно соответствует нашей однострочной программе «print(4 + 4  – 2);».

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

3. Генератор кода

Третья и последняя часть компилятора – это генератор кода. Его роль заключается в том, чтобы преобразовывать АСД в машинный код или промежуточное представление. В нашем случае будет происходить преобразование АСД в промежуточное представление LLVM (LLVM IR).

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

Чтобы начать, создадим файл codegen.py, содержащий класс CodeGen. Этот класс отвечает за настройку LLVM и создание/сохранение IR-кода. В нем мы также объявим функцию печати.

Теперь обновим основной файл main.py, чтобы вызывать методы CodeGen:

Как вы можете видеть, для того, чтобы обработка происходила классическим образом, входная программа была вынесена в отдельный файл input.toy. Это уже больше похоже на классический компилятор. Файл input.toy содержит все ту же однострочную программу:

Еще одно изменение – передача парсеру методов module, builder и printf. Это сделано, чтобы мы могли отправить эти объекты АСД. Таким образом, для получения объектов и передачи их АСД необходимо изменить parser.py:

Наконец, самое важное. Мы должны изменить файл ast.py, чтобы получать эти объекты и создавать LLMV АСД, используя методы из библиотеки LLVMlite:

После изменений компилятор готов к преобразованию программы на языке TOY в файл промежуточного представления LLVM output.ll. Далее используем LLC для создания файла объекта output.o и GCC для получения конечного исполняемого файла:

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

Следующие шаги

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

  • Переменные
  • Бинарные операторы
  • Унарные операторы
  • Условия
  • Циклы

Итоговый программный код вы также найдете на GitHub.

Оригинал

Другие материалы по теме языков программирования

Интересуетесь программированием на Python?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

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




3 Комментарии

    • «Пример игрушечный, но позволит понять, с чего начать и в каком направлении двигаться.»

  1. В детстве в 7-8 классе пришлось с парнем написать компилятор с собственного же языка программирования в машинные коды для системы команд процессора PDP-11. Писали на машинных же кодах, на автокоде, на ассемблере, потом уже на своём же языке последние версии компилятора дописывали. Дело в том, что нам хотелось писать игры для машин БК-0010, а компилятора для него не было в поставке. А на интерпретаторе FOCAL много игр не напрограммируешь… )))

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

    Много ли сейчас школьников отважится на свой компилятор со своего языка? Привыкла молодёжь к комфорту и потреблению готового. Нас дефицит чего-то толкал на изобретения и трудовые подвиги. )))

Оставьте комментарий