Как создать свой язык программирования

Создаем свой собственный язык программирования с использованием LLVM. Часть 1: Лексический и синтаксический анализ

С 2003 года, когда я поступил в ВУЗ, по нынешнее время я написал много различных парсеров, от простых (чтение конфигурационных файлов в ini, json и yaml форматах) до более сложных (полноценный парсер С++ подобного языка с поддержкой обобщенного программирования в виде шаблонов (схожих по сложности с тем что есть в языках С++ и D), ООП с множественным наследованием, pattern matching и др.), интерпретаторов для различных языков (от простых академических, таких как Brainfuck, до более серьезных скриптовых языков, которые были использованы в различных проектах (в основном различных pet-проектов), которые позволяли решать различные задачи от расчета значений математических функций для построения трехмерных сеток объектов с последующей их визуализацией, до интерпретаторов, позволяющих разработчику/пользователю расширять функционал ПО без модификации исходного кода самого приложения (например создание анимаций, рисования различных объектов, элементов управления и программирование обработчиков для этих элементов управления).

Еще когда я учился в институте мне было интересно изучать различные языки программирования. Позже мне захотелось узнать, как они были устроены внутри, как они работают. Мне было интересно, как из исходных текстов которые мы даем на вход компилятору получается программа, которая может быть запущена и которая делает то, что мы запрограммировали. Что привело меня к изучению теории компиляции и дизайну языков программирования. Я прочитал книгу, которая в свое время была классикой [1], так же во время чтения ее я наткнулся на очень интересную книгу [2], которая была больше направленна не на теорию, а на практику. И тогда у меня зародилась идея написать свой собственный компилятор, для своего собственного языка программирования, но все мои попытки воплотить мою идею в жизнь сталкивались с проблемой, что для того что бы написать хороший компилятор, который мог генерировать эффективный код и быть кросс платформенным, нужны знания, которые сложно получить по учебникам (а именно создание backend компилятора, хотя в это время я уже понимал как различные конструкции языка C++ работали под «капотом», такие как виртуальные таблицы, множественное наследование и много другое). В русском интернете эта тема была не освещена вообще, а в иностранном это что-то полезное было очень сложно найти. Но в какой-то момент я наткнулся на проект под названием LLVM, который позиционировал себя как набор библиотек и инструментов, которые могут помочь в написании компиляторов. Я начал изучать официальную документацию, но ее оказалось не достаточно, т. к. она описывала только простые кейсы использования данного «комбайна», язык Kaleidoscope демонстрировал только базовые концепты, которые могли бы помочь в создании своего языка программирования. Благо на тот момент уже были созданы различные реализации языков программирования, которые использовали LLVM в качестве backend (clang, ldc, crack и несколько других реализаций), соответственно я начал изучать как различные конструкции были реализованы в них. Так и родился simple

Simple

Изначально данный язык был задуман как обобщение всех моих знаний в теории компиляции и применении их в связке с LLVM, для создания простого языка с базовой поддержкой ООП, которые могли бы быть положены в серию статей по созданию языка программирования. Изначально исходный код был написан в итеративном подходе, пригодном для написания серии статей (т. е. наращивание функционала из статьи в статью), но после написания всего планированного функционала, проект по тем или иным причинам был заброшен, поэтому сами статьи пришлось писать с нуля (т. к. исходные версии были утеряны), а сам исходный код пришлось адаптировать (т. к. осталась только финальная версия проекта, без его промежуточных частей). Финальная версия была написана около 11 лет назад (и использовался LLVM 3.0), в новой версии был взят исходный код старого проекта и произведены следующие изменения:

Смена версии LLVM на 14, т. к. версии частично не совместимы, поэтому были произведены некоторые изменения, чтобы программа работала корректно с новыми реалиями;

Изменена структура проекта (за основу был взята структура описанная в [3]).

Сам код по большей части остался в том виде, в каком он был 11 лет назад. Т.к. сам я уже 3 года не пишу на С++, и в последние годы его использования я периодически следил за историей его развития, но не применял большую часть нововведений на практике, поэтому некоторые части кода могут не подходить под правила хорошего тона в написании современных приложений на языке C++. Но должно быть достаточным для базового понимания того, как те или иные вещи можно было бы реализовать в своем языке с использованием LLVM в качестве backend (пожелания по улучшению просьба оставлять в комментариях или в личных сообщениях).

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

О серии

Сам цикл будет разбит на несколько статей, в которых мы реализуем данный язык.

Мы начнем с простого подмножества в котором доступны только два типа данных int и float, пользователь может объявлять локальные переменные и описывать функции, использовать различные арифметические операции над ними, а так же будут доступны управляющие конструкции if, while, for, а так же break, continue и return. Данное подмножество будет реализовано в рамках нескольких статей начиная с лексического и синтаксического анализаторов, затем мы добавим семантический анализатор (проверка типов и корректности программы) и в заключении будет реализована генерация промежуточного кода для LLVM.

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

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

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

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

Замечание по генерируемому коду: в процессе написания изначальной версии я очень много времени провел изучая код, который генерировал clang для различных конструкций языка C++, поэтому на тот момент качество кода генерированного данным интерпретатором был сопоставим с тем, что генерировал clang, включая различные оптимизации по переиспользованию блоков. С тех пор прошло много времени, но код до сих пор в большинстве ситуаций совпадает с тем, что генерирует clang для программы, если ее переписать один-в-один на C++ [5].

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

Поддержка модулей (import и export);

Добавление области видимости для переменных и членов класса (private, protected, public);

Добавление множественного наследования по средством интерфейсов (или полного аналога, как в C++);

Вывод типов (type inference), сопоставление с образцом (pattern matching);

Обобщенное программирование (generics);

Вычисление во время компиляции (template metaprogramming или constant expressions).

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

Согласно Wikipedia компилятор — программа, переводящая написанный на языке программирования текст в набор машинных кодов.

Традиционно компилятор состоит из двух больших блоков:

Frontend – основная задача которого заключается в чтении исходных кодов на конкретном языке программирования, анализа его на наличие как синтаксических, так семантических ошибок, а в случае их отсутствия, генерации промежуточного представления программы, которое может быть передано в backend, для последующей обработки. Один из вариантов представления полученного после успешной отработки frontend является аннотированное AST (Abstract Syntax Tree), в котором содержится вся необходимая информация о программе;

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

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

Раньше для написания backend приходилось писать генератор кода под каждую платформу и операционную систему, с появлением LLVM данная задача упростилась, т. к. достаточно написать генератор в LLVM IR и дальше все остальное можно будет сделать через утилиты, идущие с LLVM (хочу уточнить, что какую-то часть платформозависимых функций придется все равно реализовать, например поддержку ABI для платформы, но все равно большую часть LLVM берет на себя).

Frontend в свою очередь состоит из:

Синтаксический анализатор (или парсер);

Семантический анализатор (или проверка типов);

Генератор промежуточного кода.

Далее мы рассмотрим более подробно первые 2 пункта, последние 2 будут более подробно описаны в следующих статьях.

Backend в свою очередь обычно состоит из:

Оптимизатор промежуточного кода;

Генерация кода для целевой платформы.

В рамках данной серии backend мы рассматривать не будем.

Лексический анализ

Лексический анализатор — часть компилятора, которая читает текст программы из входного потока и преобразовывает его в набор лексем или токенов (неделимые примитивы языка, такие как ключевые слова, идентификаторы, строковые и числовые константы, операторы и др), которые в простейшем случае представляют собой структуру содержащую информацию о типе прочитанного токена и его значение. Так же лексический анализатор часто убирает из выходного потока «шум» (конструкции языка, которые не влияют на дальнейший разбор программы, такие как комментарии и пробельные символы (в языках, где отступы не являются значимыми для разбора программы)). Причина данного шага банальна, проще работать с представлением, которое просто использовать в машинной обработке, в котором нет никаких неоднозначностей. Например для синтаксического анализатора может быть не важно значение целочисленной константы, а важно то, что это целочисленная константа. Так же часто в языках программирование одна и та же лексическая конструкция может быть записана множеством способов. Например, в языке C++ целочисленное число 10 может быть записано множеством способов

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

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

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

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

Для данной серии мы реализуем лексический анализатор сами.

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

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

Сама же таблица символов имеет следующий вид:

Где TokenKind обычный enum вида:

Сам токен, который возвращается в результате лексического анализа имеет вид:

Как видно из выше представленной класса, токен хранит минимальное количество информации:

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

Длина токена и его тип;

Значение токена (для оптимизации места используется union).

Сам же лексический анализатор имеет следующий вид:

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

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

Для упрощения работы, как и с ошибками в лексическом анализаторе, будем просто выводить сообщение об ошибке и завершать работу приложения. Но возможны различные варианты восстановления от ошибок, которые зависят от конкретной конструкции и типа ошибки, например некоторые ошибки могут быть обработаны путем добавление необходимых элементов и продолжения анализа (например отсутствие операнда у бинарного или унарного оператора). Так же это может быть вариант панического восстановления, путем пропуска токенов и поиска ближайшего синхронизирующего токена (например «;» или «>»). Про все эти методы можно более подробно прочитать в [1] или в интернете.

В процессе своей работы парсер будет возвращать AST, со следующим списком базовых типов (все типы поддерживают RTTI, который используется в LLVM [6].

Данный класс является базовым для иерархии типов в дереве (например базовые типы (int, float, bool, void), тип для функций. В последующих статьях серии данный список будет расширен и будут добавлены типы для строк, символов, классов, структур, указателей и массивов.

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

Данный класс является базовым для иерархии различных инструкций языка, такие как условные операторы if, циклы while и for, а так же операторы выхода из цикла break, continue, инструкция возврата из функции, объявление локальных переменных и выражений, а так же блок с набором инструкций.

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

Иерархия для типов

На данный момент для типов у нас будет всего два типа BuiltinTypeAST, который отвечает за базовые типы, такие как int, float, bool и void.

и FuncTypeAST, который отвечает за прототип функции (тип возвращаемого ей значения и типы ее параметров)

Иерархия выражений

Для констант целочисленных и с плавающей точкой будем использовать следующие классы:

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

Для преобразования типов будем использовать следующий класс (т. к. явных преобразований в языке не будет, то этот класс будет в основном использоваться как вспомогательный другими выражениями, для приведения операндов к единому типу (например int к float или int/float к bool в условных выражениях)):

Для выражений с одним операндом (такие как +,-, ++, — и

) будем использовать следующий класс:

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

Для тернарного оператора ? : будем использовать следующий класс:

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

Иерархия для инструкций

Для инструкций, которые содержат выражения (например вызов функции или присвоение переменной):

Инструкция ветвления if:

Цикл с предусловием:

Инструкция для досрочного выхода из цикла:

Инструкция для перехода к следующей итерации цикла:

Инструкция для возврата из функции:

Блок с инструкциями (например тело функции или цикла):

Объявление локальной переменной:

Цикл for. Данный цикл, как и его аналог из C++, имеет три блока (для объявлений переменных цикла или инициализации цикла, условие цикла и операции, которые должны быть выполнены после каждой итерации), которые являются не обязательными, а так же обязательное тело цикла:

Иерархия для объявлений

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

Разбор выражений

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

Следующий вид выражений, это постфиксные операции, такие как ++ и —, а так же вызов функции:

Следующий вид выражений, это выражения с одним операндом:

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

Теперь, когда у нас есть список всех приоритетов, мы можем описать функцию, которая на основе типа токена выдает нам приоритет данного оператора:

Теперь рассмотрим реализацию самого разбора выражений с двумя операндами:

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

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

Для разбора прототипа функции мы будем использовать следующую функцию (она будет применяться в нескольких местах):

Для разбора объявления функции будет использована следующая функция:

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

Разбор модуля со всеми верхнеуровневыми объявлениями:

Разбор объявлений для локальных переменных и блока инициализации в цикле «for»:

Вспомогательная функция, которая считывает инструкцию и если это не блочный элемент (набор инструкций между «<" и ">«), то создает новый элемент дерева в виде блочного элемента:

Разбор инструкций языка:

Для упрощения объявления прототипов функций для внутреннего использования (для подключения функций из языка C++) будем использовать следующую функцию:

Для разбора файла используется следующая функция:

Заключение

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

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

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

На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно — он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub.

Введение

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

Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.

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

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

Первые шаги

«А с чего вообще начинать?» — вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.

Компилируемый или интерпретируемый?

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

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

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

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

Выбор языка

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

Но в целом совет можно дать такой:

• интерпретируемый ЯП крайне рекомендуетсяписать на компилируемом ЯП (C, C++, Swift). Иначе потери производительности будут расти как снежный ком, пока мета-интерпретатор интерпретирует ваш интерпретатор;
• компилируемый ЯП можно писать на интерпретируемом ЯП (Python, JS). Возрастёт время компиляции, но не время выполнения программы.

Проектирование архитектуры

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

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

Строка исходного кода проходит через лексер и превращается в список токенов.

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

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

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

Одним из основных таких инструментов является Flex — генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.

Моё решение

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

Синтаксический анализатор / парсер

Список токенов проходит через парсер и превращается в дерево.

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

Bison

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

Преимущества кастомных программ

С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него — 750 строк, и это уже третья попытка (первые две были просто ужасны).

Тем не менее, я решил делать парсер сам. Вот основные причины:

• минимизация переключения контекста;
• упрощение сборки;
• желание справиться с задачей самостоятельно.

В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей:

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

Абстрактный семантический граф

Переход от синтаксического дерева к семантическому графу

В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).

АСГ vs АСД

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

Запуск

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

Варианты компиляции

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

Написать свой компилятор

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

LLVM — это коллекция инструментов для компиляции, которой пользуются, например, разработчики Swift, Rust и Clang. Я решил остановиться на этом варианте, но опять не рассчитал сложности задачи, которую перед собой поставил. Для меня проблемой оказалось не освоение ассемблера, а работа с огромной многосоставной библиотекой.

Транспайлинг

Мне всё же нужно было какое-то решение, поэтому я написал то, что точно будет работать: транспайлер (transpiler) из Pinecone в C++ — он производит компиляцию по типу «исходный код в исходный код», а также добавил возможность автоматической компиляции вывода с GCC. Такой способ не является ни масштабируемым, ни кроссплатформенным, но на данный момент хотя бы работает почти для всех программ на Pinecone, это уже хорошо.

Дальнейшие планы

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

Заключение

Надеюсь, эта статья окажется кому-нибудь полезной. Я крайне рекомендую хотя бы попробовать написать свой язык, несмотря на то, что придётся разбираться во множестве деталей реализации — это обучающий, развивающий и просто интересный эксперимент.

Вот общие советы от меня (разумеется, довольно субъективные):

• если у вас нет предпочтений и вы сомневаетесь, компилируемый или интерпретируемый писать язык, выбирайте второе. Интерпретируемые языки обычно проще проектировать, собирать и учить;
• с лексерами и парсерами делайте, что хотите. Использование средств автоматизации зависит от вашего желания, опыта и конкретной ситуации;
• если вы не готовы / не хотите тратить время и силы (много времени и сил) на придумывание собственной стратегии разработки ЯП, следуйте цепочке действий, описанной в этой статье. Я вложил в неё много усилий и она работает;
• опять же, если не хватает времени / мотивации / опыта / желания или ещё чего-нибудь для написания классического ЯП, попробуйте написать эзотерический, типа Brainfuck. (Советуем помнить, что если язык написан развлечения ради, это не значит, что писать его — тоже сплошное развлечение. — прим. перев.)

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

О том, что ввязался в историю с созданием Pinecone, ни в коем случае не жалею — это отличный эксперимент, и он только начался.

H Как создать язык программирования в черновиках Из песочницы

Куда же без него! Он требуется для «разделения» всего на токены. Если объяснить зачем он тогда представим: у нас есть код (CoffeScript).

И лексер превращает этот код в это(сокращенная запись):

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

Он превратит в читабельное (!):

Парсер

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

Но ничего не работало, точнее не печатало текст, потом я попробовал так:

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

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

Но все равно ничего не работало 😐 и с таким лицом я пытался что-то сделать… Целый час. И спустя около полутора часа я сделал это!

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

Вопросы-опросники запрещены на Stack Overflow на русском. Для получения ответа, перефразируйте ваш вопрос так, чтобы на него можно было дать однозначно правильный ответ.

Закрыт 7 лет назад .

Я далеко не ас, но хочется попробовать написать какой-то простой язык программирования для веба. Никакой мании величия, просто хочется попробовать. Подскажите, с чего можно начать?

1. Если хотите создавать язык для веб, очевидно будете писать инструмент для интерпретатции/компиляции приложений получающих данные от сервера и выдающих текст в поток стандартного вывода, с тем, чтобы иметь возможность выводить результаты работы программы (веб страницу, например) — здесь могу посоветовать почитать о технологии CGI, написать парочку простых CGI-скриптов (на чем угодно).
2. Определитесь, какой язык будете создавать — интерпретируемый или компилируемый. Каков будет результат работы «компилятора» (например, Вы можете просто написать транслятор, который будет переводить программу на ВАШЕМ языке в эквивалент на PHP, который и будет в дальнейшем использоваться).
3. Наконец, по синтаксическому анализу, компиляции и прочему — советую (не в первый раз) — Дж. Креншоу, «Давайте создадим компилятор» — для человека, который не собирается заморачиваться теорией формальных языков, обратной польской записью, формами Бэкуса-Наура и пр. пр. пр. — в самый раз. Если хотите серьезно заниматься компиляторами — А.Ахо «Компиляторы: принципы, технологии и инструменты» («Dragon book»).

P.S. Если интересуетесь скриптами (в частности, для игр) и скриптовыми языками, советую также обратить внимание на Alex Varanese «Game Scripting Mastery» — хорошо написана и легко читается (на мой вкус)

Язык программирования — просто его идея, спецификация описывающая синтаксис, семантику и стандартную библиотеку.

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

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

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

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

Вполне можно считать примитивным вариантом транслятора.

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