Мой первый компилятор на LLVM
Это руководство посвящено написанию простейшего компилятора на LLVM. Никакой предварительной подготовки не требуется.
Входным языком нашего компилятора будет BF. Это классический «игрушечный» язык для компиляторов, и даже есть компилятор BF в примерах к LLVM! В этом посте я приведу процесс написания компилятора с пояснениями.
Первая программа на LLVM
Инфраструктура LLVM построена вокруг языка программирования LLVM IR. Вначале мы напишем самую простую программу LLVM IR, насколько это возможно.
Так как LLVM уже использует LLVM IR, мы можем просто использовать clang, чтобы посмотреть, как выглядит простая программа. Возьмём простую программу на C
Пропустим её через clang:
Получаем файл forty_two.ll, который выглядит так:
Наша первая программа на LLVM IR! Мы можем использовать lli, чтобы запустить её:
Пишем скелет
Мы будем компилировать команды BF в последовательность инструкций LLVM IR. Однако, эти инструкции должны быть помещены внутрь функции main, чтобы LLVM знал, где находится точка входа. Нам также будет нужно аллоцировать и инициализировать ячейки памяти и индекс ячейки.
И снова мы просто напишем эквивалент на С и посмотрим на код LLVM IR, который сгенерирует Clang. Вот скелет программы, который мы будем использовать:
Вручную компилируем >
«>» — это самая простая для компиляции команда BF. Откроем текстовый редактор и запишем её эквивалент на LLVM IR.
Если ваши познания BF немного заржавели, «>» просто инкрементирует индекс ячейки.
Чтобы проверить, что код правильный, запустим его. Просто вставим его в наш скелет, запустим в lli, и посмотрим, что получилось. Реализация «>» прямолинейна, и мы также напишем программу для » «. Прекрасное руководство по LLVM включает в себя инструкции для компиляции простой программы C++ с использованием LLVM API.
Компиляция других команд BF — это простая трансляция наших написанных вручную сниппетов. Вы можете увидеть полностью работающий компилятор здесь.
Генерация машинного кода
Наш компилятор генерирует только LLVM IR. Настоящие компиляторы генерируют машинный код. Используем llc для преобразования в объектный файл, а затем слинкуем для получения исполняемого файла.
Приложение: Оптимизация
Можно делать оптимизации, чтобы получить более быстрые исполняемые файлы из программ BF. Однако, LLVM достаточно умён для компиляции простой BF-программы без циклов в оптимальное представление LLVM IR!
Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.
Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:
— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это »
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):
Ответы машина выдавала вроде бы правильные.
Как написать простейший компилятор
Лучший способ понять как работает компилятор — написать свой собственный. В этом поможет этот краткий, но исчерпывающий гайд.
Введение
Стандартный компилятор осуществляет следующие шаги:
В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).
После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.
Запомните основные моменты
Компилятор должен быть:
Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.
Читайте книги!
Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.
Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.
Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.
Хорошо определите свой язык
Вы можете использовать любую нотацию, но будьте уверены, что имеете полное и последовательное описание языка. Оно включает в себя как синтаксис, так и семантику.
Используйте свой любимый язык
Это совершенно нормально — писать компилятор на Pyhton, Ruby или любом другом языке, который вам нравится. Используйте простые алгоритмы, принцип которых вы хорошо понимаете. Первый ваш компилятор вовсе не обязан быть быстрым, или эффективным, или обладать кучей фич. Все, что от него требуется — работать достаточно правильно и легко поддаваться переработкам.
Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.
Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.
Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.
Сделайте хороший парсер
Парсеров существует огромное количество, выбирайте любой. Можно написать свой собственный, но это сработает только в том случае, если синтаксис вашего языка примитивен до маразма.
Парсер должен выявлять синтаксически ошибки и сообщать о них. Пишите много тестов, как позитивных, так и негативных. Переиспользуйте написанный код для определения языка.
На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».
Напишите семантический валидатор
Вполне вероятно, что ваш язык допускает синтаксически правильные конструкции, не имеющие смысла в некоторых контекстах. Примером может служить повторное объявление одной и той же переменной или пропуск параметра неправильного типа. Валидатор призван выявлять ошибки такого рода.
Также зона его ответственности охватывает разрешение зависимостей с другими модулями, написанными на вашем языке, загрузкой этих модулей и использовании их в процессе валидации. Например, именно на этом этапе проверяется соответствие количества параметров, поступающих на вход функции из подключаемого модуля.
Еще раз, пишите и запускайте много тестов. Тривиальные случаи также обязательны к рассмотрению, как и сложные.
Генерируйте код
Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условны й оператор) в слабо параметризированный шаблон кода.
Забудьте об эффективности и сосредоточьтесь только на правильности.
Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.
Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.
Конечно, некоторая простая оптимизация вполне уместна на начальном этапе. Но старайтесь избегать излишних хитростей, пока ваш компилятор не будет достаточно стабилен.
Как я писал компилятор С++. Пересказ спустя 15 лет
15 лет назад не было Хабрахабра, не было фейсбука, и что характерно, не было компилятора С++, с выводом диагностических сообщений на русском. С тех пор, вышло несколько новых стандартов С++, технологии разработки сделали гигантский скачок, а для написания своего языка программирования или анализатора кода может потребоваться в разы меньше времени, используя существующие фреймворки. Пост о том, как я начинал свою карьеру и путем самообразования и написания компилятора С++, пришел к экспертному уровню. Общие детали реализации, сколько времени это заняло, что получилось в итоге и смысл затеи — тоже внутри.
С чего все начиналось
В далеком 2001-ом году, когда мне купили первый компьютер Duron 800mhz/128mb ram/40gb hdd, я стремительно взялся за изучение программирования. Хотя нет, сначала меня постоянно мучил вопрос, что же поставить Red Hat Linux, FreeBSD или Windows 98/Me? Ориентиром в этом бесконечном мире технологий для меня служил журнал Хакер.
Старый такой, стебный журнал. К слову, с тех пор, стиль изложения в этом издании почти не поменялся.
Виндузятники, ламеры, трояны, элита, линух — вот это все сносило крышу. Реально хотелось
поскорей освоить этот весь стек, которые они там печатали и хакнуть Пентагон (без интернета).
Внутренняя борьба за то, становиться ли Линуксоидом или рубится в игры на винде продолжалась до тех пор, пока в дом не провели интернет. Модемный, скрежечащий 56kb/s интернет, который занимал телефон на время подключения, и качал mp3-песню в районе получаса. При цене порядка 0.1$/mb, одна песня вытягивала на 40-50 центов. Это днем.
А вот ночью, были совсем другие расценки. Можно было с 23.00 до 6.00 залипать во все сайты не отключая изображения в браузере! Поэтому все что можно было скачать из сети за ночь, качалось на винт, и далее прочитывалось уже днем.
В первый день, когда мне домой провели и настроили сеть, админ передо мной открыл IE 5 и Яндекс. И быстро ретировался. Думая, что же первым делом искать в сети, я набрал что-то вроде «сайт для программистов». На что первой ссылкой в выдаче выпал совсем недавно открывшийся rsdn.ru. И на нем я стал зависать продолжительное время, испытывая чувство неудовлетворенности, от того, что мало что понимаю. На то время флагманом и самым популярным языком на форуме (да и вообще) был С++. Поэтому вызов был брошен, и ничего не оставалось, как догонять бородатых дядек в их знаниях по С++.
А еще был не менее интересный сайт на то время — firststeps.ru. Я до сих пор считаю их метод подачи материала наилучшим. Маленькими порциями (шагами), с небольшими конечными результатами. Тем не менее все получалось!
Но вернемся к теме поста. Осилив Кнута, надо было двигаться дальше. Попутно я сходил на курсы Turbo Pascal, прочитал Кернигана и Ритчи, а за ними С++ за 21 день. Из С и С++, мне было не все понятно, я просто брал и переписывал тексты из книг. Загуглить или спросить было не у кого, но зато времени было вагон, так как школу я забросил и перешел в вечернюю, в которую можно было практически не ходить, или появляться на 3-4 урока в неделю.
В итоге с утра до ночи, я фанатично развивался, познавая все новые и новые темы. Мог написать калькулятор, мог написать простое приложение на WinApi. На Delphi 6 тоже получалось что-то нашлепать. В итоге, получив диплом о среднем образовании, я уже был подготовлен на уровне 3-4 курса университета, и разумеется на какую специальность идти учится вопроса не стояло.
Поступив на кафедру Компьютерных систем и сетей, я уже свободно писал на С и С++ задачи любого уровня сложности университета. Хотя, зайдя на тот же rsdn.ru, понимал, как много еще нужно изучить и насколько бывалые форумчане прокаченней меня в плюсах. Это задевало, непонимание и вместе с тем жгучее желание знать все, привело меня к книге «Компиляторы. Инструменты. Методы. Технологии» — А.Ахо, Рави Сети. В простонародье именуемой книгой Дракона. Вот тут и началось самое интересное. Перед этой книгой, был прочитан Герберт Шилдт, Теория и практика С++, в которой он раскрывал продвинутые темы разработки, такие как шифрование, сжатие данных, и самое интересное — написание собственного парсера.
Начав скрупулезно изучать книгу дракона, двигаясь от лексического анализа, затем к синтаксическому и наконец к проверке семантики и генерации кода, ко мне пришло судьбоносное решение — написать свой компилятор С++.
— А почему бы и нет, спросил себя?
— А давай, ответила та часть мозга, которая с возрастом становится все скептичней ко всему
новому. И разработка компилятора началась.
Подготовка
Модемный интернет к тому времени мне перекрыли, в силу смены телефонных линий на цифровые, поэтому для ориентира был скачан стандарт ISO C++ редакции 1998 года. Уже полюбившимся и привычным инструментом стала Visual C++ 6.0.
И по сути задача свелась к тому, чтобы реализовать то, что написано в стандарте С++. Подспорьем в разработке компилятора была книга дракона. А отправной точкой, был парсер-калькулятор из книги Шилдта. Все части пазла собрались воедино и разработка началась.
Препроцессор
Лексический анализатор
Синтаксический анализатор
nrcpp/Parser.cpp
Задача синтаксического анализатора — проверить правильность расстановки лексем, который были получены на этапы лексического анализа.
За основу синтаксического анализатора были взяты опять же простенький парсер из Шилдта, прокаченный до уровня синтаксиса С++, с проверкой переполнения стека. Если мы например напишем:
То мой рекурсивный анализатор съест стэк, и выдаст, что выражение слишком сложное.
У внимательного читателя, может возникнуть вопрос. А зачем изобретать велосипед, ведь был же yacc и lex. Да, был. Но на том этапе, хотелся велосипед с полным контролем над кодом. Разумеется в производительности он уступал сгенерированному этими утилитами коду. Но не в этом была цель — техническое совершенство. Цель была — понять все.
Семантика
Занимает соотвественно главы с 3-ей по 14-ую стандарта ISO C++ 98. Эта наиболее сложная часть, и я уверен, что >90% С++ разработчиков не знает всех правил описанных в этих разделах. Например:
Знали ли вы, что функцию можно объявлять дважды, таким образом:
Есть такие конструкции для указателей:
А это указатель на функцию-член класса X:
Это первое, что пришло в голову. Стоит ли говорить, что при тестировании кода из стандарта в Visual C++ 6, я не редко получал Internal Compiler Error.
Разработка анализатора семантики языка заняла у меня 1.5 года, или полтора курса универа. За это время меня чуть не выгнали, по другим предметам кроме программирования, за счастье получалась тройка (ну, ок четверка), а компилятор тем временем разрабатывался и обрастал функционалом.
Генератор кода
Чего нет в nrcpp?
Зачем писать свой велосипед?
А в заключении хочу отметить то, ради чего писалась этот пост. Написание своего велосипеда, даже если на это потрачено 2 с лишним года, кормит меня до сих пор. Это бесценные знания, база, которая будет с Вами на протяжении всей карьеры разработчика. Будут меняться технологии, фреймворки, выходить новые языки — но фундамент в них будет заложен из прошлого. И на их понимание и освоение уйдет совсем немного времени.
Кратчайшее введение в создание компилятора
Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 15-минутные завершенные истории могут оказаться неплохим способом погружения в сложные темы. Только хорошо бы не пассивно читать то, что представлено ниже, а еще и проверять код в работе.
Если первый опыт окажется успешным, то в будущем вас могут ожидать и другие 15-минутные «зарисовки» по тематике компиляторов.
О чем пойдет речь
Давайте сделаем компилятор арифметических выражений. Такой, который переведет исходный текст в обратной польской форме записи (ее еще называют RPN или ПОЛИЗ) в промежуточный код, работающий со стеком. Но мы обойдемся здесь без интерпретаторов. Далее мы сразу переведем результат в представление на языке Си. То есть у нас получится компилятор из RPN в Си.
Кстати говоря, писать компилятор мы будем на Python. Но пусть это не останавливает тех, кто предпочитает какой-то иной язык программирования. Вот вам полезное упражнение: переведите приведенный код на ваш любимый язык. Или воспользуйтесь уже готовым переводом:
Начнем с синтаксического анализа
Что мы здесь сделали? Функция scan получает от пользователя строку в обратной польской форме записи («2 2 +»).
А на выходе мы получаем ее промежуточное представление. Вот такое, например:
Вот так, мы уже получили компилятор. Но уж очень он несерьезный. Вспомним, что изначально речь шла о коде на Си.
Займемся трансляцией в Си
Что здесь происходит? Давайте посмотрим на вывод данной функции (на том же примере с «2 2 +»).
Да, это уже похоже на код на Си. Массив st играет роль стека, а sp — его указатель. Обычно с этими вещами работают виртуальные стековые машины.
Вот только самой машины — интерпретатора у нас-то и нет. Есть компилятор. Что нам осталось? Надо добавить необходимое обрамление для программы на Си.
Наш первый компилятор в готовом виде
Остается скомпилировать вывод данной программы компилятором Си.
Вы все еще готовы продолжать? Тогда давайте обсудим, что у нас получилось. Есть один сомнительный момент — наш компилятор транслирует константные выражения, а ведь их можно вычислить просто на этапе компиляции. Нет смысла переводить их в код. Но давайте пока считать, что какие-то аргументы могут попасть в стек извне. Остановимся на том, что практический смысл нашей разработке можно придать и позднее. Сейчас же важно получить общее представление о построении простейших компиляторов, верно?
Компилятор с использованием формы SSA
Вам нравится заголовок? SSA — это звучит очень солидно для любого компиляторщика. А мы уже сейчас будем использовать эту самую SSA. Что же это такое? Давайте двигаться по порядку.
Мы генерируем в данный момент код на Си, безо всяких виртуальных машин. Но зачем нам тогда рудимент в виде операций со стеком? Давайте заменим эти операции работой с обычными переменными из Си. Причем, мы не будем экономить переменные — для каждого выражения заведем новое имя. Пусть компилятор Си сам со всем этим разбирается. Получается, что у нас каждой переменной значение присваивается лишь однажды. А это, кстати говоря, и есть форма SSA.
Вот наш новый компилятор.
Обратите внимание — стека в коде на Си уже нет, а работа с ним имитируется в процессе трансляции. На стеке, который используется в процессе компиляции, содержатся не значения, а имена переменных.
Вот окончательный результат:
Итоги
Похоже, время нашего совместного занятия истекло. Мы занимались тем, что переводили программу с одного языка на другой. Это называется source-to-source трансляцией. Или же — просто трансляцией, которую можно считать синонимом компиляции, но обычно компилятор переводит программу из высокоуровневого представления в низкоуровневое. Существует еще модное словечко «транспилятор» для обозначения source-to-source транслятора. Но упоминание «транспилятора» может вызвать раздражение у специалистов по компиляторам, будьте осторожны!