Как написать компилятор

Написание компилятора на собственном языке

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

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

12 ответов

Это называется “bootstrapping”. Сначала вы должны создать компилятор (или интерпретатор) для своего языка на каком-либо другом языке (обычно Java или C). Как только это будет сделано, вы можете написать новую версию компилятора на языке Фу. Вы используете первый компилятор начальной загрузки для компиляции компилятора, а затем используете этот компилятор для компиляции всего остального (включая будущие версии самого себя).

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

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

Я помню, как слушал a Программная инженерия Радио подкаст в котором Дик Гэбриэл говорил о загрузке оригинального интерпретатора LISP, написав версию с голыми костями на LISP на бумаге и рука собирая его в код машины. С тех пор остальные функции LISP были записаны и интерпретированы с LISP.

добавление любопытства к предыдущим ответам.

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

цель “bootstrap” не просто скомпилируйте GCC, но скомпилируйте его несколько раз. Он использует программы, скомпилированные в первом раунд, чтобы скомпилировать себя во второй раз, а затем снова в третий раз. Затем он сравнивает эти второй и третий компилирует, чтобы убедиться, что он может воспроизводить себя безупречно. Это также означает, что он был составлен правильно.

это использование цели “bootstrap” мотивировано тем фактом, что компилятор, используемый для построения цепочки инструментов целевой системы, может не иметь того же самого версия целевого компилятора. Таким образом, в целевой системе можно получить компилятор, который может компилироваться сам.

когда вы пишете свой первый компилятор для C, вы пишете его на каком-то другом языке. Теперь у вас есть компилятор для C, скажем, ассемблер. В конце концов, вы придете к месту, где вам нужно разобрать строки, в частности escape-последовательности. Вы напишете код для преобразования n на символ с десятичным кодом 10 (и r до 13 и т. д.).

после того, как этот компилятор будет готов, вы начнете переопределять его в C. Этот процесс называется “загрузки”.

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

когда это компилируется, у вас есть двоичный файл, который понимает ‘n’. Это означает, что вы можете изменить исходный код:

Итак, где информация о том, что’ n ‘ является кодом для 13? Это в двоичном коде! Это похоже на ДНК: компиляция исходного кода C с этим двоичным кодом унаследует эту информацию. Если компилятор компилирует себя, он передаст это знание своему потомству. От на этом этапе невозможно увидеть из одного источника, что будет делать компилятор.

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

интересными частями являются A и B. A-исходный код для compileFunction включая вирус, вероятно, зашифрованный каким-то образом, поэтому это не очевидно из поиска результирующего двоичного файла. Это гарантирует, что компиляция в компилятор сама по себе сохранит код вирусной инъекции.

B то же самое для функции, которую мы хотим заменить нашим вирусом. Например, это может быть функция ” login “в исходном файле “login”.c”, который, вероятно, из ядра Linux. Мы могли бы заменить его версией, которая будет принимать пароль “joshua” для учетной записи root в дополнение к обычному паролю.

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

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

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

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

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

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

из того, что я помню из “mono”, вероятно, им нужно будет добавить несколько вещей к размышлению, чтобы заставить его работать: команда mono продолжает указывать, что некоторые вещи просто невозможны с Reflection.Emit ; конечно, команда MS может доказать их неправильный.

Это несколько реальные плюсы: это довольно хороший тест для начала! И у вас есть только один язык, о котором нужно беспокоиться (т. е. Возможно, эксперт C# может не знать много C++; но теперь вы можете исправить компилятор C#). Но мне интересно, нет ли здесь профессиональной гордости: они просто хочу это будет самостоятельный хостинг.

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

обновление 1

Я только что смотрел видео Андерса в PDC ,и (около часа) он дает некоторые гораздо более веские причины – все о компиляторе как службе. Для протокола.

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

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

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

• Переводы, 11 апреля 2017 в 21:59
• Саша

На протяжении последних шести месяцев я работал над созданием языка программирования (ЯП) под названием 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, ни в коем случае не жалею — это отличный эксперимент, и он только начался.

Как написать компилятор

Хотите улучшить этот вопрос? Переформулируйте вопрос, чтобы он был сосредоточен только на одной проблеме, отредактировав его.

Закрыт 2 года назад .

Не могу понять, в чем сложность написания компилятора и нужно ли его вообще писать? Разве нет универсального компилятора – типа нажал “импорт” и все автоматически перевелось в машинный язык. Вопрос возник, потому что в интернете много противоречивой информации на этот счет.

Насколько я понимаю компилятор нужен, чтобы преобразовать какую-нибудь программу на языке высокого уровня (например С “си”) в машинный код, который понимает процессор. Но ведь программа – это набор инструкций на языке высокого уровня, которым соответствует битовая последовательность на языке низкого уровня. Разве в языках программирования высокого уровня нет грубо говоря “программы перевода” на низкий уровень, называемый компиляцией?

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

Также в интернете пишут, что компилируемые языки сложнее интерпретируемых, потому что после написания программы на компилируемых языках ее нужно компилировать? А в чем сложность? Если я правильно понимаю, то уже давно существует соответствие команд высокого уровня битовой последовательности низкого (разумеется для каждого языка свое соответствие)? Или все совсем не так, тогда что из себя технически представляет компилирование на языке высокого уровня?

2 ответа

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

Насколько я понимаю компилятор нужен, чтобы преобразовать какую-нибудь программу на языке высокого уровня (например С “си”) в машинный код, который понимает процессор.

Это верно, обычно так это и есть. (Исключение — компиляторы в промежуточный код, например, компилятор C#.)

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

Да. И вот именно переводом инструкций высокого уровня в инструкции низкого уровня и занимается компилятор.

Разве в языках программирования высокого уровня нет грубо говоря “программы перевода” на низкий уровень, называемый компиляцией?

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

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

Это определение указателя t на тип T ? Может, да, а может, нет. Если T и pt — ранее определённые переменные, то это вызов оператора умножения. То есть ваш код должен знать, какие переменные есть к текущему моменту, чтобы понять, является ли данная строчка объявлением новой переменной. А значит, должен знать границы всех функций и всех классов.

Затем, допустим, что у нас есть * , и мы выяснили, что это не объявление указателя, а умножение. Какую инструкцию для него использовать? Если это умножение целых чисел, на интеловской архитектуре можно использовать imul . Если это умножение чисел с плавающей запятой, вам понадобится команда наподобие mulsd (если вы используете XMM-регистры). А если одно из чисел с плавающей запятой, а другое целое, то такой команды умножения у процессора вовсе нет, и вам нужно сконвертировать целое число в число с плавающей точкой. А если у вас перемножаются не числа, а пользовательские структуры данных с перегруженным оператором умножения, то вместо умножения надо и вовсе вызвать функцию.

То, что я описал, не представляет собой и десятой доли процента сложности компилятора C++.

по идее писать ничего не надо (все уже должно быть 30 лет назад написано)?

Новые стандарты языков и новые языковые возможности выходят регулярно, в C#, например, только в этом году вышло три (минорных) версии языка. Старым компилятором невозможно скомпилировать новый код.

Если я правильно понимаю, то уже давно существует соответствие команд высокого уровня битовой последовательности низкого (разумеется для каждого языка свое соответствие)?

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

нужно ли его вообще писать

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

Источники:

http://askdev.ru/q/napisanie-kompilyatora-na-sobstvennom-yazyke-11002/
http://tproger.ru/translations/how-to-create-programming-language/
http://ru.stackoverflow.com/questions/746196/%D0%9D%D1%83%D0%B6%D0%BD%D0%BE-%D0%BB%D0%B8-%D0%BF%D0%B8%D1%81%D0%B0%D1%82%D1%8C-%D1%81%D0%B2%D0%BE%D0%B9-%D0%BA%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80