Создание языка программирования. Часть 0
Доброго времени суток Уважаемые Хабра пользователи! Не буду долго рассусоливать, расскажу лишь основное что подтолкнуло меня к написанию данной статьи, и к собственно разработке своего языка программирования.
Все дело в том, что я занимаюсь программированием достаточно давно, и знаю несколько языков программирования. И несмотря на их различия, я в любом языке умудряюсь наворотить сложных конструкций (даже в Python мой код иногда настолько закручен, что я сам не понимаю что я курил когда писал его). В связи с тем что мой код полностью противоречит всем канонам правильного кода, мне стало интересно как же компиляторы и интерпретаторы понимают мой кривой код.
В связи с этим, сразу даю ответ на вопросы «Зачем это надо?! Очередной велосипед написать? Заняться что ли нечем?» — делается это с целью удовлетворения интереса, а так же для того что бы такие же интересующиеся как я имели представление о том как это работает.
Теперь собственно к теории языков программирования. Посмотрим что на этот счет всеми любимая Википедия:
Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель (обычно — ЭВМ) под её управлением.
С этим все понятно, ничего сложного, все мы знаем что это такое.
О том, что предстоит сделать
1. Лексический анализатор. Модуль который будет проверять правильность лексических конструкций, которые предусмотрены нашим языком программирования.
2. Парсер. Данный модуль будет переводить код понятный человеку в поток токенов, которые в последующем будут исполняться или переводиться в машинный язык.
3. Обычно на этом месте стоит оптимизатор, но так как наша поделка является скорее игрушкой чем крупным проектом, я откажусь от оптимизатора. И теперь наши пути расходятся:
3.1. Транслятор. Данный модуль будет транслировать поток токенов полученных от парсера в машинный код. Данный подход используется в компиляторах
3.2. Исполнитель. Данный модуль выполняет команды записанные в виде потока токенов. Данный подход используется в интерпретаторах.
Я больше склоняюсь к созданию некоего промежуточного звена между интерпретатором и компилятором. То есть к созданию языка программирования, который будет транслироваться в байт-код виртуальной машины, которую так же предстоит написать.
Немного о реализации
1. Для реализации транслятора будет использован язык программирования Python. Почему именно он? Потому что его я знаю лучше всех. К тому же, его типизация, а точнее ее полное отсутствие позволит сократить количество переменных используемых при написании кода.
2. Для реализации виртуальной машины так же будет использован Python.
3. Для сборки проекта будет использован PyInstaller, так как он позволяет упаковывать все в один файл, к тому же на данный момент можно собрать для Linux и Windows без особых заморочек.
Теперь к практике
Предлагаю поставить перед собой минимальную задачу, при выполнении которой мы будем считать задачу условно выполненной и дальше можно не идти. Для этого определимся с минимальным синтаксисом языка:
1. Есть однострочные комментарии, начинаются со знака диеза (#) и продолжаются до конца строки.
2. Есть два типа данных (integer, string).
3. Есть возможность вывода информации на экран.
4. Есть возможность ввода значений с клавиатуры.
Напишем простенькую программу на нашем новом языке, с учетом правил которые мы только что сформулировали:
Вод собственно и все. Простенькая программка, которая демонстрирует возможности только что придуманного языка. На этом я думаю следует закончить.
В следующей части начнем написание своего велосипеда, который сможет выполнить код приведенный выше.
Пишем свой язык программирования без мам, пап и бизонов. Часть 0: теория
Тема написания своего ЯПа не дает мне покоя уже около полугода. Я не ставил перед собой цель «убить» CoffeeScript, TypeScript, ELM, тысячи их, я просто хотел понять кухню и как они вообще пишутся.
К моему неприятному удивлению, большинство из этих языков используют Jison (Bison для JavaScript), а это не совсем попадало под мою задачу — «понять», так как по сути дела Jison делает все за вас, собирает AST по заданным вами правилам (Jison как таковой отличный инструмент, который делает за вас львиную долю работы, но сейчас не о нем).
В конечном итоге я методом проб и ошибок (а если сказать точнее, чтения статей и реверс инжиниринга) научился писать свои полноценные языки программирования от разбития исходного текста на лексемы до его трансляции в JS код.
Стоит заметить, что данное руководство не привязано к JavaScript, он выбран исключительно из соображений скорости разработки и читаемости, так что вы можете написать свой «лисп»/»питон»/»ваш абсолютно новый синтаксис» на любом знакомом вам языке.
Также до момента написании компилятора (в нашем случае транслятора), процесс написания языка не отличается от процессов создания языков компилируемых в ASM/JVM bitcode/LLVM bitcode/etc, а это значит, что данное руководство не ограничивается созданием языка трансляцируемого в JavaScript.
Весь код, который будет написан в данной (и последующих статьях), лежит на Github’е. Тегами обозначены начало и концы статей для удобства.
Немного теории
Не углубляясь в википедийность, процесс трансляции исходного кода в конечный JS код протекает следующим образом:
Что тут происходит:
1) Lexer
Исходный код нашей программы разбивается на лексемы. По-простому это нахождение в исходном тексте ключевых слов, литералов, символов, идентификаторов и т.д.
Т.е. на выходе из этого (CoffeeScript):
Мы получаем это (сокращенная запись):
Так-как CoffeeScript отступо-чувствительный и не имеет явного выделения блока скобками < и >, блоки отделяются отступами ( INDENT ом и OUTDENT ом), которые по сути заменяет скобки.
2) Parser
Парсер составляет AST из токенов (лексем). Он обходит весь массив и рекурсивно подбирает подходящие паттерны, основываясь на типи токена или их последовательности.
Из полученных токенов в пункте 1, parser составит, примерно такое дерево (сокращенная запись):
Не стоит пугаться объема дерева, на деле он генерируется рекурсивно и его создание не вызывает трудностей.
3) Compiler
Построение конечного кода по AST. Этот пункт можно заменить на компиляцию в байткод, или даже рантайм, но в рамках данной серии статей мы рассмотрим реализацию транслятора в другой язык программирования.
Компилятор (читай транслятор) преобразует Абстрактно-Синтаксическое Дерево в JavaScript код:
Вот и все. Большинство компиляторов работают именно по такому принципу (с незначительными изменениями. Иногда добавляют процесс стримминга исходного текста в поток символов, иногда напротив объединяют парсинг и компиляцию в один этап, но не нам их судить).
Habrlang
Итак, разобравшись с теорией, нам предстоит собрать свой язык программирования, у которого будет примерно следующий синтаксис (что-бы не особо париться, мы будем делать смесь из Ruby, Python и CoffeeScript):
В следующей главе вы реализуем все основные классы нашего транслятора, и научим его транслировать комментарии Habrlang‘а в JavaScript.
11 шагов к созданию языка программирования
Изучите устройство компьютера
Это правило важно не только для тех, кто желает создать новый язык, но и для тех, кто просто сел за программирование. Вы не можете создать ничего стоящего, если не понимаете, как один код преобразуется в другой и исполняется компьютером. Без понимания того, как функционирует машина, вам будет очень сложно принимать решения в дальнейшем.
Изучите терминологию
В дальнейшем речь пойдёт о парсерах и лексерах, компиляторах и интерпретаторах, синтаксических деревьях и многом другом. Вам будет значительно проще черпать информацию из сети, спрашивать советов у опытных разработчиков, если у вас не будет пробелов в терминологии. Вкупе с пониманием технологий – это фундамент для постройки рабочего языка.
Определитесь с назначением языка
Сразу решите, будет ли ваш язык иметь узкую специализацию или ваша цель – универсальный инструмент, который окажется востребован в любой области IT. Оцените объём работы, которой вам предстоит проделать, поставьте цели, которых вы хотите достичь. Ну и самое главное – определитесь: вы хотите покорить мир или просто попробовать для себя что-то новое?
Очертите основные концепции
Есть ряд вопросов, на которые необходимо ответить:
Эти вопросы помогут сформировать облик будущего языка и породят ряд новых базисных вопросов, на которые тоже придётся дать ответы.
Поэкспериментируйте с синтаксисом
Наличие служебных символов может здорово упростить работу машине и увеличить производительность, но будет отталкивать потенциального пользователя. То же самое с видом функций – простые и интуитивно понятные или максимально отражающие действие.
Дайте название языку
Выберите язык для языка
Новый язык надо на чём-то написать. Суровые гики могут использовать язык ассемблера или машинные коды, но в XXI веке куда больше смысла ориентироваться на высокоуровневые языки: Pascal, C, C++, Swift (компилируемые языки) для интерпретируемого варианта; Java, JavaScript, Python, Ruby (интерпретируемые языки) — для компилируемого. Такие пары обеспечат минимальные потери в производительности.
Поработайте над лексером и парсером
Лексер – инструмент, отвечающий за лексический анализ, разбиения кода на составные единицы, называемые токенами. Парсер, отвечающий за синтаксический анализ, организует иерархию из токенов, определяя порядок их взаимодействия. Графически это можно представить следующим образом:
Не спешите хвататься за голову, для создания лексеров и парсеров есть специальные библиотеки и приложения, которые снимут эту достаточно сложную часть работы.
Создайте стандартную библиотеку
Вне зависимости от того, есть ли у языка встроенные возможности для исполнения базового функционала или требуются внешние библиотеки, вам необходимо создать ряд функций, на которых можно было продемонстрировать хотя бы в общих чертах все заложенные возможности.
Напишите уйму тестов
Создать язык – не так сложно, как заставить его нормально работать. Определить работоспособность всех механизмов языка вам помогут специальные тесты, очерчивающие границы «можно» и «нельзя» и не вызывающие при этом исключительных ситуаций, которые поставят возможности языка в тупик.
Опубликуйте язык
Когда язык будет готов – не смейте прятать его в стол. Даже если мировое господство – не ваша цель, публикация поможет собрать отзывы, найти единомышленников для дальнейших усовершенствований языка. Ну и в конце концов, этим вы сделаете личный вклад в программирование.
Мотивы создания нового языка программирования всегда очень разные: кто-то делает это от скуки, кто-то с целью преодоления существующих барьеров, кто-то для собственного удобства. Вы тоже можете попробовать создать собственный язык, руководствуясь следующими 11 пунктами. Кто знает, возможно, вы станете заметной личностью в мире программирования?
Изучите устройство компьютера
Это правило важно не только для тех, кто желает создать новый язык, но и для тех, кто просто сел за программирование. Вы не можете создать ничего стоящего, если не понимаете, как один код преобразуется в другой и исполняется компьютером. Без понимания того, как функционирует машина, вам будет очень сложно принимать решения в дальнейшем.
Изучите терминологию
В дальнейшем речь пойдёт о парсерах и лексерах, компиляторах и интерпретаторах, синтаксических деревьях и многом другом. Вам будет значительно проще черпать информацию из сети, спрашивать советов у опытных разработчиков, если у вас не будет пробелов в терминологии. Вкупе с пониманием технологий – это фундамент для постройки рабочего языка.
Определитесь с назначением языка
Сразу решите, будет ли ваш язык иметь узкую специализацию или ваша цель – универсальный инструмент, который окажется востребован в любой области IT. Оцените объём работы, которой вам предстоит проделать, поставьте цели, которых вы хотите достичь. Ну и самое главное – определитесь: вы хотите покорить мир или просто попробовать для себя что-то новое?
Очертите основные концепции
Есть ряд вопросов, на которые необходимо ответить:
Эти вопросы помогут сформировать облик будущего языка и породят ряд новых базисных вопросов, на которые тоже придётся дать ответы.
Поэкспериментируйте с синтаксисом
Наличие служебных символов может здорово упростить работу машине и увеличить производительность, но будет отталкивать потенциального пользователя. То же самое с видом функций – простые и интуитивно понятные или максимально отражающие действие.
Дайте название языку
Выберите язык для языка
Новый язык надо на чём-то написать. Суровые гики могут использовать язык ассемблера или машинные коды, но в XXI веке куда больше смысла ориентироваться на высокоуровневые языки: Pascal, C, C++, Swift (компилируемые языки) для интерпретируемого варианта; Java, JavaScript, Python, Ruby (интерпретируемые языки) — для компилируемого. Такие пары обеспечат минимальные потери в производительности.
Поработайте над лексером и парсером
Лексер – инструмент, отвечающий за лексический анализ, разбиения кода на составные единицы, называемые токенами. Парсер, отвечающий за синтаксический анализ, организует иерархию из токенов, определяя порядок их взаимодействия. Графически это можно представить следующим образом:
Не спешите хвататься за голову, для создания лексеров и парсеров есть специальные библиотеки и приложения, которые снимут эту достаточно сложную часть работы.
Создайте стандартную библиотеку
Вне зависимости от того, есть ли у языка встроенные возможности для исполнения базового функционала или требуются внешние библиотеки, вам необходимо создать ряд функций, на которых можно было продемонстрировать хотя бы в общих чертах все заложенные возможности.
Напишите уйму тестов
Создать язык – не так сложно, как заставить его нормально работать. Определить работоспособность всех механизмов языка вам помогут специальные тесты, очерчивающие границы «можно» и «нельзя» и не вызывающие при этом исключительных ситуаций, которые поставят возможности языка в тупик.
Опубликуйте язык
Когда язык будет готов – не смейте прятать его в стол. Даже если мировое господство – не ваша цель, публикация поможет собрать отзывы, найти единомышленников для дальнейших усовершенствований языка. Ну и в конце концов, этим вы сделаете личный вклад в программирование.
Создаем свой язык программирования с блэкджеком и компилятором
В этом пособии с соответствующими примерами кода рассказываем о том, как написать при помощи Python свой язык программирования и компилятор к нему.
Введение
Изучение компиляторов и устройства языков программирования по видеоурокам и руководствам – дело для новичков тяжелое. В этих материалах нередко отсутствуют важные составляющие. Цель публикации – помочь людям, ищущим способ создать свой язык программирования и компилятор. Пример игрушечный, но позволит понять, с чего начать и в каком направлении двигаться.
Системные требования
Если вы незнакомы с нижеприведенными понятиями, не беспокойтесь – мы проясним необходимость этих компонентов далее, по ходу создания компилятора. В качестве лексера и парсера используется PLY. В роли низкоуровневого языка-посредника для генерации оптимизированного кода выступает LLVMlite.
Таким образом, к системе предъявляются следующие требования:
Свой язык программирования: с чего начать?
Начнем с того, что назовем свой язык программирования. В качестве примера он будет называться TOY. Пусть пример программы на языке TOY выглядит следующим образом:
Любой язык программирования включает множество составляющих его компонентов. Чтобы не застрять в мелочах, возьмем в качестве микропрограммы вызов одной функции нашего языка:
Как для этой однострочной программы формально описать грамматику языка? Чтобы это сделать, необходимо использовать расширенную Бэкус – Наурову форму (РБНФ) (англ. Extended Backus–Naur Form ( EBNF )). Это формальная система определения синтаксиса языка. Воплощается она при помощи метаязыка, определяющего в одном документе всевозможные грамматические конструкции. Чтобы в деталях разобраться с тем, как работает РБНФ, прочтите эту публикацию.
Создаем РБНФ (EBNF)
Создадим РБНФ, которая опишет минимальный функционал нашей микропрограммы. Начнем с операции суммирования:
Соответствующая РБНФ будет выглядеть следующим образом:
Дополним язык операцией вычитания:
В соответствующем РБНФ изменится первая строка:
Наконец, опишем функцию print:
В этом случае в РБНФ появится новая строка, описывающая работу с выражениями:
В таком ключе развивается описание грамматики языка. Как же научить компьютер транслироваться эту грамматику в бинарный исполняемый код? Для этого нужен компилятор.
Компилятор
Компилятор – это программа, переводящая текст ЯП на машинный или другие языки. Программы на TOY в этом руководстве будут компилироваться в промежуточное представление LLVM IR (IR – сокращение от Intermediate Representation) и затем в машинный язык.
Использование LLVM позволяет оптимизировать процесс компиляции без изучения самого процесса оптимизации. У LLVM действительно хорошая библиотека для работы с компиляторами.
Наш компилятор можно разделить на три составляющие:
Для лексического анализатора и парсера мы будем использовать 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.