Перед началом, хочу сообщить -- я не компиляторщик и вообще слабо связан с этой деятельностью. Плохо знаю математику и тем более математические термины, которые часто употребляются в "компиляторостроении". Также, не умею в оптимизации и прочие умные штуки.
В этой статье (если эту писанину можно так назвать) не будет описываться "как сделать компилятор?" и подобное. Здесь будет просто описан мой небольшой опыт создания компилятора для языка.
Идея создать собственный компилятор появилась у меня раньше идеи сделать собственный язык программирования. Помню, ковырялся в исходниках прошивки EV3 контроллера, чтобы сделать его эмуляцию, и в голову пришла идея -- почему бы не сделать что-то такое, но свое? Эмуляция так и не получилась адекватная, но идея написания компилятора или виртуальной машины из головы не уходила.
После долгого поиска проектов-компиляторов, которые я бы смог хоть как-то понять, на глаза попался проект CheezLang. По описанию из репозитория, язык похож на Rust. Я совсем не знаю как программировать на Rust, но зато сам компилятор написан на C# (я шарпист🥴), поэтому моя стартовая точка оказалась именно на этом проекте.
После долгого разбора проекта, после нескольких неудачных попыток его переделать, после кучи всего другого -- я понял, что просто взять чужой проект и немного переделать семантику, не самый лучший вариант. Пришлось читать кучу статей, делать "простенький компилятор"; и во время изучения всего этого в голову начало понемногу приходить понимание, как это все примерно работает.
Примерно такая схема компилятора получилась (стрелочки показывают поток передачи данных между частями компилятора):
Схема компилятора
Стоит отметить, что проект писался не сверху вниз и не снизу вверх. Он писался сразу по всем этапам одновременно. На самом деле -- мне кажется, что это плохая идея так писать компиляторы, но т.к. я не понимал, что может пригодиться на следующем этапе компилятора, приходилось постоянно что-то переделывать.
Лексер и парсер
Лексер и парсер были просто взяты из проекта CheezLang и в дальнейшем сильно переписаны. Если я верно понимаю, в этом проекте использован LR(1) парсер. Я думал, что этого будет достаточно для моего проекта (на тот момент я даже не понимал, какой язык я хочу). По-итогу, такой тип парсера мне не подошел из-за необходимости парсинга обобщений, пришлось его дополнять, чтобы делать lookahead на несколько символов вперед, получился парсер LR(K).
Немного подробнее о причине, почему мне так пришлось сделать: если у нас есть выражение
var a = Test < b > c;
то с LR(1) парсером мне тяжело (или невозможно) понять -- это сравнение или что-то связанное с обобщениями. Для этого необходимо посмотреть на несколько токенов вперед и тогда, возможно, получится понять, что это такое.
На самом деле, этого тоже недостаточно, чтобы понять -- перед тобой обобщение или хитрое выражение со сравнениями, так как могут встречаться и такие вещи:
var a = Test < b > (c);
Такое выражение необходимо обрабатывать на этапе вывода типов, о котором мы поговорим чуть позже. К сожалению, у меня не хватило умений и знаний, чтобы сделать такую точную обработку этих хитрых выражений у себя в компиляторе, поэтому я просто оставил это дело для будущего себя :)
В остальном, разрабатывать лексер и парсер было не так проблемно, просто получаешь токены из лексера, немного "смотришь вперед", создаешь AST ноды в парсере и готово. Если что-то идет не так, как ожидается, бросаешь ошибки.
Вывод типов
Следующий этап компиляции -- это вывод типов. Если простыми словами -- получаешь AST дерево, проходишься по нему, пытаешься понять где какой тип данных, пытаешься посчитать некоторые выражения на этапе компиляции и все.
Первая проблема, с которой я столкнулся, когда начал писать этот этап -- просто пройтись подряд по деревьям не получится. Так как классы, структуры и прочее могут находиться в разных файлах, могут быть объявлены ниже места, где будут использованы, и прочие нюансы, то пришлось обходить эти деревья по-хитрому. Вот на какие этапы я разбил обработку:
- Обработка деклараций верхнеуровневых типов без внутрянок и прочего. Просто "засовываю" декларации в скоуп пространства имен;
- Обработка обобщенных параметров у этих типов и обработка констрэйновэтих обощенных параметров;
- Обработка наследуемых типов;
- Обработка делегатов, вложенных типов и деклараций функций;
- Обработка деклараций полей и свойств;
- Обработка инициализаторов полей и свойств;
- Обработка аттрибутов;
- И только на этом этапе происходит обработка внутренностей функций.
В общем, все не так сложно на первый взгляд. Были, конечно, всякие дурацкие моменты с обработкой операций для разных типов и головные боли с обработкой виртуальных и абстрактных штуковин, но это все решалось. Самая жесть возникла там, где я меньше всего этого ожидал -- опять обобщения.
Вот, на первый взгляд, что такое обобщенные типы? Просто, какой-то условный List<T>, ты пишешь определенный тип вместо T и создается копия обобщенного класса, но уже с твоим типом. На "бумажках" все легко, но по-итогу я убил на работу с этим всем больше 4 месяцев и все равно текущий результат мне не нравится. Пришлось несколько раз переписывать проект вывода типов, просто потому что последовательность обработки не подходила для обработки обобщений. У вас в голове может возникнуть вопрос "А что, собственно, сложного?". Прошу, пример:
public class Test<T>
{
public static Test<E> GetTest<E>();
}
В первых версиях обработчика обобщений, мой компилятор просто зацикливался на таких вещах. Как это было -- компилятор пытается обработать класс Test<T>, обработал; пытается обработать функцию GetTest, видит что надо обработать класс Test<E>, обработал; пытается обработать функцию GetTest в классе Test<E>, ну и т.д. Создается куча классов Test<E> и компилятор падает с ошибкой переполнения стека.
На самом деле, это только одна из проблем с обобщениями, их было много, честно-честно. Ну, на память приходит еще одна -- в компиляторе есть ограничение специальное, что нельзя создавать статические поля и свойства с использованием обобщенного параметра класса. Короче, такое нельзя:
public class Test<T>
{
public static T CoolField;
}
Почему нельзя? -- это мы обсудим в главе про кодогенерацию.
Подготовка типов
Типы выведены, некоторые выражения вычислены, все, вроде, хорошо. Можно преступать к кодогенерации? Вообще, да, но будет немного неудобно использовать AST дерево в текущем виде, поэтому я решил добавить еще один этап, чтобы подготовить это дерево для удобной кодогенерации.
Просто перечислю, что происходит на этом этапе:
- Обработка лямбда-выражений и вложенных нестатических функций. Не могу привести статью или другой документ о том, как это делают умные люди, т.к. насчет захвата контекста, и как это делать с замыканиями, я общался с искусственной головой. Но приведу небольшой пример, как это происходит у меня в компиляторе:
```
public class Test
{
public Action ReturnFunction(int a, int b)
{
var action = () =>
{
Console.WriteLine($"Result: {a + b}");
};
return action;
}
public void CallFunction()
{
var a = ReturnFunction(1, 2);
a();
}
}
```
Такой код превратится во что-то подобное:
```
public class __SyntheticClass0
{
public int a;
public int b;
public void Lambda0()
{
Console.WriteLine($"Result: {a + b}");
}
}
public class Test
{
public Action ReturnFunction(int a, int b)
{
__SyntheticClass0 tmpVar = new __SyntheticClass0();
tmpVar.a = a;
tmpVar.b = b;
return tmpVar.Lambda0;
}
public void CallFunction()
{
var a = ReturnFunction(1, 2);
a();
}
}
```
Приходится такие хитрые штуковины делать, чтобы сохранить контекст у лямбд и вложенных функций.
- Создание get/set функций и полей для свойств;
- Подмена работы со свойствами на вызовы функций get/set;
- Просмотр используемого кода, чтобы не генерировать код, который не используется (для библиотек генерируется всё);
- Какие-то хитрости с вызовами статических конструкторов;
- Самый важный этап -- все, что связано с классами переделывается под работу с указателями. Я не хотел делать этот этап при кодогенерации, потому что там это учитывать сидеть - головая боль. И не хотелось с указателями возиться при выводе типов. Именно этот момент сподвигнул меня на создание дополнительного этапа перед кодогенерацией;
- Ну и добавление виртуальных (в этот же список входят и просто функции, наследуемые от базового класса) функций в сам класс.
После всех этих манипуляций, мы можем со спокойной душой перейти к кодогенерации.
Генерация кода
Еще перед началом работы с компилятором, я где-то слышал про LLVM, мне показалось это очень удобным - просто генерировать один промежуточный код и он будет работать "везде". Очевидно, в этом "везде" есть нюансы: всякие setjmp/longjmp разные на разных платформах, туда же и valist. Ну, короче, в общем, это прикольно генерировать LLVM IR, но и не без проблем с платформо-специфичным кодом.
Вот, когда мы получили подготовленное AST дерево, можем приступить к генерации IR. На самом деле, этот этап был один из самых простых, потому что все неприятные вещи, в основном, уже решены на предыдущих этапах.
А, нет, вспомнил. Давайте немного поговорим про ограничение обобщений, что нельзя использовать обобщенный параметр типа в статических полях и свойствах. Почему так? Представим, что у нам есть три библиотеки и одно приложение, такая схема зависимости:
Смеха зависимостей
В библиотеке A определен тип SomeType<T>, потом в библиотеках B и C этот тип используется с параметром int. Потом эти две библиотеки импортируются в нашем приложении. При кодогенерации и в библиотеке B, и в библиотеке C создаются свои типы SomeType<int>, для каждой библиотеки они свои. Ну и очевидно, что при изменении статического поля у SomeType<int> в библиотеке B, изменение не отразится в этом же типе в библиотеке C. Да и вообще, как в проекте конечного приложения понять, какой из типов использовать - из B или из C?
Вы можете сказать -- "Ну, просто у тебя проблема в кодогенерации, наверняка это как-то можно решить". Согласен, наверняка как-то можно, я что-то даже находил про это (где-то в сохраненках была ссылка на статью о том, как поиграться с линковщиком и прочей умной темой, чтобы можно было решить мою проблему, но я ее благополучно потерял где-то), но по-итогу мне стало лень этим заниматься. Изучение работы линковщиков - не то, что я хочу изучать в ближайшее время, хотя надо бы.
Была еще одна проблема с линковщиком, помню. Там что-то было связано с нижними подчеркиваниями ('_'). Их то ли надо было добавлять к называниям глобальных переменных, то ли еще к чему при генерации под x86 Windows. Но эта проблема решилась заменой MSVC линковщика на линковщик от LLVM.
Короче, были всякие странные такие моменты, но в общем, кодогенерация все еще оставалась одной из самых простых частей компилятора, просто нужно было знать синтаксис LLVM IR.
Остальные моменты
Есть еще пару вещей, о которых я бы хотел написать, но они не относятся к конкретному этапу компиляции. Вот, например, сборщик мусора. Я всегда знал, что эта штука не простая и я потрачу на нее уйму времени. Так бы и получилось, если бы я не забил *** на работу сборщика где-то в отдельном потоке. Потоки у меня не были реализованы (они и сейчас не реализованы), поэтому нужно было думать о том, как собирать мусор, но без хитростей таких. По-итогу получился смешной сборщик мусора, который нужно вызывать самому. Сам сборщик консервативный, просто поднимается (или опускается, не помню в какую сторону стек идет) по стеку до рута главного и смотрит на все. Ну и да, одна из проблем таких сборщиков, что они могут оставлять нетронутыми объекты, которые нужно почистить, из-за ложного срабатывания (типа адрес объекта будет такой же, как просто число, лежащее где-то на стеке). А в остальном, меня устраивает такой сборщик.
Тип массива сделал обобщенным. Я на самом деле думал, что в C# он тоже обобщенный, оказалось, что нет. Ну, надеюсь, это не опрометчивое решение, пока что проблем не наблюдаю особых с этим. Вслед за этим переделал еще обобщенные интерфейсы ICollection, IEnumerable и прочие, чтобы они были идентичны обычным.
Добавил команду для обновления компилятора, хочется, чтобы пользователь всегда был на последней версии компилятора. Вряд ли, конечно, так будет, но просто захотелось. Breaking changes особо не планируются. Планируется только схожесть с C#.
Главные изменения подсветил в документации, но в общем, язык получился очень похожим на шарпы.
Итог
Изначально, я даже не знал, какой язык я хочу. Получился C#-подобный язык :) Считаю это хорошим опытом, хотя, очевидно, что многие вещи я делал "неправильно". Компилятор я буду развивать дальше, забрасывать пока не планирую, нужно еще много вещей добавить: многопоточность, поддержку блатного паттерн-матчинга, да и стандартную библиотеку бы сделать обширнее.
Спасибо, что прочитали до конца. С радостью почитаю ваше мнение об этом проекте и приму во внимание замечания.
~~Ссылка на очередной бесполезный тг канал.~~
Ссылка на проект: hapet-lang/hapet: Compiler for hapet programming language
Ссылка на сайт проекта: hapet