Как я пишу компилятор C-подобного языка с нуля и зачем — конкурс пет-проектов

Всем привет! Меня зовут Вячеслав!

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

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

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

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

Таким образом, я сменил целевой язык на язык Go, получив таким образом транспилер. Тем не менее язык Go и мой C-подобный язык плохо совместимы. Например, в Go нельзя объявлять переменную, которая затем не будет использоваться, а в моем языке можно. В конце концов целевым языком стал для меня классический GNU Assembler, ведь я компилирую программы под ОС Ubuntu x64. В настоящее время он и остается целевым языком. После компиляции программ с языка GNU Assembler я получаю исполняемые файлы.

Лексический анализ предполагает разбиение входного потока символов на осмысленные группы (лексемы), а также выделение токенов (лексемы и ее типа). Например, “AND”, “11”, “(” — это лексемы моего языка). Я выделяю, например, следующие типы лексем: OP — операция, VAL — значение, VAR — переменная, BR — скобка. Так, для приведенных лексем можно назвать следующие токены: “OP AND”, “VAL 11”, “BR (“. Когда код команды (символы до “;”) разбит на лексемы, наступает фаза синтаксического анализа — выявление того, в каких отношениях состоят сущности (токены). Результатом синтаксического анализа обычно является либо абстрактное синтаксическое дерево (АСД), либо трехадресный код. Я строю АСД. Вот пример такого дерева.

Рисунок 1. Абстрактное синтаксическое дерево для выражения

Для построения таких деревьев, визуально понятных для человека, я использую GoCV — обертку на Go для библиотеки OpenCV.

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

Пустые кружки означают тот факт, что у узла нет потомков.

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

Рисунок 2. Процесс получения защищенной программы и ее исполнения

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

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

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

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

В настоящее время мной написан чат-бот на языке Go ВКонтакте, но я мечтаю переписать со временем этого бота на собственном языке. Любимый кусочек кода:

Функция DrawTree, выполняющая первичную подготовку данных и изображения АСД

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

Более подробно о процессе реализации компилятора я рассказываю в своей группе ВКонтакте. Также прикрепляю ссылку на репозиторий GitHub.

• GitHub: https://github.com/korepanov/bint
• ВКонтакте: https://vk.com/repaschool