Как написать простейший компилятор
Лучший способ понять как работает компилятор — написать свой собственный. В этом поможет этот краткий, но исчерпывающий гайд.
Введение
Стандартный компилятор осуществляет следующие шаги:
- Парсинг: исходный текст конвертируется в абстрактное синтаксическое дерево (Abstract Syntax Tree, AST).
- Разрешение зависимостей с другими модулями (С откладывает этот этап на шаг линковки).
- Семантическая валидация: исключение синтаксически корректных, но бессмысленных выражений, например, повторного объявления переменных.
- Эквивалентные преобразования и высокоуровневая оптимизация: AST преобразуется для осуществления более эффективных вычислений при той же семантике.
- Генерация кода: AST трансформируется в линейный код низкого уровня с переходами, распределением регистров и тому подобным.
- Локальная оптимизация: низкоуровневый код проверяется на простые локальные недостатки.
В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).
После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.
Запомните основные моменты
Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.
Читайте книги!
Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.
Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.
Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.
Хорошо определите свой язык
Вы можете использовать любую нотацию, но будьте уверены, что имеете полное и последовательное описание языка. Оно включает в себя как синтаксис, так и семантику.
Используйте свой любимый язык
Это совершенно нормально — писать компилятор на Pyhton, Ruby или любом другом языке, который вам нравится. Используйте простые алгоритмы, принцип которых вы хорошо понимаете. Первый ваш компилятор вовсе не обязан быть быстрым, или эффективным, или обладать кучей фич. Все, что от него требуется — работать достаточно правильно и легко поддаваться переработкам.
Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.
Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.
Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.
Сделайте хороший парсер
Парсеров существует огромное количество, выбирайте любой. Можно написать свой собственный, но это сработает только в том случае, если синтаксис вашего языка примитивен до маразма.
Парсер должен выявлять синтаксически ошибки и сообщать о них. Пишите много тестов, как позитивных, так и негативных. Переиспользуйте написанный код для определения языка.
На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».
Напишите семантический валидатор
Вполне вероятно, что ваш язык допускает синтаксически правильные конструкции, не имеющие смысла в некоторых контекстах. Примером может служить повторное объявление одной и той же переменной или пропуск параметра неправильного типа. Валидатор призван выявлять ошибки такого рода.
Также зона его ответственности охватывает разрешение зависимостей с другими модулями, написанными на вашем языке, загрузкой этих модулей и использовании их в процессе валидации. Например, именно на этом этапе проверяется соответствие количества параметров, поступающих на вход функции из подключаемого модуля.
Еще раз, пишите и запускайте много тестов. Тривиальные случаи также обязательны к рассмотрению, как и сложные.
Генерируйте код
Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условны й оператор) в слабо параметризированный шаблон кода.
Забудьте об эффективности и сосредоточьтесь только на правильности.
Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.
- LLVM: позволяет эффективно генерировать машинный код, чаще всего для х86 и ARM.
- CLR: ориентирована на .NET.
- JVM: нацелена на мир Java, мультиплатформенна.
Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.
Конечно, некоторая простая оптимизация вполне уместна на начальном этапе. Но старайтесь избегать излишних хитростей, пока ваш компилятор не будет достаточно стабилен.
Источник статьи: http://proglib.io/p/how-to-write-a-plain-compiler/
Как создать свой язык программирования: теория, инструменты и советы от практика
На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием Pinecone. Я не рискну назвать его законченным, но использовать его уже можно — он содержит для этого достаточно элементов, таких как переменные, функции и пользовательские структуры данных. Если хотите ознакомиться с ним перед прочтением, предлагаю посетить официальную страницу и репозиторий на GitHub.
Введение
Я не эксперт. Когда я начал работу над этим проектом, я понятия не имел, что делаю, и всё еще не имею. Я никогда целенаправленно не изучал принципы создания языка — только прочитал некоторые материалы в Сети и даже в них не нашёл для себя почти ничего полезного.
Тем не менее, я написал абсолютно новый язык. И он работает. Наверное, я что-то делаю правильно.
В этой статье я постараюсь показать, каким образом Pinecone (и другие языки программирования) превращают исходный код в то, что многие считают магией. Также я уделю внимание ситуациям, в которых мне приходилось искать компромиссы, и поясню, почему я принял те решения, которые принял.
Текст точно не претендует на звание полноценного руководства по созданию языка программирования, но для любознательных будет хорошей отправной точкой.
Первые шаги
«А с чего вообще начинать?» — вопрос, который другие разработчики часто задают, узнав, что я пишу свой язык. В этой части постараюсь подробно на него ответить.
Компилируемый или интерпретируемый?
Компилятор анализирует программу целиком, превращает её в машинный код и сохраняет для последующего выполнения. Интерпретатор же разбирает и выполняет программу построчно в режиме реального времени.
Технически любой язык можно как компилировать, так и интерпретировать. Но для каждого языка один из методов подходит больше, чем другой, и выбор парадигмы на ранних этапах определяет дальнейшее проектирование. В общем смысле интерпретация отличается гибкостью, а компиляция обеспечивает высокую производительность, но это лишь верхушка крайне сложной темы.
Я хотел создать простой и при этом производительный язык, каких немного, поэтому с самого начала решил сделать Pinecone компилируемым. Тем не менее, интерпретатор у Pinecone тоже есть — первое время запуск был возможен только с его помощью, позже объясню, почему.
Прим. перев. Кстати, у нас есть краткий обзор серии статей по созданию собственного интерпретатора — это отличное упражнение для тех, кто изучает Python.
Выбор языка
Своеобразный мета-шаг: язык программирования сам является программой, которую надо написать на каком-то языке. Я выбрал C++ из-за производительности, большого набора функциональных возможностей, и просто потому что он мне нравится.
Но в целом совет можно дать такой:
- интерпретируемый ЯП крайне рекомендуетсяписать на компилируемом ЯП (C, C++, Swift). Иначе потери производительности будут расти как снежный ком, пока мета-интерпретатор интерпретирует ваш интерпретатор;
- компилируемый ЯП можно писать на интерпретируемом ЯП (Python, JS). Возрастёт время компиляции, но не время выполнения программы.
Проектирование архитектуры
У структуры языка программирования есть несколько ступеней от исходного кода до исполняемого файла, на каждой из которых определенным образом происходит форматирование данных, а также функции для перехода между этими ступенями. Поговорим об этом подробнее.
Лексический анализатор / лексер
Строка исходного кода проходит через лексер и превращается в список токенов.
Первый шаг в большинстве ЯП — это лексический анализ. Говоря по-простому, он представляет собой разбиение текста на токены, то есть единицы языка: переменные, названия функций (идентификаторы), операторы, числа. Таким образом, подав лексеру на вход строку с исходным кодом, мы получим на выходе список всех токенов, которые в ней содержатся.
Обращения к исходному коду уже не будет происходить на следующих этапах, поэтому лексер должен выдать всю необходимую для них информацию.
При создании языка первым делом я написал лексер. Позже я изучил инструменты, которые могли бы сделать лексический анализ проще и уменьшить количество возникающих багов.
Одним из основных таких инструментов является Flex — генератор лексических анализаторов. Он принимает на вход файл с описанием грамматики языка, а потом создаёт программу на C, которая в свою очередь анализирует строку и выдаёт нужный результат.
Моё решение
Я решил оставить написанный мной анализатор. Особых преимуществ у Flex я в итоге не увидел, а его использование только создало бы дополнительные зависимости, усложняющие процесс сборки. К тому же, мой выбор обеспечивает больше гибкости — например, можно добавить к языку оператор без необходимости редактировать несколько файлов.
Синтаксический анализатор / парсер
Список токенов проходит через парсер и превращается в дерево.
Следующая стадия — парсер. Он преобразует исходный текст, то есть список токенов (с учётом скобок и порядка операций), в абстрактное синтаксическое дерево, которое позволяет структурно представить правила создаваемого языка. Сам по себе процесс можно назвать простым, но с увеличением количества языковых конструкций он сильно усложняется.
Bison
На этом шаге я также думал использовать стороннюю библиотеку, рассматривая Bison для генерации синтаксического анализатора. Он во многом похож на Flex — пользовательский файл с синтаксическими правилами структурируется с помощью программы на языке C. Но я снова отказался от средств автоматизации.
Преимущества кастомных программ
С лексером моё решение писать и использовать свой код (длиной около 200 строк) было довольно очевидным: я люблю задачки, а эта к тому же относительно тривиальная. С парсером другая история: сейчас длина кода для него — 750 строк, и это уже третья попытка (первые две были просто ужасны).
Тем не менее, я решил делать парсер сам. Вот основные причины:
- минимизация переключения контекста;
- упрощение сборки;
- желание справиться с задачей самостоятельно.
В целесообразности решения меня убедило высказывание Уолтера Брайта (создателя языка D) в одной из его статей:
Я бы не советовал использовать генераторы лексических и синтаксических анализаторов, а также другие так называемые «компиляторы компиляторов». Написание лексера и парсера не займёт много времени, а использование генератора накрепко привяжет вас к нему в дальнейшей работе (что имеет значение при портировании компилятора на новую платформу). Кроме того, генераторы отличаются выдачей не релевантных сообщений об ошибках.
Абстрактный семантический граф
Переход от синтаксического дерева к семантическому графу
В этой части я реализовал структуру, по своей сути наиболее близкую к «промежуточному представлению» (intermediate representation) в LLVM. Существует небольшая, но важная разница между абстрактным синтаксическим деревом (АСД) и абстрактным семантическим графом (АСГ).
АСГ vs АСД
Грубо говоря, семантический граф — это синтаксическое дерево с контекстом. То есть, он содержит информацию наподобие какой тип возвращает функция или в каких местах используется одна и та же переменная. Из-за того, что графу нужно распознать и запомнить весь этот контекст, коду, который его генерирует, необходима поддержка в виде множества различных поясняющих таблиц.
Запуск
После того, как граф составлен, запуск программы становится довольно простой задачей. Каждый узел содержит реализацию функции, которая получает некоторые данные на вход, делает то, что запрограммировано (включая возможный вызов вспомогательных функций), и возвращает результат. Это — интерпретатор в действии.
Варианты компиляции
Вы, наверное, спросите, откуда взялся интерпретатор, если я изначально определил Pinecone как компилируемый язык. Дело в том, что компиляция гораздо сложнее, чем интерпретация — я уже упоминал ранее, что столкнулся с некоторыми проблемами на этом шаге.
Написать свой компилятор
Сначала мне понравилась эта мысль — я люблю делать вещи сам, к тому же давно хотел изучить язык ассемблера. Вот только создать с нуля кроссплатформенный компилятор — сложнее, чем написать машинный код для каждого элемента языка. Я счёл эту идею абсолютно не практичной и не стоящей затраченных ресурсов.
LLVM — это коллекция инструментов для компиляции, которой пользуются, например, разработчики Swift, Rust и Clang. Я решил остановиться на этом варианте, но опять не рассчитал сложности задачи, которую перед собой поставил. Для меня проблемой оказалось не освоение ассемблера, а работа с огромной многосоставной библиотекой.
Транспайлинг
Мне всё же нужно было какое-то решение, поэтому я написал то, что точно будет работать: транспайлер (transpiler) из Pinecone в C++ — он производит компиляцию по типу «исходный код в исходный код», а также добавил возможность автоматической компиляции вывода с GCC. Такой способ не является ни масштабируемым, ни кроссплатформенным, но на данный момент хотя бы работает почти для всех программ на Pinecone, это уже хорошо.
Дальнейшие планы
Сейчас мне не достаёт необходимой практики, но в будущем я собираюсь от начала и до конца реализовать компилятор Pinecone с помощью LLVM — инструмент мне нравится и руководства к нему хорошие. Пока что интерпретатора хватает для примитивных программ, а транспайлер справляется с более сложными.
Заключение
Надеюсь, эта статья окажется кому-нибудь полезной. Я крайне рекомендую хотя бы попробовать написать свой язык, несмотря на то, что придётся разбираться во множестве деталей реализации — это обучающий, развивающий и просто интересный эксперимент.
Вот общие советы от меня (разумеется, довольно субъективные):
- если у вас нет предпочтений и вы сомневаетесь, компилируемый или интерпретируемый писать язык, выбирайте второе. Интерпретируемые языки обычно проще проектировать, собирать и учить;
- с лексерами и парсерами делайте, что хотите. Использование средств автоматизации зависит от вашего желания, опыта и конкретной ситуации;
- если вы не готовы / не хотите тратить время и силы (много времени и сил) на придумывание собственной стратегии разработки ЯП, следуйте цепочке действий, описанной в этой статье. Я вложил в неё много усилий и она работает;
- опять же, если не хватает времени / мотивации / опыта / желания или ещё чего-нибудь для написания классического ЯП, попробуйте написать эзотерический, типа Brainfuck. (Советуем помнить, что если язык написан развлечения ради, это не значит, что писать его — тоже сплошное развлечение. — прим. перев.)
Я делал довольно много ошибок по ходу разработки, но большую часть кода, на которую они могли повлиять, я уже переписал. Язык сейчас неплохо функционирует и будет развиваться (на момент написания статьи его можно было собрать на Linux и с переменным успехом на macOS, но не на Windows).
О том, что ввязался в историю с созданием Pinecone, ни в коем случае не жалею — это отличный эксперимент, и он только начался.
Хинт для программистов: если зарегистрируетесь на соревнования Huawei Honor Cup, бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.
Перейти к регистрации
Источник статьи: http://tproger.ru/translations/how-to-create-programming-language/