Компилятор

Введение

Я делаю компилятор для C-подобного языка. Грамматика взята из Cpp2: https://github.com/hsutter/cppfront На данной итерации на большинство папок в проекте можно не обращать внимание. Основные вещи расположены в: tests, src/ast, src/cli, src/compilation, src/lexis, src/sources, src/syntax, src/utils

Лексер

Файлы лексера находятся в папке src/lexis. Перед использованием его необходимо скомпилировать. В файле compile_lexis_table.cpp находится описание регулярных выражений для каждого токена. По ним строится единый детерминированный конечный автомат (с небольшими дополнениями), согласно которому будет работать лексер. Автомат сохраняется в файле lexis.lx.

Сам лексер находится в файле LexicalAnalyzer.h. Он работает подобно потоку, не сохраняя все обработанные токены. У него есть два основных метода:

• current_token возвращает токен, на котором сейчас находится указатель лексера
• next_token смещает указатель лексера на (1 токен)* и возвращает новый текущий токен

*: есть технические виды токенов (например комментарий), которые лексер пропускает всегда

Виды токенов описаны в файле Token.h. Там используется макрос для создания "умного" enum. Он ведёт себя так же, как и обычный enum почти во всех случаях, но предоставляет удобные методы, такие как .to_string() и т.д. Токен помимо своего типа хранит диапазон символов, который он покрывает.

Чтобы не копировать повсюду строки, есть класс SourceManager. Он единожды загружает текст программы в память, а после предоставляет способ получения "view" на этот текст программы. Для описания позиций в этом тексте программы существуют классы SourceLocation и SourceRange.

Парсер

Для парсинга используется LR(1)-парсер. Файлы парсера находятся в src/syntax. Перед использованием его необходимо скомпилировать. Он берёт грамматику, описанную в файле grammar.txt, составляет LR(1)-таблицу и сохраняет её в файле grammar.lr. Также автоматически генерируется файл BuildersRegistry.h. Он необходим, чтобы парсер при сворачивании правила вызывал правильную функцию для построения AST-дерева.

LR-парсер описан в файле lr/LRParser.h. Помимо непосредственно построения AST парсер обрабатывает ошибки. Для этого есть класс RecoveryTree в файле LRParser.cpp, который отвечает за механизм восстановления после ошибок. В будущем я планирую разделить две эти структуры полностью, чтобы RecoveryTree было независимой от парсера структурой.

Чтобы не копировать строки повсюду, есть класс StringPool. У каждого модуля есть свой StringPool. При добавлении строки в него он выдаёт уникальный идентификатор этой строки - StringId (важно: не объекта, а именно строки, которую он представляет - у одинаковых строк одинаковый идентификатор). StringId гарантированно копируется и сравнивается на равенство за O(1), поэтому в компиляторе он всегда передаётся по значению.

Семантический анализ

Файлы семантического анализатора находятся в src/compilation/semantics. Перед запуском семантического анализатора для модуля M компилятор проводит семантический анализ для всех зависимостей модуля M. Семантический анализатор обходит AST-дерево и делает следующее:

1. Вычисляет типы выражений (Expression) и типов (TypeNode). Типы сохраняются таким образом, что для проверки на равенство двух типов из одного модуля достаточно сравнить лишь указатели на них. Один тип в одном модуле хранится в памяти не более, чем в одном экземпляре. Файлы, связанные с типами, хранятся в src/compilation/types.
2. Заполняет таблицу символов. (Сейчас она довольно сумбурно построена, но будет улучшаться со временем) Основные файлы таблицы символов - это SymbolInfo.{h, cpp} и Scope.h. В виде SymbolInfo хранится информация о символах, определённых в программе, которую собирает семантический анализатор. Фактически SymbolInfo - это дополнительная информация о Declaration.
3. Запоминает экспортируемые символы. Это нужно, чтобы потом получать их из модулей, зависящих от текущего.

Генератор IR

Файлы генератора IR находятся в src/compilation/ir. Этот генератор создаёт llvm-модуль для каждого модуля. Основную сложность здесь представляет генерация кода для Expression (эти методы находятся в IRExpressions.{h, cpp}). Выражения генерируются рекурсивно, возвращая специальный класс Value в качестве результата. Value - это обёртка над llvm::Value, которая дополнительно хранит, является ли это указателем на значение или самим значением. Отмечу, что это не всегда коррелирует с понятием rvalue и lvalue из семантики языка. Для простых типов (i64, b8 и т.п.) rvalue - это значение, а lvalue - указатель на значение, но вот сложные типы (tuple или класс) всегда передаются через указатель ( даже когда в семантике языка они передаются по значению).

Дополнительно делается манглер для имён. Он находится в src/compilation/mangling. Он старается следовать Itanium C++ ABI, чтобы код можно было линковать с C++.

Текущий статус языка

В языке на данный момент поддерживаются:

1. управляющие конструкции if и while
2. функции (однако они не совсем следуют ABI - при передаче tuple по значению они всегда принимают его, как указатель, но ABI процессоров требует иногда передавать классы через регистры, если классы маленькие)
3. пространства имён (namespace)
4. объявление переменных и запись в них
5. выражения, состоящие из +, -, *, все сравнения, ! (унарный оператор not), .{0, 1, 2, ...} (доступ к элементам tuple), скобки, вызовы функций, литералы, имена переменных, tuple-expression (например: (1, 2, 3, 4))
6. поддерживаются типы i64 и b8, а также tuple, состоящие из этих типов

Сборка и запуск

CMake настроен так, что он автоматически запускает генератор таблицы для лексера и парсера при необходимости. Для сборки и запуска проекта вам потребуется:

1. GoogleTest (git-submodules)
2. fmt (git-submodules)
3. argparse (git-submodules)
4. LLVM: помимо самой библиотеки требуются clang, FileCheck, lit и llc в собранном виде (CMake будет их искать через find_program при сборке) Библиотеки, помеченные "(git-submodules)", устанавливаются вместе с этим проектом через git-submodules. Их можно найти в папке lib.

Чтобы не настраивать всё самостоятельно, можно воспользоваться docker-образом, описанным в Dockerfile. После входа в docker-контейнер (или после самостоятельной установки библиотек) можно установить проект через git:

git clone --recursive https://github.com/MishkaSimakov/RecursiveFunctions

После скачивания проекта нужно сконфигурировать cmake-проект. Для этого выполните из корня проекта:

mkdir build
cd build
cmake ..

Цели для сборки

Основная цель - это cli. Она выдаёт исполняемый файл, который служит интерфейсом к компилятору через командную строку.

Также есть cli_installation. Она собирает cli и устанавливает его в системе под именем tlang ( не путать с clang :-) )

Тестирование

Тесты находятся в папке tests. Есть 2 вида тестов.

unit-тесты

Они используют GoogleTest и тестируют лексер и парсер. Чтобы их запустить есть цель tests.unit

lit-тесты

я не знаю, как их правильно называть по научной классификации тестов

Они используют llvm lit для тестирования. По духу они ближе к feature-тестам, так как запускают определённую часть компилятора и проверяют, что выход соответствует определённым паттернам. Для проверки вывода компилятора используется llvm FileCheck. Чтобы запустить их, соберите цель tests.lit

Идеи на будущее

У меня нет какого-то гениально-красиво-абстрактно-математического плана для этого языка. Я просто постараюсь сделать язык, на котором можно будет написать что-нибудь осмысленное, и чтобы можно было быть уверенным, что это что-то осмысленное корректно заработает.

У меня есть несколько более-менее сформированных идей того, что бы я хотел добавить:

1. Явный кастинг между типами. Я хочу сделать для этого 3 вариации одного оператора: as, as? и as!. Это должно выглядеть примерно так: 123 as u32 или shape as? Rectangle.
   1. Версия as - самая простая. Она должна работать в тех вариантах, когда корректность преобразования можно проверить в compile-time. Например, каст Rectangle -> Shape, если Rectangle - это наследник Shape.
   2. as? должен работать в тех случаях, когда корректность кастинга устанавливается в run-time. Он должен возвращать что-то вроде Optional, чтобы потом можно было проверить, удался ли каст. Это что-то вроде dynamic_cast из c++.
   3. as! работает в тех же случаях, что и as?. Делает то же самое, но без всех проверок. Его некорректное использование должно приводить к UB. Это что-то вроде static_cast из c++.
2. Работа с указателями. Тут довольно сложный выбор. Мне хотелось бы, чтобы пользователь вместо указателей работал со ссылками или с аналогом std::span, но у них более сложная семантика, поэтому на первое время я хочу сделать указатели, а потом постепенно убирать места, где их нужно использовать.
3. Константность. Думаю, что тут я возьму подход из Rust. Всё будет константным до тех пор, пока пользователь явно не напишет mut.