Содержание

теория, инструменты и советы от практика

Рассказывает программист Вильям В. Вольд


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

Введение

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

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

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

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

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

Первые шаги

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

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

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

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

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

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

Выбор языка

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

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

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

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

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

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

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

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

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

Flex

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

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

Моё решение

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

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

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

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

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

Bison

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

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

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

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

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

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

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

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

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

АСГ vs АСД

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

Запуск

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

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

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

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

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

LLVM

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

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

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

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

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

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

Заключение

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

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

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

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

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

Перевод статьи: «I wrote a programming language. Here’s how you can, too»

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

В этой теме есть отличные ответы, но я просто хотел добавить свой, поскольку у меня тоже когда-то был тот же вопрос. (Также я хотел бы отметить, что книга, предложенная Joe-Internet, является отличным ресурсом.)

Сначала вопрос о том, как работает компьютер? Вот как: ввод -> вычисление -> вывод.

Сначала рассмотрим часть «Compute». Мы рассмотрим, как работает ввод и вывод.

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

Чтобы ответить на это, нам нужно понять структуру процессора. Ниже приведен довольно простой вид. Процессор по существу состоит из двух частей. Одним из них является набор областей памяти, встроенных в процессор, которые служат его рабочей памятью. Они называются «регистрами». Второй представляет собой набор электронных механизмов, созданных для выполнения определенных операций с использованием данных в регистрах. Есть два специальных регистра, называемых «счетчик программ» или ПК и «регистр команд» или ир. Процессор считает, что память разделена на три части. Первая часть — это «память программ», в которой хранится исполняемая компьютерная программа. Второе — это «память данных». Третий используется для каких-то особых целей, об этом мы поговорим позже. Счетчик программ содержит местоположение следующей инструкции для чтения из памяти программ. Счетчик команд содержит номер, который относится к текущей выполняемой операции. Каждая операция, которую может выполнить процессор, указывается номером, который называется кодом операции операции. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Счетчик команд содержит номер, который относится к текущей выполняемой операции. Каждая операция, которую может выполнить процессор, указывается номером, который называется кодом операции операции. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Счетчик команд содержит номер, который относится к текущей выполняемой операции. Каждая операция, которую может выполнить процессор, указывается номером, который называется кодом операции операции. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Каждая операция, которую может выполнить процессор, указывается номером, который называется кодом операции операции. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Каждая операция, которую может выполнить процессор, указывается номером, который называется кодом операции операции. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр. Принцип работы компьютера заключается в том, что он считывает ячейку памяти, на которую ссылается счетчик программ, в регистр команд (и увеличивает счетчик программ так, чтобы он указывал на ячейку памяти следующей инструкции). Затем он читает регистр команд и выполняет требуемую операцию. Например, инструкция может состоять в том, чтобы считывать определенную ячейку памяти в регистр, или записывать в какой-либо регистр, или выполнять некоторую операцию, используя значения двух регистров, и записывать вывод в третий регистр.

Теперь, как компьютер выполняет ввод / вывод? Я приведу очень упрощенный ответ. См. Http://en.wikipedia.org/wiki/Input/output и http://en.wikipedia.org/wiki/Interrupt, для большего. Он использует две вещи, третью часть памяти и нечто, называемое прерываниями. Каждое устройство, подключенное к компьютеру, должно иметь возможность обмениваться данными с процессором. Это делается с использованием третьей части памяти, упомянутой ранее. Процессор выделяет часть памяти каждому устройству, и устройство и процессор обмениваются данными через этот фрагмент памяти. Но как процессор узнает, какое местоположение относится к какому устройству и когда ему нужно обмениваться данными? Это то место, где приходят прерывания. Прерывание — это, по сути, сигнал процессору приостановить текущее состояние и сохранить все свои регистры в известном месте, а затем начать делать что-то еще. Там много прерываний, каждое из которых идентифицируется уникальным номером. Для каждого прерывания существует специальная программа, связанная с ним. Когда происходит прерывание, процессор выполняет программу, соответствующую прерыванию. Теперь, в зависимости от BIOS и того, как аппаратные устройства подключены к материнской плате компьютера, каждое устройство получает уникальное прерывание и часть памяти. При загрузке операционной системы с помощью биоса определяется прерывание и место в памяти каждого устройства, а также настраиваются специальные программы для прерывания для правильной обработки устройств. Поэтому, когда устройству нужны какие-то данные или они хотят отправить какие-то данные, оно сигнализирует о прерывании. Процессор приостанавливает то, что он делает, обрабатывает прерывание и затем возвращается к тому, что он делает. Существует много видов прерываний, например, для жесткого диска, клавиатуры и т. Д. Важным является системный таймер, который вызывает прерывания через равные промежутки времени. Также есть коды операций, которые могут вызывать прерывания, называемые программными прерываниями.

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

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

Как можно разрабатывать процессор и язык ассемблера? Чтобы знать, что вы должны прочитать некоторые книги по компьютерной архитектуре. (см. главы 1-7 книги, на которую ссылается joe-internet). Это включает в себя изучение булевой алгебры, как создавать простые комбинаторные схемы для сложения, умножения и т. Д., Как строить память и последовательные схемы, как создавать микропроцессор и так далее.

Теперь, как писать компьютерные языки. Можно начать с написания простого ассемблера в машинном коде. Затем используйте этот ассемблер, чтобы написать компилятор для простого подмножества C. Затем используйте это подмножество C, чтобы написать более полную версию C. Наконец, используйте C, чтобы написать более сложный язык, такой как python или C ++. Конечно, чтобы написать язык, вы должны сначала спроектировать его (так же, как и процессор). Снова посмотрите на некоторые учебники по этому вопросу.

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

Таким образом, чтобы написать ОС, вы должны написать «загрузчик». Затем вы должны написать код для обработки прерываний и устройств. Затем вы должны написать весь код для управления процессами, управления устройствами и т. Д. Затем вы должны написать API, который позволяет программам, запущенным в вашей ОС, получать доступ к устройствам и другим ресурсам. И, наконец, вы должны написать код, который читает программу с диска, устанавливает ее как процесс и начинает выполнять ее.

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

Как создать свой язык программирования: теория, инструменты и советы от практика | ДНЕВНИК СТУДЕНТА

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

Введение

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

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

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

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

Первые шаги

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

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

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

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

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

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

Выбор языка

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

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

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

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

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

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

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

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

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

Flex

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

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

Моё решение

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

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

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

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

Bison

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

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

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

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

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

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

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

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

АСГ vs АСД

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

Запуск

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

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

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

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

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

LLVM

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

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

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

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

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

Заключение

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

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

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

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



Возможные Дубликаты:
Ссылки, необходимые для реализации интерпретатора в C/C++
Как создать язык в наши дни?
Учимся писать компилятор

Я знаю некоторые c++, VERY хорошо в php, профи в css html, хорошо в javascript. Итак, я думал о том, как был создан c++, я имею в виду, как компьютер может понять, что означают коды? Как он может читать… так возможно ли, что я могу создать свой собственный язык и как?

c++ compiler-construction programming-languages interpreter
Поделиться Источник Ramilol     07 сентября 2010 в 20:22

13 ответов




48

Если вас интересует дизайн компилятора («как компьютер может понять, что означают коды»), я настоятельно рекомендую Dragon Book . Я использовал его еще в колледже и дошел до того, что сам создал язык программирования.

Поделиться Nikita Rybak     07 сентября 2010 в 20:27


Поделиться anthony     07 сентября 2010 в 20:39



20

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

Для еще более низкого уровня понимания вам нужно будет изучить электронику. Цифровая логика показывает вам, как вы можете взять электронный «gates» и реализовать универсальный CPU, который может понять машинный код, сгенерированный из кода языка assembly.

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

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

Поделиться Mr Fooz     07 сентября 2010 в 20:29


  • Как добавить свой собственный язык программирования в IDE?

    Существует простой интерпретирующий язык программирования и, собственно, консоль interpreter.exe. Нужно сделать раскрашивание синтаксиса, автозаполнение и выполнение нажатием клавиши F5. (если можно сделать ‘debug’-это будет потрясающе!) Я никогда не делал таких вещей. Есть много IDE, которые…

  • Создайте язык программирования JVM

    Я создал компилятор в C (используя lex & bison) для динамического типизированного языка программирования, который поддерживает циклы, объявления функций внутри функций, рекурсивные вызовы и т. д. Я также создал виртуальную машину, которая запускает промежуточный код, созданный компилятором….



11

Да, можно создать свой собственный язык. Взгляните на компиляторы компиляторов. Или исходный код некоторых скриптовых языков, если вы осмелитесь. Некоторые полезные инструменты — это yacc, bison и lexx.

Другие упоминали книгу о драконах. Мы использовали книгу, которая, по-моему, называлась «compiler theory and practice» еще в мои университетские дни.

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

Самым простым языком запуска программы может быть написание простого текстового калькулятора, то есть взятие текстового файла, запуск через него и выполнение вычислений. Вы могли бы написать это в C++ очень легко.

Моим первым языком для проекта в колледже был язык, определенный в BNF году, данный нам. Затем мы должны были написать парсер, который разбирал его в древовидную структуру в памяти, а затем в нечто, называемое 3-адресным кодом (который похож на ассемблер). Вы вполне можете превратить 3-адресный код в настоящий ассемблер или написать для него интерпретатор.

Поделиться Matt     07 сентября 2010 в 20:35



8

Ага! Это определенно возможно. Другие упоминали книгу о драконах, но в интернете также есть много информации. llvm, например, имеет учебник по реализации языка программирования: http://llvm.org/docs/tutorial/

Поделиться Niki Yoshiuchi     07 сентября 2010 в 20:30



4

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

Поделиться Rohan Singh     07 сентября 2010 в 22:27



3

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

Поделиться Bernard     07 сентября 2010 в 20:27



3

Начните изучать ASM и читать о том, как работает байт-код, и у вас может появиться шанс 🙂

Поделиться Marc Towler     07 сентября 2010 в 20:27



3

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

В ней есть глава, где автор создает интерпретатор «C», в C. Это не академически серьезно, как книга о драконе, но я помню, что она довольно проста, очень практична и легка для понимания, и поскольку вы только начинаете, это будет потрясающее введение в идеи «grammar» для языков и «tokenizing» для программ.

Это было бы идеальным местом для начала. Кроме того, в $0.01 за подержанный экземпляр, дешевле, чем книга Дракона. 😉

Поделиться Ben Zotto     07 сентября 2010 в 20:34



3

Начните с создания парсера. Почитайте о EBNF грамматиках. Это ответит на ваш вопрос о том, как компьютер может читать код. Это очень продвинутая тема, так что не ждите от себя слишком многого, но получайте удовольствие. Некоторые ресурсы, которые я использовал для этого, — это bison, flex и PLY .

Поделиться gtrak     07 сентября 2010 в 20:37



3

Да! Интерес к компиляторам был моим крючком в профессиональном CS (ранее я был на пути к EE и только формально перешел на другую сторону в колледже), это отличный способ узнать TON о широком спектре тем информатики. Вы немного моложе (я учился в средней школе, когда начал дурачиться с парсерами и интерпретаторами), но в наши дни у вас под рукой гораздо больше информации.

Начните с малого: разработайте самый крошечный язык, который только можно придумать, — начните с простого математического калькулятора, который позволяет присваивать и заменять переменные. Когда вам захочется приключений, попробуйте добавить «if» или петли. Забудьте о тайных инструментах, таких как lex и yacc, попробуйте написать простой рекурсивный парсер спуска вручную, возможно, преобразовать его в простые байт-коды и написать интерпретатор для него (избегайте всех трудных частей понимания assembly для конкретной машины, выделения регистров и т. д.). Только с этим проектом вы узнаете огромное количество нового.

Как и другие, я рекомендую книгу «Дракон» (издание 1986 года, Честно говоря, мне не нравится новая).

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

(Примечание: если бы Вы были профессионалом, совет был бы NOT создать новый язык. Это почти никогда не бывает правильным решением. Но как проект для обучения и исследования, это фантастика.)

Поделиться Larry Gritz     08 сентября 2010 в 00:27



1

Если вы хотите действительно общее (но очень хорошо написанное) введение в эту тему-Основы вычислительной техники — я настоятельно рекомендую книгу под названием » Код » Чарльза Петцольда. Он объясняет ряд тем, которые вас интересуют, и оттуда вы можете решить, что вы хотите создать сами.

Поделиться Ulysses     07 сентября 2010 в 21:25


Поделиться cirons42     07 сентября 2010 в 21:44


Похожие вопросы:


Язык программирования GUI

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


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

Возможный Дубликат : Учимся писать компилятор Я огляделся вокруг, пытаясь узнать больше о разработке языка программирования, но не смог найти много информации в интернете. Я нашел несколько…


Вы написали свой собственный эзотерический (или нет) язык? На что это было похоже?

Я видел несколько вопросов, касающихся любимых эзотерических (или нет) языков программирования пользователей stackoverflow. Есть также вопросы, касающиеся реализации языков. Однако мне было…


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

Как бы выглядел ваш собственный (Я полагаю, идеальный) язык программирования? Приведите небольшой пример и объясните свои новые идеи! Меня действительно интересует синтаксис.


Название класса языков программирования, выполняющих собственный код

Как вы называете язык программирования, который может выполнять свой собственный код (передаваемый в виде строкового литерала)? Установка в моем сознании примерно такая (забыв на мгновение набирать…


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

Существует простой интерпретирующий язык программирования и, собственно, консоль interpreter.exe. Нужно сделать раскрашивание синтаксиса, автозаполнение и выполнение нажатием клавиши F5. (если можно…


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

Я создал компилятор в C (используя lex & bison) для динамического типизированного языка программирования, который поддерживает циклы, объявления функций внутри функций, рекурсивные вызовы и т….


Как язык программирования может быть «implemented»?

может быть, это просто небольшое недоразумение, но как можно реализовать язык программирования ? Я говорю не о том, как реализовать свой собственный язык программирования, а о слове implemented? Я…


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

Я хотел бы создать свой собственный язык программирования, ориентированный на JVM. Я не знаю, как это сделать. Должен ли я создать свой собственный компилятор? Есть ли у всех языков программирования…


Почему Neto/Shopify используют свой собственный язык шаблонов?

Почему Neto/Shopify используют свой собственный язык шаблонов вместо использования любого популярного популярного языка ?

11 шагов к созданию языка программирования | GeekBrains

Возможность стать в один ряд с Гвидо ван Россумом и Джеймсом Гослингом.

https://d2xzmw6cctk25h.cloudfront.net/post/1549/og_cover_image/26eb2a82d453f861f8ccffe2f358b171

Мотивы создания нового языка программирования всегда очень разные: кто-то делает это от скуки, кто-то с целью преодоления существующих барьеров, кто-то для собственного удобства. Вы тоже можете попробовать создать собственный язык, руководствуясь следующими 11 пунктами. Кто знает, возможно, вы станете заметной личностью в мире программирования?

Изучите устройство компьютера

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

Изучите терминологию

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

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

Сразу решите, будет ли ваш язык иметь узкую специализацию или ваша цель – универсальный инструмент, который окажется востребован в любой области IT. Оцените объём работы, которой вам предстоит проделать, поставьте цели, которых вы хотите достичь. Ну и самое главное – определитесь: вы хотите покорить мир или просто попробовать для себя что-то новое?

Очертите основные концепции

Есть ряд вопросов, на которые необходимо ответить:

  • Компиляция или интерпретация? Компилируемый код целиком собирается в машинный, после чего исполняется. Интерпретируемый код разбирается и выполняется построчно. Здесь, как и во всех дальнейших вопросах, нет однозначно правильного ответа, вам предстоит выбирать между удобством, функциональностью, безопасностью, производительностью и прочими аспектами.
  • Статическая или динамическая типизация? В первом случае пользователь должен самостоятельно задавать типы данных, во втором – вам придётся описать систему для определения типов.
  • Будет ли язык содержать автоматический сборщик мусора или ручное управление памятью?
  • Какую вы планируете использовать модель программирования: ООП, логическое функциональное, структурное? А может, вы собираетесь изобрести что-то принципиально новое?
  • Будет ли ваш язык поддерживать вставки из других языков программирования?
  • Содержит ли язык базовые функции или все возможности будут поддерживаться из внешних библиотек?
  • Как будет выглядеть архитектура программы?

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

Поэкспериментируйте с синтаксисом

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

Дайте название языку

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

Выберите язык для языка

Новый язык надо на чём-то написать. Суровые гики могут использовать язык ассемблера или машинные коды, но в XXI веке куда больше смысла ориентироваться на высокоуровневые языки: Pascal, C, C++, Swift (компилируемые языки) для интерпретируемого варианта; Java, JavaScript, Python, Ruby (интерпретируемые языки) — для компилируемого. Такие пары обеспечат минимальные потери в производительности.   

Поработайте над лексером и парсером

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

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

Создайте стандартную библиотеку

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

Напишите уйму тестов

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

Опубликуйте язык

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

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

Серия видеоуроков по созданию своего языка программирования на Java без использования генераторов парсеров. По мере выхода уроков, буду обновлять статью.

Репозиторий проекта: https://github.com/aNNiMON/Own-Programming-Language-Tutorial
Плейлист на YouTube: https://www.youtube.com/playli…soWX0qTeQ9_-MFBE552C

#1. Заготовка, калькулятор

#1. Заготовка, калькулятор

#2. Вещественные числа, константы

#2. Вещественные числа, константы

#3. Оператор присвоения, переменные

#3. Оператор присвоения, переменные

#4. Строки, оператор print

#4. Строки, оператор print

#5. Логические выражения, if/else

#5. Логические выражения, if/else

#6. Улучшаем логические выражения и лексер

#6. Улучшаем логические выражения и лексер

#7. Циклы, блок операторов

#7. Циклы, блок операторов

#8. break, continue, цикл do/while

#8. break, continue, цикл do/while

#9. Функции

#9. Функции

#10. Пользовательские функции

#10. Пользовательские функции

#11. Одномерные массивы

#11. Одномерные массивы

#12. Многомерные массивы

#12. Многомерные массивы

#13. Шаблон проектирования «Посетитель» (Visitor)

#13. Шаблон проектирования «Посетитель» (Visitor)

#14. Программируем на OwnLang

#14. Программируем на OwnLang


Также прикрепляю плагин OwnLang для Netbeans. Для установки заходим в меню Tools -> Plugins -> вкладка Downloaded -> Add Plugins и выбираем nbm файл.
  com-annimon-ownlang.nbm

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

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

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

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

Для меня удивительно, но многие люди смотрят на языках программирования как магические. Когда я встречаю людей на вечеринках или что, если они меня спросят, что я делаю, я говорю им, что я Дизайн языки программирования и реализации компиляторов и инструментов, и это удивительно, сколько раз люди-профессиональные программисты, заметь — говорит: «Вау, я никогда не думал об этом, Но да, кто-то же должен эти вещи и». Это’s, как они думали, что языки просто появляются полностью сформированные с инфраструктурой инструмент вокруг их уже.

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

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

Кроме того, рассмотреть вопрос о домене, который вас интересует, а затем разработать предметно-ориентированный язык (DSL), которая определяет пути решения проблем в этой области. Вы упомянули логотип;, что’ы отличный пример DSL для «в линию» и домен. Регулярные выражения-это DSL для С «найти закономерность в строке» и домен. LINQ в C#/VB является DSL для глаз «фильтра, соединения, рода и проектных данных» и домен. HTML-это DSL для глаз «описания расположения текста на странице» и домен, и так далее. Есть много доменов, которые поддаются языковых решений. Одним из моих фаворитов является Inform7, что это DSL для «на основе текста игры приключения на» домен; это, вероятно, самый высокий-уровень серьезный язык программирования, я’ве когда-либо видел. Подобрать домен вам что-то знать и думать о том, как использовать язык для описания проблем и решений в этой области.

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

  1. лексические: какие правила для слов на языке, какие символы являются законными, какие цифры похожи, и так далее.
  2. синтаксический: как сделать слова в языке объединяются в более крупные единицы? В C# более крупные единицы выражения, высказывания, методов, классов, и так далее.
  3. семантический: дана синтаксически правовой программы, как вы выяснить, что программа делает?

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

Один из лучших способов, чтобы начать писать компилятор, написав высокого уровня-язык до высокого уровня-язык компилятор. Написать компилятор, который принимает строки в языке и выплевывает строк в C# или JavaScript или любой другой язык вы не знаете; пусть компилятор для этого языка впоследствии ухаживать за тяжелую работу превратить его в исполняемый код.

Я пишу блог о дизайне с#, VB и VBScript, JavaScript и других языков и инструментов; если эта тема вас интересует, это проверить. http://blogs.msdn.com/ericlippert (историческое) и http://ericlippert.com (текущая)

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

http://blogs.msdn.com/b/ericlippert/archive/2010/02/04/how-many-passes.aspx

Наконец, если вы’вновь ищу работу делаете эти вещи, когда вы’повторно старше на Microsoft в колледже стажер и пытался проникнуть в подразделении Developer. Что’s, как я закончил с моей работой сегодня!

Я написал язык программирования. Вот как вы тоже можете это сделать.

Уильям Уолд

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

  • переменных
  • функций
  • пользовательских структур

Если вам это интересно, посмотрите лендинг Pinecone page или ее репозитория на GitHub.

Я не эксперт. Когда я начинал этот проект, я понятия не имел, что делаю, и до сих пор не понимаю. Я ноль курсов по созданию языков, немного прочитал об этом в Интернете и не следовал многим советам, которые мне давали.

И все же я все же сделал совершенно новый язык. И это работает. Так что я должен что-то делать правильно.

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

Я также коснусь некоторых компромиссов, на которые мне пришлось пойти, и почему я принял эти решения.

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

Начало работы

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

Скомпилированный и интерпретируемый

Существует два основных типа языков: компилируемый и интерпретируемый:

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

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

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

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

Несмотря на то, что Pinecone разрабатывался с учетом компилирования, у него есть полнофункциональный интерпретатор, который какое-то время был единственным способом его запустить. Для этого есть ряд причин, которые я объясню позже.

Выбор языка

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

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

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

Дизайн высокого уровня

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

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

Lexing

Первым шагом в большинстве языков программирования является лексирование или токенизация. «Lex» — это сокращение от лексического анализа, очень красивое слово для разделения кучи текста на токены.Слово «токенизатор» имеет гораздо больше смысла, но слово «лексер» настолько забавно, что я все равно использую его.

Токены

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

Задача лексера

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

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

Flex

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

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

Мое решение

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

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

Парсинг

Второй этап конвейера — это синтаксический анализатор. Парсер превращает список токенов в дерево узлов. Дерево, используемое для хранения данных этого типа, называется абстрактным синтаксическим деревом или AST. По крайней мере, в Pinecone в AST нет информации о типах или о том, какие идентификаторы какие. Это просто структурированные токены.

Обязанности анализатора

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

Bison

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

Почему Custom лучше

С лексером решение использовать мой собственный код было довольно очевидным. Лексер — это такая тривиальная программа, что не написать свою собственную было почти так же глупо, как не написать свой собственный «левый блокнот».

С парсером другое дело. В моем синтаксическом анализаторе Pinecone сейчас 750 строк, и я написал три из них, потому что первые две были мусором.

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

  • Минимизация переключения контекста в рабочем процессе: переключение контекста между C ++ и Pinecone достаточно плохо, не добавляя грамматику Bison
  • Сохраняйте простоту сборки: каждый раз при изменении грамматики Bison должен запускаться перед сборкой . Это можно автоматизировать, но это становится проблемой при переключении между системами сборки.
  • Мне нравится создавать крутое дерьмо: я не создавал Pinecone, потому что думал, что это будет легко, так зачем мне делегировать центральную роль, если я могу делать это сам? Пользовательский парсер может быть нетривиальным, но вполне выполнимым.

Вначале я не был полностью уверен, иду ли я по жизнеспособному пути, но меня вселило уверенность в том, что Уолтеру Брайту (разработчику ранней версии C ++ и создателю языка D) пришлось скажем по теме:

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

Дерево действий

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

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

Дерево действий против AST

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

Запуск дерева действий

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

Параметры компиляции

«Но подождите!» Я слышал, вы говорите: «Разве Pinecone не компилируется?» Да, это.Но компилировать сложнее, чем интерпретировать. Есть несколько возможных подходов.

Build My Own Compiler

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

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

Даже команды, стоящие за Swift, Rust и Clang, не хотят возиться со всем этим в одиночку, поэтому вместо этого все они используют…

LLVM

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

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

Транспилинг

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

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

Future

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

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

Заключение

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

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

  • Если сомневаетесь, переводите. Интерпретируемые языки, как правило, легче проектировать, создавать и изучать.Я не отговариваю вас писать скомпилированный вариант, если вы знаете, что это то, что вы хотите сделать, но если вы стоите на грани, я бы пошел интерпретировать.
  • Когда дело доходит до лексеров и парсеров, делайте все, что хотите. Есть веские аргументы за и против написания собственного. В конце концов, если вы продумаете свой дизайн и все разумно реализуете, это не имеет особого значения.
  • Учитесь на конвейере, с которым я закончил. При разработке того конвейера, который у меня есть сейчас, потребовалось много проб и ошибок.Я попытался устранить AST, AST, которые превращаются в деревья действий на месте, и другие ужасные идеи. Этот конвейер работает, поэтому не меняйте его, если у вас нет действительно хорошей идеи.
  • Если у вас нет времени или мотивации для реализации сложного языка общего назначения, попробуйте реализовать эзотерический язык, такой как Brainfuck. Эти интерпретаторы могут содержать всего несколько сотен строк.

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

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

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

Из всех проектов, которые я сделал, больше всего вопросов о языке программирования Ink. Большинство вопросов делятся на три категории:

  1. Зачем вы сделали язык программирования?
  2. Я хочу создать свой собственный язык программирования — посоветуете?
  3. Почему чернила работают именно так?

Цель этого поста — ответить на вопросы (1) и (2) и предоставить некоторые ресурсы, которые помогут вам начать работу на своем родном языке.Я думаю, что (3) лучше оставить для отдельного, более технического поста.

Этот пост состоит из нескольких разделов.

  1. Зачем?
  2. Проект
  3. Реализация
  4. Прочие соображения
  5. Начните с малого, проявите творческий подход, задавайте вопросы

Зачем?

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

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

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

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

Мир PL широк и глубок; Выбери свои битвы

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

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

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

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

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

Дизайн

Прежде чем вы напишете интерпретатор или компилятор, вам нужно спроектировать язык. Вы можете потратить время на изучение теории категорий, систем типов и парадигм программирования, но лучшее, что вы можете сделать для себя на этом этапе, — это изучить идеи самых разных языков программирования.Не ограничивайтесь только «современными» языками, такими как Rust и Python; вернуться в историю вычислений. Есть богатые идеи, которые нужно изобретать заново и интересно комбинировать, уходя по крайней мере столетие назад в вычисления и математику.

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

  • Какие типы есть в вашем языке? Проверяется ли это во время компиляции? При необходимости он автоматически преобразует типы?
  • Какая единица организации верхнего уровня программ на вашем языке? Языки обычно называют это модулями, пакетами или библиотеками, но некоторые языки могут изобрести свою собственную концепцию, например, Rust Crates.
  • Как язык справляется с исключительными условиями, такими как отсутствие файла, ошибка доступа к сети или ошибка деления на ноль? Вы обрабатываете ошибки как исключения, всплывающие через стек вызовов, или ошибки обрабатываются как значения, как в C и Go?
  • Выполняет ли ваш язык оптимизацию хвостовой рекурсии? Или вы предоставляете собственные инструменты управления потоком для циклов, например для и , а для циклов ?
  • Сколько утилит вы хотите встроить в язык по сравнению со стандартной библиотекой? C, например, ничего не знает о строках — семантика строк обеспечивается стандартной библиотекой C.Карты и списки являются фундаментальными языковыми конструкциями в большинстве языков высокого уровня, но не в большинстве языков низкого уровня.
  • Как ваш язык относится к распределению памяти? Распределяется ли память автоматически по мере необходимости? Нужно ли разработчику для этого писать код? Это сборщик мусора?

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

  • Lua : структура данных, называемая таблицами, программы Lua, использующие строки в качестве байтовых срезов, взаимодействие с C
  • Scheme / Clojure : Метапрограммирование с макросами, гомоиконность, замыкания, поток управления с рекурсией. Несгибаемые Common-Lispers могут не соглашаться, но Scheme и Clojure — самые простые языки в семействе языков Lisp для меня. Вы должны изучить хотя бы один вид Лиспа.
  • Go : структурная типизация с интерфейсами, параллелизм с блокировкой зеленых потоков
  • JavaScript : параллелизм в стиле обратного вызова и асинхронное программирование, первоклассные функции, цикл событий, обещания
  • Awk : Awk — отличный пример небольшого простого языка, оптимизированного для одного случая использования: манипулирования текстовыми файлами и текстовыми данными.Он очень хорошо разработан для этого рабочего процесса и служит источником вдохновения для того, насколько эффективным может быть небольшой предметно-ориентированный язык с простой семантикой.
  • APL / J : APL и J являются языками массивов, которые представляют собой увлекательную семью языков, хорошо известную своей краткостью
  • Ruby : синтаксис. Ruby хорошо известен своим сверхгибким синтаксисом, потому что он легко поддается DSL на основе Ruby, например ActiveRecord.
  • C : C мне нравится больше всего за его простоту и минимализм, а также бескомпромиссную приверженность совместимости
  • Haskell : система типов и параметрический полиморфизм, вариантные типы, частичное приложение и синтаксис типа функции.Как только вы осознаете это, Haskell также станет хорошим местом для начала более глубокого погружения в виды элегантных программ, которые возможны при функциональном программировании.

Реализация

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

Тест-драйв

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

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

Создать интерпретатор / компилятор

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

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

Два моих любимых ресурса по этой теме — пара электронных книг: Crafting Interpreters Роберта Нистрома и Let’s Build A Simple Interpreter Руслана Спивака. Обе серии статей проведут вас от полного новичка в языках программирования к пошаговой разработке и созданию простого интерпретатора. Хотя в этих книгах не будет подробно рассмотрена каждая тема в интерпретации, они дадут вам отправную точку для того, как работает каждый шаг в процессе, достаточно, чтобы привести вас к первому работающему прототипу.

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

Хотя я не читал, я слышал похвалу за пару книг Написание интерпретатора на Go и Написание компилятора на Go .Они проведут вас через процесс создания языка программирования и интерпретатора / компилятора с нуля на языке программирования Go. Как и две электронные книги, представленные выше, они охватывают все основы и потенциальные ловушки и соображения, с которыми вы столкнетесь при написании интерпретатора или компилятора для реалистичного языка, а не просто при создании простого минимального доказательства концепции.

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

С учетом сказанного, вот коллекция дополнительных материалов для чтения в Интернете по интерпретаторам и компиляторам…

Я также большой поклонник отличных технических бесед. Вот некоторые из них, которые мне показались полезными и интересными за эти годы…

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

  • Ale, простой Лисп, написанный на Go
  • Lua, написанный на C.Я написал целую отдельную статью об интересных вариантах дизайна в интерпретаторе Lua, потому что я большой поклонник его архитектуры.
  • Wasm3, интерпретатор для WebAssembly. Мне особенно понравился продуманный и уникальный дизайн интерпретатора байт-кода, описанный в проектном документе в репозитории.
  • Boa, среда выполнения JavaScript и WebAssembly, написанная на Rust

Приведенный здесь список — лишь верхушка айсберга из статей в блогах, тематических исследований и тем GitHub Issues, которые я изучил, чтобы добавить мяса к скелету, который я представлял себе, о том, как работают интерпретаторы и компиляторы.Языки программирования — это глубокая и обширная тема! Не соглашайтесь только на знание простых основ; действительно исследуйте то, что вас интересует, и погрузитесь глубже, даже если поначалу тема кажется сложной.

Прочие соображения

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

Более сложные системы типов. Изучение систем типов пробудило у меня интерес к двум связанным темам: теории категорий и реализации элегантных структур данных с расширенными системами типов на таких языках, как Haskell и Elm. Если вы работаете с Java, JavaScript или Python, изучение того, как типы работают в Swift, TypeScript или Rust, может стать хорошей отправной точкой.

Оптимизация. Как сделать ваш интерпретатор или компилятор быстрее? И что вообще значит быть быстрее? Быстрее разбираетесь и компилируете код? В конце концов, производить более быстрый код? Нет предела известному уровню техники и литературе по теме производительности компилятора.

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

JIT-компиляция. Некоторые из наиболее распространенных и быстрых языковых сред выполнения, такие как Chrome V8 и LuaJIT для Lua, на самом деле являются не полностью ванильными интерпретаторами и не полными компиляторами, а гибридными JIT-компиляторами, которые генерируют скомпилированный машинный код на лету. JIT иногда могут найти лучший компромисс между производительностью и динамизмом времени выполнения на языке программирования, чем простые интерпретаторы или компиляторы, за счет большей сложности компилятора.

Начните с малого, проявите творческий подход, задавайте вопросы

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

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

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


Сохранение сложности

Как я пишу

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

Есть комментарий или ответ? Вы можете написать мне по электронной почте.

Как создать язык программирования с помощью Python?

В этой статье мы узнаем, как создать свой собственный язык программирования с использованием SLY (Sly Lex Yacc) и Python. Прежде чем мы углубимся в эту тему, следует отметить, что это руководство не для новичков, и вам необходимо иметь некоторые знания о предпосылках, указанных ниже.

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

Начало работы

Установите SLY для Python. SLY — это инструмент для лексирования и синтаксического анализа, который значительно упрощает наш процесс.

 pip install хитрый
 

Построение лексера

Первая фаза компилятора — преобразовать все символьные потоки (написанная высокоуровневая программа) в токен-потоки.Это делается с помощью процесса, называемого лексическим анализом. Однако этот процесс упрощается с помощью SLY

. Сначала давайте импортируем все необходимые модули.

Теперь давайте создадим класс BasicLexer , который расширяет класс Lexer от SLY. Давайте создадим компилятор, выполняющий простые арифметические операции. Таким образом, нам понадобятся некоторые базовые токены, такие как NAME , NUMBER , STRING . В любом языке программирования между двумя символами будет пробел.Таким образом, мы создаем литерал игнорировать . Затем мы также создаем базовые литералы, такие как ‘=’, ‘+’ и т. Д., NAME токенов — это в основном имена переменных, которые могут быть определены регулярным выражением [a-zA-Z _] [a-zA-Z0- 9 _] *. СТРОКА токенов — это строковые значения, заключенные в кавычки («»). Это можно определить с помощью регулярного выражения \ ”. *? \”.

Всякий раз, когда мы находим цифру / с, мы должны присвоить ее токену НОМЕР , и это число должно быть сохранено как целое число.Мы делаем базовый программируемый скрипт, так что давайте просто сделаем его с целыми числами, однако не стесняйтесь расширять его для десятичных, длинных и т. Д. Мы также можем делать комментарии. Всякий раз, когда мы находим «//», мы игнорируем все, что идет дальше в этой строке. То же самое делаем с символом новой строки. Таким образом, мы создали базовый лексер, который преобразует поток символов в поток токенов.

Python3

класс BasicLexer (Lexer):

токенов = {ИМЯ, НОМЕР, СТРОКА 2 902 \ t '

литералов = { ' = ' , ' + ' , ' - ' , 3,

'*' , '(' , ')' , ',' , ';' № ] * '

СТРОКА = r ' \ ".*? \ "'

@_ (r ' \ d + ' )

def , t):

t.value = int (t.value)

возврат

@_ (r '//.* ' )

def КОММЕНТАРИЙ ( self , t):

проход

    02 902

      02 902 902 @_ (r '\ n +' )

      def перевод строки ( self , t):

      self. self.Lineno = t.value.count ( '\ n' )

Создание синтаксического анализатора

Сначала давайте импортируем все необходимые модули.

Теперь давайте создадим класс BasicParser , который расширяет класс Lexer . Поток токенов от BasicLexer передается переменной токенов. Определен приоритет, который одинаков для большинства языков программирования. Большая часть синтаксического анализа, написанного в приведенной ниже программе, очень проста.Когда ничего нет, утверждение ничего не передаёт. По сути, вы можете нажать Enter на клавиатуре (ничего не вводя) и перейти к следующей строке. Затем ваш язык должен понимать задания, в которых используется знак «=». Это обрабатывается в строке 18 программы ниже. То же самое можно сделать при присвоении строки.

Python3

класс BasicParser (Parser):

токенов = BasicLexer.токены

приоритет = (

( 'левый' 1, '+' 9026 '+' 9026

( 'левый' , '* , ' / ' ),

( 902 ( '2 ' справа UMINUS ' ),

)

def __init __ ( self 1 env = {}

@_ ('')

def заявление ( 1 само по себе ): проход

@_ ( 'var_assign' )

def 2 возврат р.var_assign

@_ ( 'NAME "=" expr' )

def

возврат ( 'var_assign' , p.NAME, p.expr)

@_ ( "НАЗВАНИЕ ' )

def var_assign ( self , p):

return ( 'var_assign' , p.НАЗВАНИЕ, стр.

возврат (p.expr)

@_ ( 'expr "+" expr' ) def ( self , p):

return ( 'add' , p.expr0, p.expr1)

@_ ( 'expr "-" expr' )

def p):

возврат ( 'sub' , p.expr0, p.expr1)

@_ ( "expr ' )

def expr ( self , p):

return ( ' mul ' 902expr0, p.expr1)

@_ ( 'expr "/" expr' )

def p):

возврат ( 'div' , p.expr0, p.expr1)

@_ - "( " expr% prec UMINUS ' )

def expr ( self , p):

return p.expr

@_ ( «ИМЯ» )

def expr ( само по себе ) возврат ( 'var' , p.NAME)

@_ ( 'НОМЕР' )

    03 def261 902 self , p):

    return ( 'num' , p.НОМЕР)

Синтаксический анализатор также должен выполнять синтаксический анализ в арифметических операциях, это можно сделать с помощью выражений. Допустим, вам нужно что-то вроде показанного ниже. Здесь все они построчно преобразуются в поток токенов и построчно анализируются. Следовательно, согласно приведенной выше программе, a = 10 похоже на строку 22. То же самое для b = 20. a + b напоминает строку 34, которая возвращает дерево синтаксического анализа (‘add’, (‘var’, ‘a’), (‘var’, ‘b’)).


 Язык GFG> a = 10
Язык GFG> b = 20
Язык GFG> a + b
30
 

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

Execution

Устный перевод - это простая процедура. Основная идея состоит в том, чтобы пройти по дереву и иерархически оценить арифметические операции. Этот процесс рекурсивно вызывается снова и снова, пока не будет оценено все дерево и не будет получен ответ. Скажем, например, 5 + 7 + 4. Этот символьный поток сначала токенизируется в токен-поток в лексере. Затем поток токенов анализируется для формирования дерева синтаксического анализа. Дерево синтаксического анализа по существу возвращает (‘add’, (‘add’, (‘num’, 5), (‘num’, 7)), (‘num’, 4)).(см. изображение ниже)

Интерпретатор сначала добавит 5 и 7, а затем рекурсивно вызовет walkTree и прибавит 4 к результату сложения 5 и 7. Таким образом, мы получим 16. Приведенный ниже код действительно тот же процесс.

Python3

класс BasicExecute:

def __init __ ( 3 само, дерево .env = env

результат = self .walkTree (tree)

результат 2 2 результат 2 isinstance (результат, int ):

print (результат)

if isinstance 9026r260 (результат) результат [ 0 ] = = '"' :

печать (результат)

def ( сам , узел):

9 0002 если isinstance (узел, int ):

возврат узел

узел 9026 ):

возврат узел

если узел это нет

    0
      03
        03

        , если узел [ 0 ] = = «программа» :

        если 2 узел 1 = Нет :

        сам .walkTree (узел [ 2 ])

        еще :

        сам .walkTree (узел [

          0 1 3 3 3 ]) .walkTree (узел [ 2 ])

          если узел [ 0 ] = 1

          возврат узел [ 1 ]

          если узел [ 0 ] = = = = = = = = = =

          возврат узел [ 1 ]

          если узел [ 0 ] = = 'добавить' :

          возврат возврат walkTree (узел [ 1 ]) + self .walkTree (узел [ 2 ])

          elif node60 [ node60] = = 'sub' :

          возврат self .walkTree (node ​​[ 1 ]) - (self .walk1 self self self. 2 ])

          elif узел [ 0 ] = = 'mul' :

            03
              01 возврат walkTree (узел [ 1 ]) * сам .walkTree (узел [ 2 ])

              elif node60 [ node60] = = 'div' :

              возврат self .walkTree (node ​​[ 1 ]) / (self .walk1 self self 2 ])

              если узел [ 0 ] = = 'var_assign' 902 'var_assign' 902 902 .env [узел [ 1 ]] = self .walkTree (node ​​[ 2 ])

              возврат узел [ 2601 260 узел 1 260

              если узел [ 0 ] ] = = 'var' :

              3 попробовать возврат: сам .env [node [ 1 ]]

              за исключением LookupError:

              print ( «Неопределенная переменная '» ] + «'found!» )

              return 0

Отображение вывода

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

Python3

if __name__ = = '__main__' :

базовый лексер = BasicParser ()

печать ( 'Язык GFG' )

ENV

2

1

3 902 при True :

try :

текст = ввод ' ' ' ' '

кроме EOFError:

разрыв

если текст:

деревоparse (lexer.tokenize (text))

BasicExecute (tree, env)

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

Выполните программу, которую вы написали, используя

 python you_program_name.py
 

Сноски

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

Внимание компьютерщик! Укрепите свои основы с помощью курса Python Programming Foundation и изучите основы.

Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS .И чтобы начать свое путешествие по машинному обучению, присоединяйтесь к Машинное обучение - курс базового уровня

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

Куинн Домбровски на Flickr

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

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

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

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

Дизайн и реализация

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

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

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

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

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

 для i в диапазоне (0,10):
    печать (я)
 

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

 forLoop = For (Var ("i"),
Функция ("диапазон", Int (0), Int (10)),
BuiltIn ("печать", Var ("i")))
 

, где For, Var, Function, Int и BuiltIn - это классы, которые должен был создать писатель интерпретатора.Вы можете представить структуру программы как что-то вроде

Пример абстрактного синтаксического дерева (AST)

Затем, как только интерпретатор создал этот AST, он выполнит код. Это означает разделение объектов, представляющих программу, и выполнение соответствующих действий. Цикл for превратится в нечто повторяющееся. Переменные становятся отложенными данными, которые можно будет получить позже. Встроенные операции, такие как печать, будут записывать вывод в консоль. В данном случае это будет немного тривиально, потому что концепции Python легко перевести в код Python.Но если вы писали интерпретатор Python в чем-то вроде Haskell, цикл Python выполняется как функция Haskell.

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

Вот основные шаги и порядок, которые я рекомендую для написания языка программирования:

  • Создание вашего языка
  • Создание AST для языка
  • Написание кода для выполнения AST
  • Выбор языка
  • Написание парсера

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

Создание вашего языка

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

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

  • Как вы повторяете на своем языке? То есть как выполнить одни и те же шаги несколько раз?
  • Как вы делаете выбор на своем языке? Вам понадобится способ принимать решения о том, когда что-то должно произойти.Большинство языков делают это с помощью некоторой формы оператора if.
  • Какие данные у вас будут: числа, строки, списки и т. Д.?
  • Как будут работать функции?
  • Вы хотите иметь возможность создавать параллельные потоки?
  • Есть ли языки, которые вас вдохновляют?
  • Есть ли языки, которые вы почти любите, но хотели бы исправить?

Можно подумать и о других дизайнерских решениях, но это хорошее начало.

Выбор того, как должен выглядеть ваш язык

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

Хорошая идея - «подделать» некоторые программы на вашем новом языке ручкой и бумагой, а затем делать заметки о том, что они должны делать.

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

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

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

Узнать больше

Учебник по созданию простого интерпретатора в Python (старый)

http://www.norvig.com/lispy.html

Больше деталей, меньше дизайна

https://ruslanspivak.com/lsbasi-part1/

Haskell и написание простого интерпретатора

https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours

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

https://www.kidscodecs.com/build-a-programming-language-1/
https: // www.kidscodecs.com/designing-programming-language-part-ii/

Итак, я создал язык программирования | Чираг Ханделвал | Young Coder

Мне все еще кажется странным (и удивительным) сказать, что я действительно создал язык программирования. Вот небольшая часть моего путешествия и обзор языкового дизайна для Ethereal .

Ethereal - Simple Factorial Program

Я первым признаю, что, вероятно, не очень хорош в системном программировании. Я не специалист в области языкового дизайна и понятия не имел, как создать язык.У меня действительно был большой интерес к его созданию. Компиляторы, интерпретаторы и языки увлекали меня в течение долгого времени, и я всегда хотел знать, каково это - писать код и понимать, что код написан на моем родном языке. (Спойлер: кажется, GOOOD !)

Компиляторы и интерпретаторы, такие как GCC, LLVM, CPython и т. Д., Являются поистине изысканными частями кода, которые - даже для меня - совершенно ошеломляют. Но построить свой собственный язык возможно.

Я пишу маленькие и эзотерические языки (Alacrity Lang, ESIL) около полутора лет, но все они были очень ограничены в своих возможностях, возможностях и архитектуре. Но на этот раз мне нужен интерпретируемый язык (в основном) общего назначения. Так родился Ethereal.

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

Ethereal - это интерпретируемый язык, который переводит данный исходный код в байт-код и запускает его на настраиваемой виртуальной машине на основе стека. Его синтаксис вдохновлен C и Python и основан на упрощении по своей природе, таком как C, при этом эстетически приятный синтаксис, как у Python.Лично я всегда предпочитал использовать фигурные скобки для определения блоков кода вместо отступов, и это то, что я здесь использовал. Внутренне Ethereal не заботится о строках или отступах для чтения исходного кода (аналогично C).

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

  1. Переменные, функции, условные выражения, циклы, перечисления, структуры - обычные функции-члены
  2. (в некотором роде) для структур - функции, которые работают для определенных структур / типов и вызываются. с использованием оператора точки (как в языках ООП)
  3. Функции и типы в C ++ (или C) с использованием модулей или в самом Ethereal с использованием структур и импорта
  4. Перегрузка функций - на основе количества аргументов и типов для внутренних (модульных) функций; и на основе количества аргументов для функций, созданных в Ethereal
  5. Динамическая типизация
  6. Стандартная библиотека, состоящая из базовой консоли и файлового ввода-вывода и важных структур данных - векторов, карт, наборов, дополнительных элементов (аналогично указателям)

Поддерживает Linux , macOS, BSD и Android прямо из коробки (дополнительную информацию см. в репозитории Git), и есть планы по возможной поддержке Windows.

Чаще всего мне задают вопрос, почему я решил создать интерпретируемый язык вместо скомпилированного. Изначально я немного об этом думал. Я понял, что могу позволить себе пожертвовать производительностью, которую дают компилируемые языки, для создания интерпретируемого языка. Если бы я создал скомпилированный язык, я бы, скорее всего, использовал API-интерфейсы LLVM для создания серверной части компилятора (оптимизации и генерации кода). Но для этого проекта я хотел создать всю реализацию самостоятельно (и я пока не хотел заниматься созданием ассемблерного кода).

Наконец, создание генератора байт-кода и виртуальной машины показалось более увлекательным!

Мне нравился C, когда я начинал программировать, а когда я перешел на C ++, пути назад уже не было. Так что для меня выбор языка был более или менее несуществующим. Мне нравится C ++, и я выбрал его в качестве языка для создания справочного интерпретатора в мгновение ока. Поскольку он по своей сути обеспечивает высокую производительность (при условии, что кто-то пишет достойный код), мне не нужно было бы слишком беспокоиться о том, что мой код работает медленно.

Кроме того, гораздо лучше написать интерпретатор языка на компилируемом языке. Интерпретируемые языки медленнее компилируемых. Создание интерпретируемого языка на другом интерпретируемом языке (например, Python, Ruby и т. Д.) Было бы слишком медленным.

Возьмем небольшой пример программы:

Интерпретатор языка состоит из 4 основных компонентов:

1. Lexer - преобразует предоставленный исходный код в отдельные, отдельные токены, распознаваемые языком

Lexical Tokens - Sample Program

2.Синтаксический анализатор - преобразует последовательность токенов в дерево синтаксического анализа, которое обеспечивает значимый формат, в письменный код в терминах дерева синтаксического анализа Ethereal

- пример программы

3. Генератор байт-кода - преобразует дерево синтаксического анализа в последовательность пользовательских инструкций байт-кода

Байт-код - пример программы

4. Виртуальная машина - выполняет сгенерированную последовательность байт-кода для получения окончательного результата / вывода (здесь 15 )

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

  1. Лексер - Довольно простой
  2. Генератор байт-кода
  3. - В основном хорошо, было трудно сгенерировать байт-код для выражений
  4. Парсер - Немного сложнее, особенно при синтаксическом анализе выражений, но и в целом
  5. Виртуальная машина - потребовалось больше всего, в основном из-за все внутренние компоненты, такие как управление памятью, управление переменными (и областью видимости) и т. д.

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

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

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

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

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

С помощью этой функции создается вся основная библиотека числовой и логической арифметики. Когда мы пишем что-то вроде a + b , оно фактически вызывает функцию с именем + для a & b (см. Выходные данные генератора байт-кода выше - ID от 3 до 6).

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

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

Я надеюсь, что это было интересное чтение для всех вас.Языковой дизайн считается очень узкой, туманной и сложной темой, и - не поймите меня неправильно - это определенно так. Компиляторы и интерпретаторы, такие как GCC, LLVM, CPython и т. Д., Являются поистине чудесными, гениальными и изысканными фрагментами кода, которые даже для меня просто ошеломляют. Но это не невозможно, и я люблю все это понимать.

Так что, если вы интересуетесь языковым дизайном и разработкой, обязательно попробуйте. Это невероятный опыт обучения и абсолютное удовольствие работать.И даже не заставляйте меня испытывать блаженное чувство написания кода на вашем родном языке ❤️.

Ниже приведены ссылки на Ethereal и другие языки, над которыми я работал. Если вам интересно, пачкайте руки!

Спасибо за внимание!

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

Создание компилятора Bolt: Часть 1

10 мая 2020 г.

6 мин чтения

Серия: Создание компилятора Bolt


На приведенной выше диаграмме показан компилятор для языка Bolt, который мы будем создавать.Что означают все этапы? Мне нужно изучить OCaml и C ++? Подождите, я даже не слышал об OCaml…

Не волнуйтесь. Когда я начал этот проект 6 месяцев назад, я никогда не создавал компилятор и не использовал OCaml или C ++ в каких-либо серьезных проектах. Я все объясню в свое время. Вопрос, который мы действительно должны задать: , зачем создавать свой собственный язык ? Возможные ответы:

  1. Это весело
  2. Круто иметь свой собственный язык программирования
  3. Это хороший побочный проект

Ментальные модели

Хотя все три из них (или ни одна!) Могут быть правдой, есть более крупный вариант. мотивация: правильные ментальных моделей .Видите ли, когда вы изучаете свой первый язык программирования, вы смотрите на программирование через призму этого языка. Перенесемся на второй язык, и это кажется трудным, вам придется заново учить синтаксис, а этот новый язык работает по-другому. Используя больше языков программирования, вы понимаете, что эти языки имеют общие темы. В Java и Python есть объекты, в Python и JavaScript не нужно писать типы, список можно продолжить. Углубляясь в теорию языков программирования, вы читаете о существующих языковых конструкциях: Java и Python - объектно-ориентированных языков программирования, , а Python и JavaScript - , с динамической типизацией .

Языки программирования, которые вы использовали, на самом деле основаны на идеях, представленных в более старых языках, о которых вы, возможно, не слышали. Simula и Smalltalk представили концепцию объектно-ориентированных языков программирования. Lisp представил концепцию динамической типизации. И все время появляются новые исследовательские языки, которые вводят новые концепции. Более распространенный пример: Rust встраивает безопасности памяти в язык системного программирования низкого уровня.

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

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

Итак, вы создали свой модный новый язык, и он собирается произвести революцию в мире, но есть одна проблема. Как это запустить? Это роль компилятора. Чтобы объяснить, как работают компиляторы, давайте сначала вернемся в XIX век, в век телеграфа.У нас есть новый модный телеграф, но как отправлять сообщения? Та же проблема, другой домен. Телеграфисту необходимо принять речь, преобразовать ее в азбуку Морзе и набрать код. Первое, что делает оператор, это разбирает речь - они разбивают ее на слова (, лексика ), а затем понимают, как эти слова используются в предложении (, синтаксический анализ ) - являются ли они частью именной группы, придаточное предложение и т. д. Они проверяют, имеет ли это смысл, классифицируя слова по категориям или типов (прилагательное, существительное, глагол) и проверяют, имеет ли предложение грамматический смысл (мы не можем использовать «пробеги» для описания существительного, поскольку это глагол не существительное).Наконец, они переводят ( - ) каждое слово в точки и тире (азбука Морзе), которые затем передаются по сети.

Похоже, это работает, потому что большая часть этого автомат для людей. Компиляторы работают таким же образом, за исключением того, что мы должны явно программировать компьютеры для этого. В приведенном выше примере описывается простой компилятор, состоящий из 4 этапов: lex, синтаксический анализ, проверка типа и затем перевод в машинные инструкции. Оператору также требуются некоторые дополнительные инструменты для фактического ввода кода Морзе; для языков программирования это среда выполнения .

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

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

На самом деле мы можем сформировать множество языков и дизайн компилятора в терминах приведенной выше аналогии:

Переводит ли оператор слова на лету в азбуку Морзе по мере их передачи, или они преобразуют слова в азбуку Морзе заранее, а затем передать азбуку Морзе? Интерпретация языков, таких как Python, делает первое, в то время как опережающих времен скомпилировали языков, таких как C (и Bolt), делают второе.На самом деле Java находится где-то посередине - он использует своевременный компилятор , который выполняет большую часть работы заранее, переводя программы в байт-код, а затем во время выполнения компилирует байт-код в машинный код.

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

Статическая или динамическая типизация? В первом случае оператор либо проверяет грамматический смысл слов до того, как они начнут нажимать. Или они этого не делают, а затем на полпути они говорят: «Ага, в этом нет смысла» и останавливаются.С динамической типизацией можно быстрее экспериментировать (например, Python, JS), но когда вы отправляете это сообщение, вы не знаете, остановится ли оператор на полпути (сбой).

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

Типы

Самая интересная часть компилятора (на мой взгляд) - проверка типов. В нашей аналогии оператор классифицировал слова как части речи (прилагательные, существительные, глаголы), а затем проверял, правильно ли они использовались. Типы работают одинаково, мы классифицируем программные ценности на основе того поведения, которое мы хотим, чтобы они имели. Например. int для чисел, которые можно умножать вместе, String для потоков символов, которые могут быть объединены вместе. Роль средства проверки типов состоит в том, чтобы предотвратить нежелательное поведение - например, объединение int s или умножение String s вместе - эти операции не имеют смысла, поэтому их нельзя допускать.С типом , проверяющим , программист аннотирует значения типами, а компилятор проверяет их правильность. При выводе типа компилятор и определяет, и проверяет типы. Мы называем правила проверки типов суждениями о типе , и их совокупность (вместе с самими типами) образует систему типов.

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

Присоединяйтесь к моему информационному бюллетеню, чтобы получать больше подобных материалов!

Подписчики электронной почты сначала получают эксклюзивный доступ к последним сообщениям!

Куда подходит Bolt?

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

Если мы сейчас оглянемся на конвейер, то увидим, что Bolt содержит фазы лексирования, синтаксического анализа и обессахаривания / понижения. Он также содержит несколько этапов сериализации и десериализации Protobuf: они предназначены исключительно для преобразования между OCaml и C ++.Он нацелен на LLVM IR, затем мы связываем пару библиотек времени выполнения (pthreads и libc) и, наконец, выводим наш объектный файл , двоичный файл, содержащий машинный код.

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

А что с этой серией?

Эту серию можно рассматривать с двух точек зрения: во-первых, мы будем обсуждать дизайн языка и по ходу сравнивать Bolt с Java, C ++ и другими языками. Во-вторых, это практическое пошаговое руководство по созданию собственного компилятора. В отличие от многих руководств по созданию собственного компилятора, в которых рассказывается, как создать игрушечный язык , некоторые темы, рассматриваемые в этом руководстве, образуют основу для параллельных объектно-ориентированных языков, таких как Java: как реализованы классы, как работает наследование , общие классы и даже то, как параллелизм реализован изнутри.

Bolt также не выводит инструкции для игрушек, а вместо этого нацелен на LLVM IR . С практической точки зрения это означает, что Bolt подключается к потрясающим оптимизациям, присутствующим в компиляторах C / C ++. LLVM API - это мощный инструмент, но в нем также очень сложно ориентироваться в документации. Я провел много ночей в обратном проектировании программ на C ++ - надеюсь, эта серия статей избавит хотя бы одного человека от этой боли!

В следующей части мы рассмотрим практические аспекты настройки проекта компилятора - я пройдусь по репозиторию Bolt и объясню , почему мы используем OCaml всех языков для интерфейса.

index-of.es/

 Название Размер
 Android / -
 Галерея искусств/                  -
 Атаки / -
 Переполнение буфера / -
 C ++ / -
 CSS / -
 Компьютер / -
 Конференции / -
 Растрескивание / -
 Криптография / -
 Базы данных / -
 Глубокая сеть / -
 Отказ в обслуживании/            -
 Электронные книги / -
 Перечисление / -
 Эксплойт / -
 Техники неудачной атаки / -
 Судебная экспертиза / -
 Галерея / -
 HTML / -
 Взломать / -
 Взлом-веб-сервер / -
 Взлом беспроводных сетей / -
 Взлом / -
 Генератор хешей / -
 JS / -
 Ява/                         -
 Linux / -
 Отмыкание/                  -
 Журналы / -
 Вредоносное ПО / -
 Метасплоит / -
 Разное / -
 Разное / -
 Протоколы сетевой безопасности / -
 Сеть / -
 ОПЕРАЦИОННЫЕ СИСТЕМЫ/                           -
 Другое / -
 PHP / -
 Perl / -
 Программирование / -
 Python / -
 RSS / -
 Rdbms / -
 Разобрать механизм с целью понять, как это работает/          -
 Рубин/                         -
 Сканирование сетей / -
 Безопасность/                     -
 Захват сеанса / -
 Снифферы / -
 Социальная инженерия/           -
 Поддерживает / -
 Системный взлом / -
 Инструменты/                        -
 Учебники / -
 UTF8 / -
 Unix / -
 Вариос-2 / -
 Варианты / -
 Видео/                       -
 Вирусы / -
 Окна / -
 Беспроводная связь / -
 Xml / -
 z0ro-Репозиторий-2 / -
 z0ro-Репозиторий-3 / -
 
.