Onyx - язык программирования, нацеленный на базовую безопасность памяти, приятный синтаксис и опыт использования. Onyx написан на C++ с компиляцией на базе LLVM. На момент написания статьи язык поддерживает:
Определение глобальных переменных
Определение функций
Определение локальных переменных
Изменение значений переменным
Вызов функций
Данный язык является моим самым серьезным проектом с максимально чистой архитектурой (конечно, по моим меркам). Компилятор также обладает оптимизациями (O1, O2, O3), выводом AST и разными режимами компиляции (в бинарь, в объектный файл и в читаемый LLVM IR код). Репозиторий не оформлен пока что, я пока что на этом не акцентировал внимания. Надеюсь заинтересовал, теперь немного о себе.
О себе
Мне 16 лет, я начинающий проггер на плюсах и LLVM. Я пишу не идеально, возможно даже не хорошо, поэтому я жду ваши предложения по улучшению языка и кода в целом. Данный компилятор не мой единственный, поэтому какие-то части кода - это пережиток прошлого, а какие-то части - обучение на собственных ошибках. Стоит сразу отметить, что я против ИИ в коддинге и не использую языковые модели для генерации кода - всё ручками пишется. Начнем всё таки уже статью, а именно немного теории (постараюсь объяснить так, чтобы понял каждый. Могу ошибаться).
Теория
Итак, как же работают языки программирования и компиляторы в целом? Язык программирования - это та же программа, что и привычные нам приложения, просто нужна эта программа для другого направления - анализ Вашего кода и его последующая компиляция (или исполнение). Языки делятся на несколько категорий:
Интерпретаторы
Виртуальные машины (частный случай интерпретатора)
Компиляторы
Транспиляторы
Я бы хотел рассказать о каждом подробнее, но сейчас речь только о компиляторах. Языки между собой не особо чем-то отличаются, максимум способом выполнения кода (или его компиляция в бинарь). Компилятор состоит из:
Лексер
Парсер
Семантика
Генерация кода
Линковка
Давайте остановимся на каждом из них подробнее, но перед началом давайте узнаем, что такое LLVM и для чего он тут нужен.
LLVM
LLVM (Low Level Virtual Machine) - огромный фреймворк для облегчения разработки компиляторов. Это не ноунейм фремворк - на его основе разработаны компиляторы C/C++, Swift, Rust, ранние версии Golang и еще много других. Комиплятор - это самая сложная вариация языка, потому что тот превращает Ваш высокоуровневый код в нативный бинарь, состоящий из ассемблерных инструкций. Так почему же это сложно? Потому что процессоры не имеют единой архитектуры, а значит процы на разных архитектурах имеют разные инструкции. Плюс ко всему ассемблеры для разных ОС также могут различаться. Кроссплатформенный компилятор обязан брать на себя всю эту рутину и переводить код в бинарь с инструкциями, соответствующими инструкциям Вашего процессора. Это сильно усложняет жизнь разработчикам компиляторов. Однако умные люди примерно 22 года назад начали разрабатывать LLVM - фреймворк, который берет всё выше сказанное на себя. Это бэкенд компилятора. LLVM генерирует не просто бинарь под любую платформу, а ещё и высокооптимизированный бинарь под любую платформу. Жизнь разработчика компиляторов упрощается в разы, ведь ему остается написать только синтаксис и семантику. LLVM также предоставляет и инструменты, которые также сильно упрощают разработку, например: вывод ошибок в стиле clang, инструменты для работы с командной строкой и много чего ещё (я просто не знаю, что ещё есть, но верю, что есть ещё много всего). Работа LLVM проста: он предоставляет апи для создания так называемого IR (Intermediated Representation - Промежуточное Представление) кода. IR это низкоуровневое представление Вашего высокоуровневого кода в виде более простых инструкций. Это то же самое, что разбить сложную задачу на более примитивные, и затем решать примитивные задачи. Сначала генерируется IR, затем он оптимизируется, а уже потом он переводится в бинарь. Это намного проще и правильнее, чем переводить высокоуровневый код сразу в бинарь, ведь высокоуровневый код - большая задача, а IR - примитивные подзадачи, которые будут понятны всем.
Лексер
Что такое файл? Знаю, странный вопрос, но простыми словами файл - одномерный массив символов (проще говоря строка). Поэтому программа не знает ни о каких строках и столбцах, которые мы видим в любом текстовом редакторе. Но эти координаты символов можно считать внутри программы. Однако нам не за чем считать строку и столбец каждого символа, ведь есть LLVM (если я буду писать статьи по другим видам языков, то там будут представлены методы определения координат символов без средств LLVM). LLVM предоставляет класс llvm::SourceMgr, который является самым главным во всем компиляторе. Он нужен для хранения исходного кода программы на Вашем высокоуровневом языке. На его основе мы получим позицию любого символа в файле с помощью класса llvm::SMLoc, который под капотом хранит указатель на символ из исходника в SourceMgr.
Мы научились определять позиции символов, но что нам это даст? Правильно, пока что ничего. В программе могут быть пробелы, табы, комментарии и куча всего ещё, что мы должны игнорировать, поэтому нам надо разбить высокоуровневый код (длинная строка) во что-то более простое, что сразу имеет ценную для нас информацию. Таким образом мы получаем минимальную единицу лексического анализатора - токен. Токен - просто контейнер с нужными нам данными: тип токена, его строковое представлене и координаты (тот самый llvm::SMLoc). Вот пример того, как будет в��глядеть токен:
enum TokenKind {
TkId, // identifier
TkVar, // keyword `var`
TkConst, // keyword `const`
TkBool, // keyword `bool`
TkChar, // keyword `char`
TkI16, // keyword `i16`
TkI32, // keyword `i32`
TkI64, // keyword `i64`
TkF32, // keyword `f32`
TkF64, // keyword `f64`
TkNoth, // keyword `noth`
TkFun, // keyword `fun`
TkRet, // keyword `return`
TkIf, // keyword `if`
TkElse, // keyword `else`
TkFor, // keyword `for`
TkBreak, // keyword `break`
TkContinue, // keyword `continue`
TkStruct, // keyword `struct`
TkPub, // keyword `pub`
TkBoolLit, // bool literal
TkCharLit, // character literal
TkI16Lit, // short literal
TkI32Lit, // int literal
TkI64Lit, // long literal
TkF32Lit, // float literal
TkF64Lit, // double literal
TkStrLit, // string literal
TkSemi, // `;`
TkComma, // `,`
TkDot, // `.`
TkLParen, // `(`
TkRParen, // `)`
TkLBrace, // `}`
TkRBrace, // `{`
TkLBracket, // `[`
TkRBracket, // `]`
TkAt, // `@`
TkTilde, // `~`
TkQuestion, // `?`
TkColon, // `:`
TkDollar, // `$`
TkEq, // `=`
TkBang, // `!`
TkNotEq, // `!=`
TkAnd, // '&`
TkOr, // `|`
TkLogAnd, // '&&`
TkLogOr, // `||`
TkPlus, // `+`
TkMinus, // `-`
TkStar, // `*`
TkSlash, // `/`
TkPercent, // `%`
TkPlusEq, // `+=`
TkMinusEq, // `-=`
TkStarEq, // `*=`
TkSlashEq, // `/=`
TkPercentEq, // `%=`
TkEqEq, // `==`
TkLt, // `<`
TkGt, // `>`
TkLtEq, // `<=`
TkGtEq, // `>=`
TkCarret, // `^`
TkEof,
TkUnknown, // Unknown token, not expected by the lexer
};
class Token {
TokenKind _kind;
llvm::StringRef _text;
llvm::SMLoc _loc;
public:
explicit Token(TokenKind kind, llvm::StringRef text, llvm::SMLoc loc)
: _kind(kind), _text(text), _loc(loc) {}
const TokenKind
GetKind() const {
return _kind;
}
const llvm::StringRef
GetText() const {
return _text;
}
const llvm::SMLoc
GetLoc() const {
return _loc;
}
bool
Is(TokenKind kind) {
return _kind == kind;
}
};llvm::StringRef - упрощенная вариация std::string (под капотом - обычный указатель на символ и поле с длинной). llvm::StringRef может переводиться в std::string, так что не переживаем.
Теперь как эти токены создавать? Для этого нам и нужен лексер. Лексер имеет под капотом ссылку на тот самый llvm::SourceMgr, чтобы оттуда получать llvm::SMLoc для токенов. Лексер должен уметь:
Токенизировать идентификаторы (в том числе и ключевые слова)
Токенизировать числовые литералы
Токенизировать строковые литералы
Токенизировать символьные литералы
Токенизировать операторы и специальные символы (которые могут понадобится языку)
Как обучить лексер так делать? Щас разберемся, а пока что накидаем каркас лексера:
class Lexer {
llvm::SourceMgr &_srcMgr;
DiagnosticEngine &_diag;
unsigned _curBuf;
const char *_bufStart;
const char *_curPtr;
public:
explicit Lexer(llvm::SourceMgr &mgr, DiagnosticEngine &diag)
: _srcMgr(mgr), _diag(diag) {
_curBuf = _srcMgr.getMainFileID();
auto *buf = _srcMgr.getMemoryBuffer(_curBuf);
_bufStart = buf->getBufferStart();
_curPtr = _bufStart;
}
Token
NextToken();
private:
Token
tokenizeId(const char *tokStart);
Token
tokenizeNumLit(const char *tokStart);
Token
tokenizeStrLit(const char *tokStart);
Token
tokenizeCharLit(const char *tokStart);
Token
tokenizeOp(const char *tokStart);
void
skipComments();
const char
getEscapeSecuence(const char *tokStart);
};DiagnosticEngine?...
Диагностика
Мы перескочили на другой раздел, скоро вернемся к лексеру. Диагностика - это вывод ошибок на экран. Вывод должен быть понятным и четким: четкое предложение с ошибкой, строка, в которой произошла ошибка, точные координаты в файле, где произошла ошибка, и выделение области ошибки. Движок рендера таких сообщений - сложная тема, однако LLVM создали такой рендер за нас. Этот рендер использует clang для вывода ошибок, теперь и мы будем использовать. Но помимо вывода нужно ещё и сделать приятное создание ошибки из кода (то есть API). Система очень хитрая и элегантная (ну как мне кажется):
class DiagnosticEngine {
llvm::SourceMgr &_srcMgr;
bool _hasErrors = false;
public:
explicit DiagnosticEngine(llvm::SourceMgr &mgr)
: _srcMgr(mgr) {}
DiagnosticBuilder
Report(llvm::SMLoc loc, DiagKind kind) {
_hasErrors = true;
return DiagnosticBuilder(_srcMgr, loc, GetDiagInfo(kind));
}
bool
HasErrors() const {
return _hasErrors;
}
void
ResetErrors() {
_hasErrors = false;
}
};class DiagnosticBuilder {
llvm::SourceMgr &_srcMgr;
llvm::SMLoc _loc;
DiagInfo _info;
std::vector<std::string> _args;
std::vector<llvm::SMRange> _ranges;
bool _isActive = true;
public:
explicit DiagnosticBuilder(llvm::SourceMgr &mgr, llvm::SMLoc loc, DiagInfo info)
: _srcMgr(mgr), _loc(loc), _info(info) {}
DiagnosticBuilder(DiagnosticBuilder &&other)
: _srcMgr(other._srcMgr), _loc(other._loc), _info(other._info),
_args(other._args), _ranges(other._ranges),
_isActive(other._isActive) {
other._isActive = false;
}
~DiagnosticBuilder();
DiagnosticBuilder &
operator<<(llvm::StringRef s);
DiagnosticBuilder &
operator<<(llvm::SMRange r);
DiagnosticBuilder &
operator<<(long n);
DiagnosticBuilder &
operator<<(char c);
DiagnosticBuilder &
operator<<(size_t s);
};struct DiagInfo {
const llvm::SourceMgr::DiagKind Kind;
const char *Format;
explicit DiagInfo(llvm::SourceMgr::DiagKind kind, const char *format)
: Kind(kind), Format(format) {}
};
DiagInfo
GetDiagInfo(DiagKind kind);enum DiagKind {
// errors, warnings and notes
ErrIntegerSuffixForFloatingPoint,
ErrUnsupportedEscapeSequence,
ErrCharLitLen,
ErrExpectedExpr,
ErrExpectedStmt,
ErrExpectedToken,
ErrExpectedId,
ErrExpectedType,
ErrUndeclaredVariable,
ErrUndeclaredFuntion,
ErrRedefinitionVar,
ErrRedefinitionFun,
ErrTypeMismatchNotNum,
ErrTypeMismatchNotBool,
ErrCannotCast,
ErrUnsupportedTypeForOperator,
ErrNotAllPathsReturnsValue,
ErrFuntionCannotReturnValue,
ErrFewArgs,
ErrAssignmentConst
};Что тут происходит собственно. Вывод ошибок осуществляется так: по значению DiagKind определяется строка ошибки, например, для ErrExpectedToken мы получим строку "expected '%0', but got '%1'". Что означают %0 и %1? Это индексы аргументов, которые мы передаем диагностике. Каждая ошибка может запрашивать какую-то информацию для вывода в качестве строки, и мы можем их передавать, а они в свою очередь подставятся вместо %0, %1 и тд. DiagInfo это контейнер для хранения той самой форматной строки вывода, а также тип для вывода (llvm::SourceMgr::DiagKind). В контексте LLVM llvm::SourceMgr::DiagKind это вывод: ошибки, предупреждения, ремарки, обычного сообщения. Функция GetDiagInfo нужна для того, чтобы перевести наш DiagKind в DiagInfo с соответствующим типом llvm::SourceMgr::DiagKind и форматной строкой:
DiagInfo
GetDiagInfo(DiagKind kind) {
#define ERR(msg) DiagInfo(llvm::SourceMgr::DiagKind::DK_Error, msg)
switch (kind) {
case ErrIntegerSuffixForFloatingPoint:
return ERR("using the `%0` suffix for floating point numeric literal");
case ErrUnsupportedEscapeSequence:
return ERR("escape-sequence `\\%0` is not supported");
case ErrCharLitLen:
return ERR("character literal `%0` must have a length equal to 1");
case ErrExpectedExpr:
return ERR("expected expression, but got `%0`");
case ErrExpectedStmt:
return ERR("expected statement, but got `%0`");
case ErrExpectedToken:
return ERR("expected `%0`, but got `%1`");
case ErrExpectedId:
return ERR("expected identifier, but got `%0`");
case ErrExpectedType:
return ERR("expected type, but got `%0`");
case ErrUndeclaredVariable:
return ERR("variable `%0` is undeclared");
case ErrUndeclaredFuntion:
return ERR("function `%0` is undeclared");
case ErrRedefinitionVar:
return ERR("redefinition the variable `%0`");
case ErrRedefinitionFun:
return ERR("redefinition the function `%0`");
case ErrTypeMismatchNotNum:
return ERR("expected number, but got `%0`");
case ErrTypeMismatchNotBool:
return ERR("expected bool, but got `%0`");
case ErrCannotCast:
return ERR("cannot implicitly cast `%0` to `%1`");
case ErrUnsupportedTypeForOperator:
return ERR("operator `%0` does not support types `%1` and `%2`");
case ErrNotAllPathsReturnsValue:
return ERR("not all paths return a value");
case ErrFuntionCannotReturnValue:
return ERR("function cannot return a value");
case ErrFewArgs:
return ERR("function `%0` expected %1 arguments, but received %2");
case ErrAssignmentConst:
return ERR("assigning a value to a constant");
}
}вернемся к DiagnosticBuilder, что это? Это временный объект, который создается при вызове DiagnosticEngine::Report, чтобы задавать аргументы для вывода. Перегрузки операторов << внутри DiagnosticBuilder позволяют ему правильно обрабатывать возможные аргументы для вывода (переводить их в строки и сохранять в _args). Конструктор перемещения позволяет передать всё управление на новый объект, чтобы только один DiagnosticBuilder мог здесь и сейчас обрабатывать форматирование ошибки. В деструкторе DiagnosticBuilder он выводит все накопленные параметры:
DiagnosticBuilder::~DiagnosticBuilder() {
if (!_isActive) {
return;
}
std::string msg = _info.Format;
for (size_t i = 0; i < _args.size(); ++i) {
std::string placeholder = "%" + std::to_string(i);
size_t pos = msg.find(placeholder);
if (pos != std::string::npos) {
msg.replace(pos, placeholder.length(), _args[i]);
}
}
_srcMgr.PrintMessage(_loc, _info.Kind, msg, _ranges);
}
DiagnosticBuilder &
DiagnosticBuilder::operator<<(llvm::StringRef s) {
_args.push_back(s.str());
return *this;
}
DiagnosticBuilder &
DiagnosticBuilder::operator<<(llvm::SMRange r) {
_ranges.push_back(r);
return *this;
}
DiagnosticBuilder &
DiagnosticBuilder::operator<<(long n) {
_args.push_back(std::to_string(n));
return *this;
}
DiagnosticBuilder &
DiagnosticBuilder::operator<<(char c) {
_args.push_back(std::string(1, c));
return *this;
}
DiagnosticBuilder &
DiagnosticBuilder::operator<<(size_t s) {
_args.push_back(std::to_string(s));
return *this;
}В будущем я планирую переписать рендер с нуля, но пока что мы можем довольствовоться только LLVM-style выводом, который осуществляется только с помощью одной строки:
_srcMgr.PrintMessage(_loc, _info.Kind, msg, _ranges);Но погодите-ка, а что такое _ranges? LLVM умеет подчеркивать необходимую область с помощью ~, но пока мы сами не скажем ему, сколько и где подчеркивать, он этого не сделает. Поэтому нам пригодится класс llvm::SMRange, который под капотом является просто контейнером двух llvm::SMLoc: начальная позиция и конечная. Теперь можно возвращаться к лексеру.
Лексер (ещё раз)
Вернемся к нашим баранам и разберем лексер. Суть его работы в том, чтобы посмотреть на текущий символ и понять, какой это потенциально возможный токен. Давайте подумаем логически: если мы увидим символ ", то что он означает в коде? Правильно, это начало строкового литерала, который заканчивается на такой же символ ", значит мы пропустим текущий (чтобы он не учитывался) и будем сохранять себе в "память" все следующие символы, пока не наткнемся на ещё один " (затем пропустим его, чтобы не мешался под ногами). Если мы увидим, к примеру, символ 1, то что он будет означать? Правильно, это числовой литерал, но какое это число: целое или дробное? Чтобы понять это, нужно "съесть" все символы цифр и точки (потенциальное дробное число) и проанализировать всё то, что съел лексер. Понимаем примерную концепцию? Отлично, теперь продолжим анализ скелета лексера. curBuf и bufStart нужны только llvm::SourceMgr для своей работы, поэтому трогать их не будем. Нас интересует _curPtr. Это поле, которое хранит значение текущего символа для анализа. Именно его мы будем сравнивать с другими символами, чтобы понять как создать токен. Методы по типу tokenizeId и tokenizeNumLit как раз таки обрабатывают текущий символ так, как они проектировались, а вот метод NextToken нужен для того, чтобы проанализировать текущий символ в лексере и выдать токен, который ему соответствует.
Но погодите-ка, NextToken возвращает лишь один токен, почему нельзя было сделать возврат всего списка токенов, которые только сможет создать лексер? Зачем мелочиться? Производительность. std::vector::push_back может делать реаллокации, которые слегка дорогие и много потребляющие. Зачем это делать, когда возврат всего одного токена не будет так сильно трогать кучу? Вот вам и оптимизация, а ведь это важно для компиляторов. Есть ещё одна причина, по которой просто логичнее возвращать лишь один токен: парсеру больше и не надо. Парсер анализирует все токены и выстраивает синтаксис из них, ему даже знать не надо о том, какие там токены были раньше и какие позже. Его интересует только текущий токен и следующий (чтобы отличить, например, x, от x()), а значит и больше ему не надо.
Token
Lexer::NextToken() {
while (*_curPtr == ' ' || *_curPtr == '\n' || *_curPtr == '\t' || *_curPtr == '\r') {
++_curPtr;
}
const char *tokStart = _curPtr;
if (*tokStart == '\0') {
return Token(TkEof, "", llvm::SMLoc::getFromPointer(tokStart));
}
if (isalpha(*tokStart) || *tokStart == '_') {
return tokenizeId(tokStart);
}
if (isdigit(*tokStart)) {
return tokenizeNumLit(tokStart);
}
if (*tokStart == '\"') {
return tokenizeStrLit(tokStart);
}
if (*tokStart == '\'') {
return tokenizeCharLit(tokStart);
}
if (*tokStart == '/' && (*(tokStart + 1) == '/' || *(tokStart + 1) == '*')) {
skipComments();
return NextToken();
}
return tokenizeOp(tokStart);
}
Token
Lexer::tokenizeId(const char *tokStart) {
while (*_curPtr != '\0' && (isalnum(*_curPtr) || *_curPtr == '_')) {
++_curPtr;
}
llvm::StringRef text(tokStart, _curPtr - tokStart);
if (keywords.find(text.str()) != keywords.end()) {
return Token(keywords.at(text.str()), text, llvm::SMLoc::getFromPointer(tokStart));
}
return Token(TkId, text, llvm::SMLoc::getFromPointer(tokStart));
}
Token
Lexer::tokenizeNumLit(const char *tokStart) {
bool hasDot = false;
while (*_curPtr != '\0' && (isdigit(*_curPtr) || *_curPtr == '.' && !hasDot)) {
if (*_curPtr == '.') {
hasDot = true;
}
++_curPtr;
}
llvm::StringRef text(tokStart, _curPtr - tokStart);
#define TOKEN(kind) Token(kind, text, llvm::SMLoc::getFromPointer(tokStart))
switch (tolower(*(_curPtr++))) { // skip suffix (maybe not suffix)
case 's':
if (hasDot) {
_diag.Report(llvm::SMLoc::getFromPointer(_curPtr - 1), ErrIntegerSuffixForFloatingPoint)
<< *(_curPtr - 1);
}
return TOKEN(TkI16);
case 'f':
return TOKEN(TkF32);
case 'd':
return TOKEN(TkF64);
}
--_curPtr; // returned, because the character is not a suffix
if (hasDot) {
return TOKEN(TkF64);
}
return TOKEN(TkI32Lit);
#undef TOKEN
}
Token
Lexer::tokenizeStrLit(const char *tokStart) {
++_curPtr; // skip "
std::string text;
while (*_curPtr != '\0' && *_curPtr != '\"') {
char c;
if (*_curPtr == '\\') {
c = getEscapeSecuence(++_curPtr);
}
else {
c = *(_curPtr++);
}
text += c;
}
++_curPtr; // skip "
return Token(TkStrLit, llvm::StringRef(tokStart, _curPtr - tokStart), llvm::SMLoc::getFromPointer(tokStart));
}
Token
Lexer::tokenizeCharLit(const char *tokStart) {
++_curPtr; // skip '
std::string text;
while (*_curPtr != '\0' && *_curPtr != '\'') {
char c;
if (*_curPtr == '\\') {
c = getEscapeSecuence(++_curPtr);
}
else {
c = *(_curPtr++);
}
text += c;
}
++_curPtr; // skip '
if (text.length() != 1) {
_diag.Report(llvm::SMLoc::getFromPointer(tokStart), ErrCharLitLen)
<< llvm::SMRange(llvm::SMLoc::getFromPointer(tokStart), llvm::SMLoc::getFromPointer(_curPtr))
<< "'" + text + "'";
}
return Token(TkCharLit, text, llvm::SMLoc::getFromPointer(tokStart));
}
Token
Lexer::tokenizeOp(const char *tokStart) {
switch (*(_curPtr++)) {
#define TOKEN(kind) Token(kind, llvm::StringRef(tokStart, _curPtr - tokStart), llvm::SMLoc::getFromPointer(tokStart))
case ';':
return TOKEN(TkSemi);
case ',':
return TOKEN(TkComma);
case '.':
return TOKEN(TkDot);
case '(':
return TOKEN(TkLParen);
case ')':
return TOKEN(TkRParen);
case '{':
return TOKEN(TkLBrace);
case '}':
return TOKEN(TkRBrace);
case '[':
return TOKEN(TkLBracket);
case ']':
return TOKEN(TkRBracket);
case '@':
return TOKEN(TkAt);
case '~':
return TOKEN(TkTilde);
case '?':
return TOKEN(TkQuestion);
case ':':
return TOKEN(TkColon);
case '$':
return TOKEN(TkDollar);
case '=':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkEqEq);
}
return TOKEN(TkEq);
case '!':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkNotEq);
}
return TOKEN(TkBang);
case '>':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkGtEq);
}
return TOKEN(TkGt);
case '<':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkLtEq);
}
return TOKEN(TkLt);
case '&':
if (*_curPtr == '&') {
++_curPtr;
return TOKEN(TkLogAnd);
}
return TOKEN(TkAnd);
case '|':
if (*_curPtr == '|') {
++_curPtr;
return TOKEN(TkLogOr);
}
return TOKEN(TkOr);
case '+':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkPlusEq);
}
return TOKEN(TkPlus);
case '-':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkMinusEq);
}
return TOKEN(TkMinus);
case '*':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkStarEq);
}
return TOKEN(TkStar);
case '/':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkSlashEq);
}
return TOKEN(TkSlash);
case '%':
if (*_curPtr == '=') {
++_curPtr;
return TOKEN(TkPercentEq);
}
return TOKEN(TkPercent);
case '^':
return TOKEN(TkCarret);
default:
return TOKEN(TkUnknown);
}
}
void
Lexer::skipComments() {
_curPtr += 2;
bool isMultilineComment = *(_curPtr - 1) == '*';
if (isMultilineComment) {
while (*_curPtr != '\0' && (*_curPtr != '*' || *(_curPtr + 1) != '/')) {
++_curPtr;
}
_curPtr += 2;
}
else {
while (*_curPtr != '\0' && *_curPtr != '\n') {
++_curPtr;
}
}
}
const char
Lexer::getEscapeSecuence(const char *tokStart) {
switch (*(_curPtr++)) {
case 'a':
return '\a';
case 'b':
return '\b';
case 'e':
return '\e';
case 'f':
return '\f';
case 'r':
return '\r';
case 'n':
return '\n';
case 't':
return '\t';
case 'v':
return '\v';
case '\\':
return '\\';
case '\'':
return '\'';
case '\"':
return '\"';
case '\?':
return '\?';
case '0':
return '\0';
default:
--_curPtr;
_diag.Report(llvm::SMLoc::getFromPointer(tokStart), ErrUnsupportedEscapeSequence)
<< llvm::SMRange(llvm::SMLoc::getFromPointer(tokStart - 1), llvm::SMLoc::getFromPointer(tokStart))
<< *tokStart;
return *tokStart;
}
}Префиксные инкремент и декремент это тоже оптимизация. Вот пример того, как выглядит пефиксный и инфиксный инкременты:
// prefix increment
int x = 0;
// int y = ++x;
x = x + 1;
int y = x;// infix increment
int x = 0;
// int y = x++;
int x_tmp = x;
x = x + 1;
int y = x_tmp;Казалось бы разница незначительная, но в 4 строке второго примера происходит копирование объекта (x) в переменную x_tmp. Да, с числами это работает быстро (но всё равно медленнее п��ефиксного инкремента), но что будет, если добавить перегрузку на инкремент/декремент массивному объекту?... Необратимая потеря в скорости. Остались кейворды:
static std::unordered_map<std::string, TokenKind> keywords {
{ "false", TkBoolLit },
{ "true", TkBoolLit },
{ "var", TkVar },
{ "const", TkConst },
{ "bool", TkBool },
{ "char", TkChar },
{ "i16", TkI16 },
{ "i32", TkI32 },
{ "i64", TkI64 },
{ "f32", TkF32 },
{ "f64", TkF64 },
{ "noth", TkNoth },
{ "fun", TkFun },
{ "return", TkRet },
{ "if", TkIf },
{ "else", TkElse },
{ "for", TkFor },
{ "break", TkBreak },
{ "continue", TkContinue },
{ "struct", TkStruct },
{ "pub", TkPub },
};Если при анализе идентификаторов иы найдем его значение в этой мапе, то это кейворд и мы создадим токен не с типом TkId, а с типом, соответствующий типу из мапы. Лексер на этом зачанчивается, это было просто, не так ли? Теперь парсер.
Парсер
Парсер это подсистема, которая выстраивает синтаксис вашему языку. Я хочу, чтобы переменные определялись так:
var a: i32 = 10;
var b: char;А вот потому что хочу, кто мне помешает? Именно парсер выстраивает синтаксис для таких операций. Но ведь эти инструкции надо где-то и как-то хранить, так? Да, для этого и придумали AST (Abstract Synyax Tree - Абстрактное Синтаксическое Дерево). AST это абстрактный набор "инструкций" нашего языка, из которых состоит программа на нашем языке. AST это в первую очередь дерево, а значит оно должно состоять из базовых нод, от которых будут расти ветви дальше:
enum NodeKind {
NkStartStmts,
NkVarDeclStmt,
NkVarAsgnStmt,
NkFunDeclStmt,
NkFunCallStmt,
NkRetStmt,
NkEndStmts,
NkStartExprs,
NkBinaryExpr,
NkUnaryExpr,
NkVarExpr,
NkLiteralExpr,
NkFunCallExpr,
NkEndExprs,
};
class Node {
const NodeKind _kind;
llvm::SMLoc _startLoc;
llvm::SMLoc _endLoc;
public:
explicit Node(NodeKind kind, llvm::SMLoc startLoc, llvm::SMLoc endLoc)
: _kind(kind), _startLoc(startLoc), _endLoc(endLoc) {}
virtual ~Node() = default;
NodeKind
GetKind() const {
return _kind;
}
const llvm::SMLoc
GetStartLoc() const {
return _startLoc;
}
const llvm::SMLoc
GetEndLoc() const {
return _endLoc;
}
void
SetStartLoc(llvm::SMLoc startLoc) {
_startLoc = startLoc;
}
void
SetEndLoc(llvm::SMLoc endLoc) {
_endLoc = endLoc;
}
};Нода это объект, который хранит тип ноды, а также координаты её начала и конца. Node - базовый класс, от которого будут наследоваться остальные узлы AST, например, базовый класс инструкции (Stmt):
class Stmt : public Node {
public:
explicit Stmt(NodeKind kind, llvm::SMLoc startLoc, llvm::SMLoc endLoc)
: Node(kind, startLoc, endLoc) {}
constexpr static bool
classof(const Node *node) {
return node->GetKind() > NkStartStmts && node->GetKind() < NkEndStmts;
}
};Или базовый класс выражения (Expr):
class Expr : public Node {
public:
explicit Expr(NodeKind kind, llvm::SMLoc startLoc, llvm::SMLoc endLoc)
: Node(kind, startLoc, endLoc) {}
constexpr static bool
classof(const Node *node) {
return node->GetKind() > NkStartExprs && node->GetKind() < NkEndExprs;
}
};Я уже слышу ваши вопросы по поводу classof, что же это такое? Это очередная примочка LLVM API, не удивляемся. В C++ существует оператор dynamic_cast, который мог бы нам подойти, но он работает только с полиморфными классами, а это много методов в виртуальной таблице методов, что просто ужасно для производительности. Нам это надо? Нет конечно. Вот и разработчики LLVM думали также и сделали свой llvm::dyn_cast. Его прикол в том, что он работает также, как и dynamic_cast, но при этом не требует полиморфности объекта: он требует лишь наличие статического метода classof, который сможет сказать, равны ли д��нные объекты, и если равны, LLVM сам с ними порабоатет и вернет нам тот объект, который мы и запрашивали. Такие выходки называются статическим полиморфизмом и не требуют методов из виртуальной таблицы, что добавляет +1 к производительности. Теперь пора делать реальные AST узлы, с которыми уже и будем взаимодействовать, например, узел для определения переменной:
class VarDeclStmt : public Stmt {
llvm::StringRef _name;
bool _isConst;
ASTType _type;
Expr *_expr;
public:
explicit VarDeclStmt(llvm::StringRef name, bool isConst, ASTType type, Expr *expr, llvm::SMLoc startLoc, llvm::SMLoc endLoc)
: _name(name), _type(type), _isConst(isConst), _expr(expr), Stmt(NkVarDeclStmt, startLoc, endLoc) {}
constexpr static bool
classof(const onyx::Node *node) {
return node->GetKind() == NkVarDeclStmt;
}
llvm::StringRef
GetName() const {
return _name;
}
bool
IsConst() const {
return _isConst;
}
ASTType
GetType() const {
return _type;
}
Expr *
GetExpr() const {
return _expr;
}
};Согласитесь, это действительно не сложно. Вопрос только в другом: а как будут хранится выражения и откуда взялся ASTType? Всё по порядку.
Выражения - самое главное, что должен уметь обрабатывать парсер. Выражение вида 2 + 3 * 4 всегда можно разложить на простые состовляющие - литералы, вызовы функций или значения переменных. Приоритет операторов играет ключевую роль в построении AST, поэтому парсер должен уметь определять приоритет. Парсер мы пока что не рассматриваем, рассматриваем только узлы AST и вспомогательные инструменты, один из которых ASTType:
enum class ASTTypeKind {
Bool,
Char,
I16,
I32,
I64,
F32,
F64,
Noth
};
class ASTType {
ASTTypeKind _kind;
llvm::StringRef _val;
bool _isConst;
public:
explicit ASTType(ASTTypeKind kind, llvm::StringRef val, bool isConst)
: _kind(kind), _val(val), _isConst(isConst) {}
bool
operator==(ASTType &other) {
return _kind == other._kind && _val == other._val;
}
ASTTypeKind
GetTypeKind() const {
return _kind;
}
llvm::StringRef
GetVal() const {
return _val;
}
bool
IsConst() const {
return _isConst;
}
std::string
ToString() const {
std::string val;
if (_isConst) {
val += "const ";
}
val += _val;
return val;
}
static ASTType
GetNothType() {
return ASTType(ASTTypeKind::Noth, "noth", false);
}
static ASTType
GetCommon(ASTType lhs, ASTType rhs) {
if (lhs.GetTypeKind() >= ASTTypeKind::Bool && lhs.GetTypeKind() <= ASTTypeKind::F64 &&
rhs.GetTypeKind() >= ASTTypeKind::Bool && rhs.GetTypeKind() <= ASTTypeKind::F64) {
return lhs.GetTypeKind() > rhs.GetTypeKind() ? lhs : rhs;
}
return GetNothType();
}
static bool
HasCommon(ASTType lhs, ASTType rhs) {
if (lhs.GetTypeKind() >= ASTTypeKind::Bool && lhs.GetTypeKind() <= ASTTypeKind::F64 &&
rhs.GetTypeKind() >= ASTTypeKind::Bool && rhs.GetTypeKind() <= ASTTypeKind::F64) {
return true;
}
return false;
}
};Это простейший класс для хранения типа (будь то i32 или какой-нибудь пользовательский). От зависит ещё один интересный класс, который хранит внутри себя уже сами значения - ASTVal:
union ASTValData {
bool boolVal;
char charVal;
short i16Val;
int i32Val;
long i64Val;
float f32Val;
double f64Val;
};
class ASTVal {
ASTType _type;
ASTValData _data;
public:
explicit ASTVal(ASTType type, ASTValData data)
: _type(type), _data(data) {}
ASTType
GetType() const {
return _type;
}
ASTValData
GetData() const {
return _data;
}
std::string
ToString() const;
double
AsDouble() const;
ASTVal
Cast(ASTType type);
static ASTVal
GetVal(double val, ASTType type);
static ASTVal
GetDefaultByType(ASTType type);
};std::string
ASTVal::ToString() const {
switch (_type.GetTypeKind()) {
#define TO_STR(field) std::to_string(_data.field)
case ASTTypeKind::Bool:
return TO_STR(boolVal);
case ASTTypeKind::Char:
return TO_STR(charVal);
case ASTTypeKind::I16:
return TO_STR(i16Val);
case ASTTypeKind::I32:
return TO_STR(i32Val);
case ASTTypeKind::I64:
return TO_STR(i64Val);
case ASTTypeKind::F32:
return TO_STR(f32Val);
case ASTTypeKind::F64:
return TO_STR(f64Val);
case ASTTypeKind::Noth:
return "<noth>";
}
}
double
ASTVal::AsDouble() const {
switch (_type.GetTypeKind()) {
case ASTTypeKind::Bool:
return _data.boolVal;
case ASTTypeKind::Char:
return _data.charVal;
case ASTTypeKind::I16:
return _data.i16Val;
case ASTTypeKind::I32:
return _data.i32Val;
case ASTTypeKind::I64:
return _data.i64Val;
case ASTTypeKind::F32:
return _data.f32Val;
case ASTTypeKind::F64:
return _data.f64Val;
case ASTTypeKind::Noth:
return 0;
}
}
ASTVal
ASTVal::Cast(ASTType type) {
if (_type == type) {
return *this;
}
if (_type.GetTypeKind() >= ASTTypeKind::Char && _type.GetTypeKind() <= ASTTypeKind::F64 &&
type.GetTypeKind() >= ASTTypeKind::Char && type.GetTypeKind() <= ASTTypeKind::F64) {
switch (type.GetTypeKind()) {
#define VAL(field, cast_type) ASTVal(type, ASTValData { .field = static_cast<cast_type>(AsDouble()) })
case ASTTypeKind::Char:
return VAL(charVal, char);
case ASTTypeKind::I16:
return VAL(i16Val, short);
case ASTTypeKind::I32:
return VAL(i32Val, int);
case ASTTypeKind::I64:
return VAL(i64Val, long);
case ASTTypeKind::F32:
return VAL(f32Val, float);
case ASTTypeKind::F64:
return VAL(f64Val, double);
}
}
return ASTVal::GetDefaultByType(ASTType::GetNothType());
}
ASTVal
ASTVal::GetVal(double val, ASTType type) {
switch (type.GetTypeKind()) {
#define VAL(field, cast_type) ASTVal(type, ASTValData { .field = static_cast<cast_type>(val) })
case ASTTypeKind::Bool:
return VAL(boolVal, bool);
case ASTTypeKind::Char:
return VAL(charVal, char);
case ASTTypeKind::I16:
return VAL(i16Val, short);
case ASTTypeKind::I32:
return VAL(i32Val, int);
case ASTTypeKind::I64:
return VAL(i64Val, long);
case ASTTypeKind::F32:
return VAL(f32Val, float);
case ASTTypeKind::F64:
return VAL(f64Val, double);
case ASTTypeKind::Noth:
return ASTVal(type, ASTValData { .i32Val = 0 });
#undef VAL
}
}
ASTVal
ASTVal::GetDefaultByType(ASTType type) {
switch (type.GetTypeKind()) {
#define VAL(field) ASTVal(type, ASTValData { .field = 0 })
case ASTTypeKind::Bool:
return VAL(boolVal);
case ASTTypeKind::Char:
return VAL(charVal);
case ASTTypeKind::I16:
return VAL(i16Val);
case ASTTypeKind::I32:
return VAL(i32Val);
case ASTTypeKind::I64:
return VAL(i64Val);
case ASTTypeKind::F32:
return VAL(f32Val);
case ASTTypeKind::F64:
return VAL(f64Val);
case ASTTypeKind::Noth:
return ASTVal(type, ASTValData { .i32Val = 0 });
#undef VAL
}
}Он нужен для того, чтобы хранить значения в литералах, вот кстати и литерал:
class LiteralExpr : public Expr {
ASTVal _val;
public:
explicit LiteralExpr(ASTVal val, llvm::SMLoc startLoc, llvm::SMLoc endLoc)
: _val(val), Expr(NkLiteralExpr, startLoc, endLoc) {}
constexpr static bool
classof(const Node *node) {
return node->GetKind() == NkLiteralExpr;
}
ASTVal
GetVal() const {
return _val;
}
};Максимально простой класс, на котором держаться все возможные выражения в языке. Остальные узлы выражений не представляют из себя что-то интересного. Например VarExpr - узел, который говорит, что мы пытаемся получить значение переменной, хранит внутри себя лишь имя переменной, к которой пытаемся обратиться. UnaryExpr и BinaryExpr - выражения унарных (оператор, затем единственный операнд) или бинарных (левый операнд, оператор, затем правый операнд) операций соответственно. На них останавливаться не будем и сразу перейдем к парсеру.
Во первых, давайте добавим ещё немного оптимизаций. Мы будем взаимодействовать с указателями на Stmt или Expr, чтобы сохранить иерархию наследования, но эти указатели должны быть где-то созданы в памяти. Простейший способ - создавать их в куче, но у такого способа есть побочки в виде ручного удаления объектов после компиляции. К тому же это медленно - куча всё таки. Компиляторы практикуют другую интересную игрушку - Arena Allocator. Арена - большой кусок выделенной памяти, внутри которого создаются объекты. Чтобы создать объект внутри арены под капотом просто записываются нужные значения в и так уже выделенный кусок памяти, поэтому такая операция почти не затратна. Плюс ко всему арены избавляют нас от мучительного удаления каждого узла AST, ведь в конце работы компилятора очищается вся арена целиком, которая внутри себя содержала те самые AST узлы. Остается понять, как такой аллокатор изобрести, или... LLVM и тут поможет с его llvm::BumpPtrAllocator. Давайте выстроим минимальный каркас парсеру (актуален на момент написания статьи):
class Parser {
Lexer &_lex;
DiagnosticEngine &_diag;
Token _curTok;
Token _nextTok;
llvm::BumpPtrAllocator _allocator;
public:
explicit Parser(Lexer &lex, DiagnosticEngine &diag)
: _lex(lex), _diag(diag), _curTok(Token(TkUnknown, "", llvm::SMLoc())),
_nextTok(Token(TkUnknown, "", llvm::SMLoc())) {
consume();
consume();
}
Stmt *
ParseStmt();
private:
template<typename T, typename ...Args>
T *
createNode(Args &&... args);
Stmt *
parseVarDeclStmt();
Stmt *
parseVarAsgn();
Stmt *
parseFunDeclStmt();
Stmt *
parseFunCallStmt();
Stmt *
parseRetStmt();
Argument
parseArgument();
Expr *
parsePrefixExpr();
Expr *
parseExpr(int minPrec);
Token
consume();
ASTType
consumeType();
Expr *
createCompoundAssignmentOp(Token op, Expr *base, Expr *expr);
bool
expect(TokenKind kind);
bool
isAssignmentOp(TokenKind kind);
llvm::SMRange
getRangeFromTok(Token tok) const;
};Тут то нам и прикодится лексер, а также те самые _curTok и _nextTok. Хм, что же такое createNode? Это метод для создания AST узла в специальном аллокаторе от LLVM:
template <typename T, typename ...Args>
T *
Parser::createNode(Args &&... args) {
void *mem = _allocator.Allocate<T>();
return new (mem) T(std::forward<Args>(args)...);
}Ничего сложного. Теперь давайте всё-таки рассмотрим весь парсер целиком:
Stmt *
Parser::ParseStmt() {
if (_curTok.Is(TkEof)) {
return nullptr;
}
switch (_curTok.GetKind()) {
case TkVar:
case TkConst:
return parseVarDeclStmt();
case TkFun:
return parseFunDeclStmt();
case TkRet:
return parseRetStmt();
case TkId:
if (_nextTok.Is(TkLParen)) {
return parseFunCallStmt();
}
return parseVarAsgn();
default:
_diag.Report(_curTok.GetLoc(), ErrExpectedStmt)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
consume();
return nullptr;
}
}
template <typename T, typename ...Args>
T *
Parser::createNode(Args &&... args) {
void *mem = _allocator.Allocate<T>();
return new (mem) T(std::forward<Args>(args)...);
}
Stmt *
Parser::parseVarDeclStmt() {
Token firstTok = _curTok;
bool isConst = consume().Is(TkConst);
llvm::StringRef name = _curTok.GetText();
if (!expect(TkId)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedId)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
}
if (!expect(TkColon)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ":" // expected
<< _curTok.GetText(); // got
}
ASTType type = consumeType();
Expr *expr = nullptr;
if (expect(TkEq)) {
expr = parseExpr(PrecLowest);
}
if (!expect(TkSemi)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ";" // expected
<< _curTok.GetText(); // got
}
return createNode<VarDeclStmt>(name, isConst, type, expr, firstTok.GetLoc(), _curTok.GetLoc());
}
Stmt *
Parser::parseVarAsgn() {
Token nameToken = consume();
if (!isAssignmentOp(_curTok.GetKind())) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "=` or `+=` or `-=` or `*=` or `/=` or `%="
<< _curTok.GetText().str();
}
Token op = consume();
Expr *expr = parseExpr(PrecLowest);
if (!expect(TkSemi)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ";" // expected
<< _curTok.GetText(); // got
}
if (op.GetKind() != TkEq && isAssignmentOp(op.GetKind())) {
expr = createCompoundAssignmentOp(op, createNode<VarExpr>(nameToken.GetText(), nameToken.GetLoc(), op.GetLoc()), expr);
}
return createNode<VarAsgnStmt>(nameToken.GetText(), expr, nameToken.GetLoc(), _curTok.GetLoc());
}
Stmt *
Parser::parseFunDeclStmt() {
Token firstTok = consume();
llvm::StringRef name = _curTok.GetText();
if (!expect(TkId)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedId)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
}
if (!expect(TkLParen)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "(" // expected
<< _curTok.GetText(); // got
}
std::vector<Argument> args;
while (!expect(TkRParen)) {
args.push_back(parseArgument());
if (!_curTok.Is(TkRParen)) {
if (!expect(TkComma)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "," // expected
<< _curTok.GetText(); // got
}
}
}
ASTType retType = ASTType(ASTTypeKind::Noth, "noth", false);
if (expect(TkColon)) {
retType = consumeType();
}
if (!expect(TkLBrace)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "{" // expected
<< _curTok.GetText(); // got
}
std::vector<Stmt *> block;
while (!expect(TkRBrace)) {
block.push_back(ParseStmt());
}
return createNode<FunDeclStmt>(name, retType, args, block, firstTok.GetLoc(), _curTok.GetLoc());
}
Stmt *
Parser::parseFunCallStmt() {
Token nameToken = consume();
consume();
std::vector<Expr *> args;
while (!expect(TkRParen)) {
args.push_back(parseExpr(PrecLowest));
if (!_curTok.Is(TkRParen)) {
if (!expect(TkComma)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "," // expected
<< _curTok.GetText(); // got
}
}
}
if (!expect(TkSemi)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ";" // expected
<< _curTok.GetText(); // got
}
return createNode<FunCallStmt>(nameToken.GetText(), args, nameToken.GetLoc(), _curTok.GetLoc());
}
Stmt *
Parser::parseRetStmt() {
Token firstTok = consume();
Expr *expr = nullptr;
if (!_curTok.Is(TkSemi)) {
expr = parseExpr(PrecLowest);
}
if (!expect(TkSemi)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ";" // expected
<< _curTok.GetText(); // got
}
return createNode<RetStmt>(expr, firstTok.GetLoc(), _curTok.GetLoc());
}
Argument
Parser::parseArgument() {
llvm::StringRef name = _curTok.GetText();
if (!expect(TkId)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedId)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
}
if (!expect(TkColon)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ":" // expected
<< _curTok.GetText(); // got
}
ASTType type = consumeType();
return Argument(name, type);
}
Expr *
Parser::parsePrefixExpr() {
switch (_curTok.GetKind()) {
case TkId: {
Token nameToken = consume();
if (_curTok.GetKind() == TkLParen) {
consume();
std::vector<Expr *> args;
while (!expect(TkRParen)) {
args.push_back(parseExpr(PrecLowest));
if (!_curTok.Is(TkRParen)) {
if (!expect(TkComma)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "," // expected
<< _curTok.GetText(); // got
}
}
}
return createNode<FunCallExpr>(nameToken.GetText(), args, nameToken.GetLoc(), _curTok.GetLoc());
}
else {
return createNode<VarExpr>(nameToken.GetText(), nameToken.GetLoc(), _curTok.GetLoc());
}
}
#define LIT(kind, type_val, field, val) \
createNode<LiteralExpr>(ASTVal(ASTType(ASTTypeKind::kind, type_val, true), \
ASTValData { .field = (val) }), consume().GetLoc(), _curTok.GetLoc())
case TkBoolLit:
return LIT(Bool, "bool", boolVal, _curTok.GetText() == "true");
case TkCharLit:
return LIT(Char, "char", charVal, _curTok.GetText()[0]);
case TkI16Lit:
return LIT(I16, "i16", i16Val, static_cast<short>(std::stoi(_curTok.GetText().data())));
case TkI32Lit:
return LIT(I32, "i32", i32Val, std::stoi(_curTok.GetText().data()));
case TkI64Lit:
return LIT(I64, "i64", i64Val, std::stol(_curTok.GetText().data()));
case TkF32Lit:
return LIT(F32, "f32", f32Val, std::stof(_curTok.GetText().data()));
case TkF64Lit:
return LIT(F64, "f64", f64Val, std::stod(_curTok.GetText().data()));
#undef LIT
case TkMinus:
case TkBang: {
Token op = consume();
return createNode<UnaryExpr>(parseExpr(PrecLowest), op, op.GetLoc(), _curTok.GetLoc());
}
case TkLParen: {
Token lparen = consume();
Expr *expr = parseExpr(PrecLowest);
if (!expect(TkRParen)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ")" // expected
<< _curTok.GetText(); // got
}
expr->SetStartLoc(lparen.GetLoc());
expr->SetEndLoc(_curTok.GetLoc());
return expr;
}
default:
_diag.Report(_curTok.GetLoc(), ErrExpectedExpr)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
consume();
return nullptr;
}
}
Expr *
Parser::parseExpr(int minPrec) {
Expr *lhs = parsePrefixExpr();
if (!lhs) {
return nullptr;
}
while (minPrec < GetTokPrecedence(_curTok.GetKind())) {
Token op = consume();
int prec = GetTokPrecedence(op.GetKind());
Expr *rhs = parseExpr(prec);
lhs = createNode<BinaryExpr>(lhs, rhs, op, lhs->GetStartLoc(), _curTok.GetLoc());
}
return lhs;
}
Token
Parser::consume() {
Token tok = _curTok;
_curTok = _nextTok;
_nextTok = _lex.NextToken();
return tok;
}
ASTType
Parser::consumeType() {
bool isConst = expect(TkConst);
Token type = consume();
switch (type.GetKind()) {
#define TYPE(kind, type_val) ASTType(ASTTypeKind::kind, type_val, isConst)
case TkBool:
return TYPE(Bool, "bool");
case TkChar:
return TYPE(Char, "char");
case TkI16:
return TYPE(I16, "i16");
case TkI32:
return TYPE(I32, "i32");
case TkI64:
return TYPE(I64, "i64");
case TkF32:
return TYPE(F32, "f32");
case TkF64:
return TYPE(F64, "f64");
default:
_diag.Report(type.GetLoc(), ErrExpectedType)
<< getRangeFromTok(type)
<< type.GetText();
return TYPE(I32, "i32");
#undef TYPE
}
}
Expr *
Parser::createCompoundAssignmentOp(Token op, Expr *base, Expr *expr) {
switch (op.GetKind()) {
#define OP(kind, val) createNode<BinaryExpr>(base, expr, Token(kind, val, op.GetLoc()), expr->GetStartLoc(), expr->GetEndLoc())
case TkPlusEq:
return OP(TkPlus, "+");
case TkMinusEq:
return OP(TkMinus, "-");
case TkStarEq:
return OP(TkStar, "*");
case TkSlashEq:
return OP(TkSlash, "/");
case TkPercentEq:
return OP(TkPercent, "%");
default:
return nullptr;
#undef OP
}
}
bool
Parser::expect(TokenKind kind) {
if (_curTok.Is(kind)) {
consume();
return true;
}
return false;
}
bool
Parser::isAssignmentOp(TokenKind kind) {
return kind >= TkPlusEq && kind <= TkPercentEq || kind == TkEq;
}
llvm::SMRange
Parser::getRangeFromTok(Token tok) const {
return llvm::SMRange(tok.GetLoc(), llvm::SMLoc::getFromPointer(tok.GetLoc().getPointer() + tok.GetText().size()));
}И начнем мы с consume. Этот метод пропускает текущий токен (но в конце возвращает его), полю _curTok присваивается значение из _nextTok, просит лексер сгенерировать новый токен и присваивает его полю _nextTok. Просто? Просто. Метод expect проверяет, является ли тип текущего токена тем, который мы передали в метод. consumeType пропускает тип и возвращает его, либо же, если текущий токен не является типом, то просим создать ошибку в диагностике и возвращаем тип по умолчанию. Не буду дальше заострять внимание на этих мелких кирпичиках, вы и сами сможете понять их смысл. Нам сейчас нужно разобрать то, как мы парсим выражения, ведь опять же выражения - самое важное, что должен уметь делать парсер.
Здесь испльзуется технология Pratt Parsing, то есть парсинг исходя из приоритета. Мы прекрасно понимаем, что то же умножение идет раньше, чем сложение. Теперь надо попробовать научить парсер понимать такое с помощью специального метода определения приоритета токена:
enum Precedence {
PrecLowest,
PrecLogical,
PrecComparation,
PrecEquality,
PrecBiwiseAnd,
PrecBiwiseXor,
PrecBiwiseOr,
PrecSum,
PrecProduct,
PrecPrefix,
PrecCall
};
int
GetTokPrecedence(TokenKind kind) {
switch (kind) {
case TkLogAnd:
case TkLogOr:
return PrecLogical;
case TkGt:
case TkGtEq:
case TkLt:
case TkLtEq:
return PrecComparation;
case TkEqEq:
case TkNotEq:
return PrecEquality;
case TkAnd:
return PrecBiwiseAnd;
case TkCarret:
return PrecBiwiseXor;
case TkOr:
return PrecBiwiseOr;
case TkPlus:
case TkMinus:
return PrecSum;
case TkStar:
case TkSlash:
case TkPercent:
return PrecProduct;
case TkLParen:
return PrecCall;
default:
return PrecLowest;
}
}Порядок расположения элементов в Precedence очень важен! Ведь именно значеня элементов перечисления и являются приоритетом операции.
Рассмотрим поближе парсинг выражений:
Expr *
Parser::parsePrefixExpr() {
switch (_curTok.GetKind()) {
case TkId: {
Token nameToken = consume();
if (_curTok.GetKind() == TkLParen) {
consume();
std::vector<Expr *> args;
while (!expect(TkRParen)) {
args.push_back(parseExpr(PrecLowest));
if (!_curTok.Is(TkRParen)) {
if (!expect(TkComma)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< "," // expected
<< _curTok.GetText(); // got
}
}
}
return createNode<FunCallExpr>(nameToken.GetText(), args, nameToken.GetLoc(), _curTok.GetLoc());
}
else {
return createNode<VarExpr>(nameToken.GetText(), nameToken.GetLoc(), _curTok.GetLoc());
}
}
#define LIT(kind, type_val, field, val) \
createNode<LiteralExpr>(ASTVal(ASTType(ASTTypeKind::kind, type_val, true), \
ASTValData { .field = (val) }), consume().GetLoc(), _curTok.GetLoc())
case TkBoolLit:
return LIT(Bool, "bool", boolVal, _curTok.GetText() == "true");
case TkCharLit:
return LIT(Char, "char", charVal, _curTok.GetText()[0]);
case TkI16Lit:
return LIT(I16, "i16", i16Val, static_cast<short>(std::stoi(_curTok.GetText().data())));
case TkI32Lit:
return LIT(I32, "i32", i32Val, std::stoi(_curTok.GetText().data()));
case TkI64Lit:
return LIT(I64, "i64", i64Val, std::stol(_curTok.GetText().data()));
case TkF32Lit:
return LIT(F32, "f32", f32Val, std::stof(_curTok.GetText().data()));
case TkF64Lit:
return LIT(F64, "f64", f64Val, std::stod(_curTok.GetText().data()));
#undef LIT
case TkMinus:
case TkBang: {
Token op = consume();
return createNode<UnaryExpr>(parseExpr(PrecLowest), op, op.GetLoc(), _curTok.GetLoc());
}
case TkLParen: {
Token lparen = consume();
Expr *expr = parseExpr(PrecLowest);
if (!expect(TkRParen)) {
_diag.Report(_curTok.GetLoc(), ErrExpectedToken)
<< getRangeFromTok(_curTok)
<< ")" // expected
<< _curTok.GetText(); // got
}
expr->SetStartLoc(lparen.GetLoc());
expr->SetEndLoc(_curTok.GetLoc());
return expr;
}
default:
_diag.Report(_curTok.GetLoc(), ErrExpectedExpr)
<< getRangeFromTok(_curTok)
<< _curTok.GetText();
consume();
return nullptr;
}
}
Expr *
Parser::parseExpr(int minPrec) {
Expr *lhs = parsePrefixExpr();
if (!lhs) {
return nullptr;
}
while (minPrec < GetTokPrecedence(_curTok.GetKind())) {
Token op = consume();
int prec = GetTokPrecedence(op.GetKind());
Expr *rhs = parseExpr(prec);
lhs = createNode<BinaryExpr>(lhs, rhs, op, lhs->GetStartLoc(), _curTok.GetLoc());
}
return lhs;
}Всегда всё начинается с parsePrefixExpr, ведь унарные операции/литералы/вызовы функций важнее, чем другие операторы. Если parsePrefixExpr ничего нам не дал, то и выражения никакого нет - выходим (строка 75). Однако если всё таки что-то есть, то парсим всё, что можем, только в том случае, если приоритет позволяет (выше минимально возможного). Парсинг инструкций рассматривать нет смысла, ведь он сводится к тому, чтобы просто проверять текущий токен на соответствие и выкидывать ошибки, если токен не ожидался.
Семантика
Мы подобрались к пожалуй самой интересной и важной части компилятора. Парсер умеет обрабатывать что-то в роде:
var a: i32 = 10;Но ведь нам никто не запрещает ошибочно (или умышленно) написать:
var a: i32 = "hello error!";А нам надо, чтобы кто-то запрещал. Нам нужен свод правил и законов, с помощью которых мы воцарим порядок в коде. Этим занимается семантический анализатор - проверяет логичность того, что написал пользователь. Парсер проверял лишь поверхностно - сопостовлял токены и выражения (которые могут быть разных типов), но нужно ещё и проверить их на корректность. Семантика может просто проверять типы выражений, но этого слишком мало в современных компиляторах, поэтому нам нужно дополнительно ещё и просчитывать значения выражений. Но тут есть оговорка, ведь если выражение нельзя просчитать на этапе компиляции, то и значения мы не узнаем. Примером таких выражений будут I/O операции (то есть ввод-вывод). Мы никогда не знаем заранее что пользователь может ввести, максимум что мы знаем, так это тип функции, которая предоставляет I/O вызовы. Таким выражениям мы не сможем выдать какое-то значение внутри компилятора, но можем использовать std::optional. Это класс, который хранит значение какого-либо типа. Если std::optional имеет значение std::nullopt, то к нему нельзя обратится (это как нулевой указатель, только безопаснее). Мы будем хранить вычисленные выражения как std::nullopt, если их значение нельзя просчитать на этапе компиляции. Чтобы хранить значения выражений будем использовать уже созданный нами ASTVal. Но перед началом нам нужно кое как подготовится - создать виситор.
Виситор
Виситор позволит нам удобно проходится по AST и выполнять какую-либо логику (например, проверять AST в семантике). Вот примерный каркас:
template<typename Derived, typename RetType = void>
class ASTVisitor {
public:
RetType
visit(Node *node) {
switch (node->GetKind()) {
case NkVarDeclStmt:
return static_cast<Derived*>(this)->visitVarDeclStmt(static_cast<VarDeclStmt *>(node));
case NkVarAsgnStmt:
return static_cast<Derived*>(this)->visitVarAsgnStmt(static_cast<VarAsgnStmt *>(node));
case NkFunDeclStmt:
return static_cast<Derived*>(this)->visitFunDeclStmt(static_cast<FunDeclStmt *>(node));
case NkFunCallStmt:
return static_cast<Derived*>(this)->visitFunCallStmt(static_cast<FunCallStmt *>(node));
case NkRetStmt:
return static_cast<Derived*>(this)->visitRetStmt(static_cast<RetStmt *>(node));
case NkBinaryExpr:
return static_cast<Derived*>(this)->visitBinaryExpr(static_cast<BinaryExpr *>(node));
case NkUnaryExpr:
return static_cast<Derived*>(this)->visitUnaryExpr(static_cast<UnaryExpr *>(node));
case NkVarExpr:
return static_cast<Derived*>(this)->visitVarExpr(static_cast<VarExpr *>(node));
case NkLiteralExpr:
return static_cast<Derived*>(this)->visitLiteralExpr(static_cast<LiteralExpr *>(node));
case NkFunCallExpr:
return static_cast<Derived*>(this)->visitFunCallExpr(static_cast<FunCallExpr *>(node));
default: {}
}
}
};От него будут публично наследоваться все классы, которые должны будут проходить по AST (например, та же семантика или кодогенератор). Смысл его работы в статическом полиморфизме, о котором я говорил ранее с classof в AST узлах. Дженерик Derived это класс, который наследуется от ASTVisitor. Дженерик RetType это тип возвращаемого значения функций виситора (мы должны будем подставлять ожидаемый тип для выражений в этот дженерик).
Семантика (ещё раз)
class SemanticAnalyzer : public ASTVisitor<SemanticAnalyzer, std::optional<ASTVal>> {
DiagnosticEngine &_diag;
struct Variable {
const llvm::StringRef Name;
const ASTType Type;
std::optional<ASTVal> Val;
const bool IsConst;
};
std::stack<std::unordered_map<std::string, Variable>> _vars;
struct Function {
const llvm::StringRef Name;
const ASTType RetType;
std::vector<Argument> Args;
std::vector<Stmt *> Body;
};
std::unordered_map<std::string, Function> functions;
std::stack<ASTType> funRetsTypes;
public:
explicit SemanticAnalyzer(DiagnosticEngine &diag) : _diag(diag) {
_vars.push({});
}
std::optional<ASTVal>
visitVarDeclStmt(VarDeclStmt *vds);
std::optional<ASTVal>
visitVarAsgnStmt(VarAsgnStmt *vas);
std::optional<ASTVal>
visitFunDeclStmt(FunDeclStmt *fds);
std::optional<ASTVal>
visitFunCallStmt(FunCallStmt *fcs);
std::optional<ASTVal>
visitRetStmt(RetStmt *rs);
std::optional<ASTVal>
visitBinaryExpr(BinaryExpr *be);
std::optional<ASTVal>
visitUnaryExpr(UnaryExpr *ue);
std::optional<ASTVal>
visitVarExpr(VarExpr *ve);
std::optional<ASTVal>
visitLiteralExpr(LiteralExpr *le);
std::optional<ASTVal>
visitFunCallExpr(FunCallExpr *fce);
llvm::SMRange
getRange(llvm::SMLoc start, int len) const;
void
checkBinaryExpr(BinaryExpr *be);
bool
variableExists(std::string name) const;
bool
canImplicitlyCast(ASTVal src, ASTType expectType) const;
ASTVal
implicitlyCast(ASTVal src, ASTType expectType, llvm::SMLoc startLoc, llvm::SMLoc endLoc) const;
};Эта семантика расчитана на переменные и функции (всё, что в языке поддерживается на данный момент). Для удобного хранения данных о переменной создана структура Variable с метаданными о переменной. Переменные образуют области видимости, поэтому для этого нам нужно сделать стек переменных. Помимо этого в одной области видимости имена переменных уникальны, значит в качестве значения стека будет мапа с переменными (std::unordered_map потому что нам не нужно их сортировать по именам, то есть +1 мини оптимизация). Также для функций создана структура Function и мапа functions, чтобы хранить и работать с этими функциями. Помимо всего прочего сдесь выделяются методы canImplicitlyCast и implicitlyCast. Это методы для неявных преобразований типов. Мы же знаем, что по хорошему int -> float можно, а наоборот нельзя. Поэтому эти методы признаны обрабатывать неявные преобразования и говорить, можно ли их совершить (canImplicitlyCast) или вызвать ошибку, если мы совершаем преобразование, которое сделать нельзя (implicitlyCast).
static std::unordered_map<ASTTypeKind, std::vector<ASTTypeKind>> implicitlyCastAllowed {
{ ASTTypeKind::Char, { ASTTypeKind::I16, ASTTypeKind::I32, ASTTypeKind::I64, ASTTypeKind::F32, ASTTypeKind::F64 } },
{ ASTTypeKind::I16, { ASTTypeKind::I32, ASTTypeKind::I64, ASTTypeKind::F32, ASTTypeKind::F64 } },
{ ASTTypeKind::I32, { ASTTypeKind::I64, ASTTypeKind::F32, ASTTypeKind::F64 } },
{ ASTTypeKind::I64, { ASTTypeKind::F32, ASTTypeKind::F64 } },
{ ASTTypeKind::F32, { ASTTypeKind::F64 } },
};
std::optional<ASTVal>
SemanticAnalyzer::visitVarDeclStmt(VarDeclStmt *vds) {
if (_vars.top().find(vds->GetName().str()) != _vars.top().end()) {
_diag.Report(llvm::SMLoc::getFromPointer(vds->GetName().data()), ErrRedefinitionVar)
<< getRange(llvm::SMLoc::getFromPointer(vds->GetName().data()), vds->GetName().size())
<< vds->GetName();
}
else {
std::optional<ASTVal> val = vds->GetExpr() != nullptr ? visit(vds->GetExpr()) : ASTVal::GetDefaultByType(vds->GetType());
Variable var { .Name = vds->GetName(), .Type = vds->GetType(), .Val = val, .IsConst = vds->IsConst() };
if (vds->GetExpr()) {
implicitlyCast(var.Val.value(), var.Type, vds->GetExpr()->GetStartLoc(), vds->GetExpr()->GetEndLoc());
}
_vars.top().emplace(vds->GetName(), var);
}
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitVarAsgnStmt(VarAsgnStmt *vas) {
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(vas->GetName().str()); var != varsCopy.top().end()) {
if (var->second.IsConst) {
_diag.Report(vas->GetStartLoc(), ErrAssignmentConst)
<< llvm::SMRange(vas->GetStartLoc(), vas->GetEndLoc());
return std::nullopt;
}
ASTVal val = visit(vas->GetExpr()).value_or(ASTVal::GetDefaultByType(ASTType::GetNothType()));
val = implicitlyCast(val, var->second.Type, vas->GetExpr()->GetStartLoc(), vas->GetExpr()->GetEndLoc());
var->second.Val = val;
return std::nullopt;
}
varsCopy.pop();
}
_diag.Report(vas->GetStartLoc(), ErrUndeclaredVariable)
<< getRange(vas->GetStartLoc(), vas->GetName().size())
<< vas->GetName();
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitFunDeclStmt(FunDeclStmt *fds) {
if (functions.find(fds->GetName().str()) != functions.end()) {
_diag.Report(llvm::SMLoc::getFromPointer(fds->GetName().data()), ErrRedefinitionFun)
<< getRange(llvm::SMLoc::getFromPointer(fds->GetName().data()), fds->GetName().size())
<< fds->GetName();
}
else {
_vars.push({});
for (auto arg : fds->GetArgs()) {
_vars.top().emplace(arg.GetName(), Variable { .Name = arg.GetName(), .Type = arg.GetType(), .Val = ASTVal::GetDefaultByType(arg.GetType()),
.IsConst = arg.GetType().IsConst() });
}
Function fun { .Name = fds->GetName(), .RetType = fds->GetRetType(), .Args = fds->GetArgs(), .Body = fds->GetBody() };
functions.emplace(fds->GetName().str(), fun);
funRetsTypes.push(fds->GetRetType());
bool hasRet;
for (auto stmt : fds->GetBody()) {
if (stmt->GetKind() == NkRetStmt) {
hasRet = true;
}
visit(stmt);
}
funRetsTypes.pop();
_vars.pop();
if (!hasRet && fds->GetRetType().GetTypeKind() != ASTTypeKind::Noth) {
_diag.Report(fds->GetStartLoc(), ErrNotAllPathsReturnsValue)
<< llvm::SMRange(fds->GetStartLoc(), fds->GetEndLoc());
}
}
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitFunCallStmt(FunCallStmt *fcs) {
FunCallExpr *expr = new FunCallExpr(fcs->GetName(), fcs->GetArgs(), fcs->GetStartLoc(), fcs->GetEndLoc());
visitFunCallExpr(expr);
delete expr;
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitRetStmt(RetStmt *rs) {
ASTVal val = ASTVal::GetDefaultByType(ASTType::GetNothType());
if (rs->GetExpr()) {
val = visit(rs->GetExpr()).value_or(ASTVal::GetDefaultByType(ASTType::GetNothType()));
}
implicitlyCast(val, funRetsTypes.top(), rs->GetStartLoc(), rs->GetEndLoc());
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitBinaryExpr(BinaryExpr *be) {
checkBinaryExpr(be);
std::optional<ASTVal> lhs = visit(be->GetLHS());
if (lhs == std::nullopt) {
return lhs;
}
std::optional<ASTVal> rhs = visit(be->GetRHS());
if (rhs == std::nullopt) {
return rhs;
}
double lhsVal = lhs->AsDouble();
double rhsVal = rhs->AsDouble();
double res;
switch (be->GetOp().GetKind()) {
#define EVAL(op) lhsVal op rhsVal
case TkPlus:
res = EVAL(+);
break;
case TkMinus:
res = EVAL(+);
break;
case TkStar:
res = EVAL(*);
break;
case TkSlash:
res = EVAL(/);
break;
case TkPercent:
res = std::fmod(lhsVal, rhsVal);
break;
case TkLogAnd:
res = EVAL(&&);
break;
case TkLogOr:
res = EVAL(||);
break;
case TkAnd:
res = static_cast<long>(lhsVal) & static_cast<long>(rhsVal);
break;
case TkOr:
res = static_cast<long>(lhsVal) | static_cast<long>(rhsVal);
break;
case TkGt:
res = EVAL(>);
break;
case TkGtEq:
res = EVAL(>=);
break;
case TkLt:
res = EVAL(<);
break;
case TkLtEq:
res = EVAL(<=);
break;
case TkEqEq:
res = EVAL(==);
break;
case TkNotEq:
res = EVAL(!=);
break;
default: {}
#undef EVAL
}
return ASTVal::GetVal(res, ASTType::GetCommon(lhs->GetType(), rhs->GetType()));
}
std::optional<ASTVal>
SemanticAnalyzer::visitUnaryExpr(UnaryExpr *ue) {
std::optional<ASTVal> rhs = visit(ue->GetRHS());
if (rhs == std::nullopt) {
return rhs;
}
double val = rhs->AsDouble();
switch (ue->GetOp().GetKind()) {
case TkMinus:
if (rhs->GetType().GetTypeKind() < ASTTypeKind::Char || rhs->GetType().GetTypeKind() > ASTTypeKind::F64) {
_diag.Report(ue->GetRHS()->GetStartLoc(), ErrTypeMismatchNotNum)
<< llvm::SMRange(ue->GetRHS()->GetStartLoc(), ue->GetRHS()->GetEndLoc())
<< rhs->GetType().ToString();
}
val *= -1;
break;
case TkBang:
if (rhs->GetType().GetTypeKind() != ASTTypeKind::Bool) {
_diag.Report(ue->GetRHS()->GetStartLoc(), ErrTypeMismatchNotBool)
<< llvm::SMRange(ue->GetRHS()->GetStartLoc(), ue->GetRHS()->GetEndLoc())
<< rhs->GetType().ToString();
}
val = !val;
break;
default: {}
}
return ASTVal::GetVal(val, rhs->GetType());
}
std::optional<ASTVal>
SemanticAnalyzer::visitVarExpr(VarExpr *ve) {
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(ve->GetName().str()); var != varsCopy.top().end()) {
return var->second.Val;
}
varsCopy.pop();
}
_diag.Report(ve->GetStartLoc(), ErrUndeclaredVariable)
<< getRange(ve->GetStartLoc(), ve->GetName().size())
<< ve->GetName();
return std::nullopt;
}
std::optional<ASTVal>
SemanticAnalyzer::visitLiteralExpr(LiteralExpr *le) {
return le->GetVal();
}
std::optional<ASTVal>
SemanticAnalyzer::visitFunCallExpr(FunCallExpr *fce) {
if (functions.find(fce->GetName().str()) != functions.end()) {
_vars.push({});
Function fun = functions.at(fce->GetName().str());
if (fun.Args.size() != fce->GetArgs().size()) {
_diag.Report(fce->GetStartLoc(), ErrFewArgs)
<< llvm::SMRange(fce->GetStartLoc(), fce->GetEndLoc())
<< fce->GetName().str()
<< fun.Args.size()
<< fce->GetArgs().size();
return std::nullopt;
}
for (int i = 0; i < fun.Args.size(); ++i) {
std::optional<ASTVal> val = visit(fce->GetArgs()[i]);
implicitlyCast(val.value_or(ASTVal::GetDefaultByType(ASTType::GetNothType())), fun.Args[i].GetType(),
fce->GetArgs()[i]->GetStartLoc(), fce->GetArgs()[i]->GetEndLoc());
_vars.top().emplace(fun.Args[i].GetName(), Variable { .Name = fun.Args[i].GetName(), .Type = fun.Args[i].GetType(),
.Val = val, .IsConst = fun.Args[i].GetType().IsConst() });
}
for (auto stmt : fun.Body) {
if (stmt->GetKind() == NkRetStmt) {
Expr *expr = llvm::dyn_cast<RetStmt>(stmt)->GetExpr();
std::optional<ASTVal> val = expr ? visit(expr) : ASTVal::GetDefaultByType(ASTType::GetNothType());
implicitlyCast(val.value_or(ASTVal::GetDefaultByType(ASTType::GetNothType())), fun.RetType, fce->GetStartLoc(),
fce->GetEndLoc());
_vars.pop();
return val;
}
else {
visit(stmt);
}
}
_vars.pop();
_diag.Report(fce->GetStartLoc(), ErrFuntionCannotReturnValue);
return std::nullopt;
}
_diag.Report(fce->GetStartLoc(), ErrUndeclaredFuntion)
<< getRange(fce->GetStartLoc(), fce->GetName().size())
<< fce->GetName();
return std::nullopt;
}
llvm::SMRange
SemanticAnalyzer::getRange(llvm::SMLoc start, int len) const {
return llvm::SMRange(start, llvm::SMLoc::getFromPointer(start.getPointer() + len));
}
void
SemanticAnalyzer::checkBinaryExpr(BinaryExpr *be) {
ASTVal lhs = visit(be->GetLHS()).value();
ASTVal rhs = visit(be->GetRHS()).value();
switch (be->GetOp().GetKind()) {
case TkPlus:
case TkMinus:
case TkStar:
case TkSlash:
case TkPercent:
if (!(lhs.GetType().GetTypeKind() >= ASTTypeKind::Char && lhs.GetType().GetTypeKind() <= ASTTypeKind::F64 &&
rhs.GetType().GetTypeKind() >= ASTTypeKind::Char && rhs.GetType().GetTypeKind() <= ASTTypeKind::F64)) {
_diag.Report(be->GetStartLoc(), ErrUnsupportedTypeForOperator)
<< llvm::SMRange(be->GetStartLoc(), be->GetEndLoc())
<< be->GetOp().GetText().str()
<< lhs.GetType().ToString()
<< rhs.GetType().ToString();
}
break;
case TkLogAnd:
case TkLogOr:
if (lhs.GetType().GetTypeKind() != ASTTypeKind::Bool ||
rhs.GetType().GetTypeKind() != ASTTypeKind::Bool) {
_diag.Report(be->GetStartLoc(), ErrUnsupportedTypeForOperator)
<< llvm::SMRange(be->GetStartLoc(), be->GetEndLoc())
<< be->GetOp().GetText().str()
<< lhs.GetType().ToString()
<< rhs.GetType().ToString();
}
break;
case TkAnd:
case TkOr:
if (!(lhs.GetType().GetTypeKind() >= ASTTypeKind::Char && lhs.GetType().GetTypeKind() <= ASTTypeKind::I64 &&
rhs.GetType().GetTypeKind() >= ASTTypeKind::Char && rhs.GetType().GetTypeKind() <= ASTTypeKind::I64)) {
_diag.Report(be->GetStartLoc(), ErrUnsupportedTypeForOperator)
<< llvm::SMRange(be->GetStartLoc(), be->GetEndLoc())
<< be->GetOp().GetText().str()
<< lhs.GetType().ToString()
<< rhs.GetType().ToString();
}
break;
case TkGt:
case TkGtEq:
case TkLt:
case TkLtEq:
case TkEqEq:
case TkNotEq:
if (!ASTType::HasCommon(lhs.GetType(), rhs.GetType())) {
_diag.Report(be->GetStartLoc(), ErrUnsupportedTypeForOperator)
<< llvm::SMRange(be->GetStartLoc(), be->GetEndLoc())
<< be->GetOp().GetText().str()
<< lhs.GetType().ToString()
<< rhs.GetType().ToString();
}
break;
default: {}
}
}
bool
SemanticAnalyzer::variableExists(std::string name) const {
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(name); var != varsCopy.top().end()) {
return true;
}
varsCopy.pop();
}
return false;
}
bool
SemanticAnalyzer::canImplicitlyCast(ASTVal src, ASTType expectType) const {
if (src.GetType() == expectType) {
return true;
}
if (auto it = implicitlyCastAllowed.find(src.GetType().GetTypeKind()); it != implicitlyCastAllowed.end()) {
return std::find(it->second.begin(), it->second.end(), expectType.GetTypeKind()) != it->second.end();
}
return false;
}
ASTVal
SemanticAnalyzer::implicitlyCast(ASTVal src, ASTType expectType, llvm::SMLoc startLoc, llvm::SMLoc endLoc) const {
if (src.GetType() == expectType) {
return src;
}
if (auto it = implicitlyCastAllowed.find(src.GetType().GetTypeKind()); it != implicitlyCastAllowed.end()) {
if (std::find(it->second.begin(), it->second.end(), expectType.GetTypeKind()) != it->second.end()) {
return src.Cast(expectType);
}
}
_diag.Report(startLoc, ErrCannotCast)
<< llvm::SMRange(startLoc, endLoc)
<< src.GetType().ToString()
<< expectType.ToString();
return ASTVal::GetDefaultByType(ASTType::GetNothType());
}implicitlyCastAllowed это таблица с разрешенными для неявного приведениями типами. Неявное приведение сработает только если: типы совпадают, тип переданного выражения можно привести к ожидаемому типу (исходя из implicitlyCastAllowed). В ином случае создаем ошибку и возвращаем пустое значение. В бинарных и унарных операции мы должны проверять типы значений и оператор, который взаимодействует со значениями. Например оператор ! не может взаимодействовать ни с чем, кроме значения типа bool и тд. При опеределении переменной или функции мы обязаны проверить, а существует ли переменная/функция в текущей области видимости, и если есть, то выкидываем ошибку о переопределении объекта. Правила можно придумать любые, но пока что будем довольствоваться такими (самыми нормальными). Чем больше фич в языке, тем сложнее его семантика. Семантика признана запрещать генерировать код на основе AST, если он может привести к ошибки компиляции (или иногда рантайм ошибке). И теперь мы плавно перебираемся в кодогенератор.
Кодогенератор
Он вообще не обрабатывает и не выкидывает ошибки, ведь всё до него сделали парсер или семантика. Кодогенератор просто "втупую" генерирует код для вашего AST. Код, который мы будем генерировать, будет считаться неоптимизированным, поскольку мы не будем знать о полном контексте программы, но оптимизациями может занятся подсистема LLVM уже после генерации нашего кода (об этом потом).
class CodeGen : public ASTVisitor<CodeGen, llvm::Value *> {
llvm::LLVMContext _context;
std::unique_ptr<llvm::Module> _module;
llvm::IRBuilder<> _builder;
std::stack<std::unordered_map<std::string, llvm::Value *>> _vars;
std::unordered_map<std::string, llvm::Function *> functions;
std::stack<llvm::Type *> funRetsTypes;
public:
explicit CodeGen(std::string fileName)
: _context(), _builder(_context),
_module(std::make_unique<llvm::Module>(fileName, _context)) {
_vars.push({});
}
std::unique_ptr<llvm::Module>
GetModule() {
return std::move(_module);
}
llvm::Value *
visitVarDeclStmt(VarDeclStmt *vds);
llvm::Value *
visitVarAsgnStmt(VarAsgnStmt *vas);
llvm::Value *
visitFunDeclStmt(FunDeclStmt *fds);
llvm::Value *
visitFunCallStmt(FunCallStmt *fcs);
llvm::Value *
visitRetStmt(RetStmt *rs);
llvm::Value *
visitBinaryExpr(BinaryExpr *be);
llvm::Value *
visitUnaryExpr(UnaryExpr *ue);
llvm::Value *
visitVarExpr(VarExpr *ve);
llvm::Value *
visitLiteralExpr(LiteralExpr *le);
llvm::Value *
visitFunCallExpr(FunCallExpr *fce);
llvm::Type *
getCommonType(llvm::Type *left, llvm::Type *right);
llvm::Value *
implicitlyCast(llvm::Value *src, llvm::Type *expectType);
llvm::SMRange
getRange(llvm::SMLoc start, int len) const;
llvm::Type *
typeKindToLLVM(ASTTypeKind kind);
};Кодген тоже проходится по AST, значит должен наследоваться от виситора. LLVMContext создает гарантии безопасности имен типов, то есть не будет двух типов с одинаковым именем. Контекст нужен также для создания модуля llvm::Module. Это минимальная единица трансляции в LLVM, то есть по сути это отдельная программа. Модуль хранит глобальные переменные и функции. llvm::IRBuilder это класс, который позволит нам создавать LLVM IR инструкций (например, инструкция для сложения или создания локальной переменной). llvm::Value* это класс, который представляет собой любое значение в среде LLVM (будь то константа или что-либо ещё). llvm::Type* это класс, который представляет собой любой тип в среде LLVM (будь то указатель, целое или дробное число и тд). Сразу стоит отметить - LLVM без разницы какое число - знаковое или нет. Если дать ему инструкцию для деления двух беззнаковых чисел, то он будет расценивать их как беззнаковые, и то же самое с инструкцией для знаковых чисел. Пока что беззнаковых чисел у нас нет, но когда будут, то придется усложнить логику.
llvm::Value *
CodeGen::visitVarDeclStmt(VarDeclStmt *vds) {
llvm::Value *initializer = nullptr;
if (vds->GetExpr()) {
initializer = visit(vds->GetExpr());
initializer = implicitlyCast(initializer, typeKindToLLVM(vds->GetType().GetTypeKind()));
}
else {
initializer = llvm::Constant::getNullValue(typeKindToLLVM(vds->GetType().GetTypeKind()));
}
llvm::Value *var;
if (_vars.size() == 1) {
var = new llvm::GlobalVariable(*_module, typeKindToLLVM(vds->GetType().GetTypeKind()), vds->IsConst(), llvm::GlobalValue::ExternalLinkage, llvm::cast<llvm::Constant>(initializer), vds->GetName());
}
else {
var = _builder.CreateAlloca(typeKindToLLVM(vds->GetType().GetTypeKind()), nullptr, vds->GetName());
_builder.CreateStore(initializer, var);
}
_vars.top().emplace(vds->GetName().str(), var);
return nullptr;
}
llvm::Value *
CodeGen::visitVarAsgnStmt(VarAsgnStmt *vas) {
llvm::Value *val = visit(vas->GetExpr());
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(vas->GetName().str()); var != varsCopy.top().end()) {
if (auto glob = llvm::dyn_cast<llvm::GlobalVariable>(var->second)) {
_builder.CreateStore(val, glob);
}
if (auto local = llvm::dyn_cast<llvm::AllocaInst>(var->second)) {
_builder.CreateStore(val, local);
}
}
varsCopy.pop();
}
return nullptr;
}
llvm::Value *
CodeGen::visitFunDeclStmt(FunDeclStmt *fds) {
std::vector<llvm::Type *> args(fds->GetArgs().size());
for (int i = 0; i < fds->GetArgs().size(); ++i) {
args[i] = typeKindToLLVM(fds->GetArgs()[i].GetType().GetTypeKind());
}
llvm::FunctionType *retType = llvm::FunctionType::get(typeKindToLLVM(fds->GetRetType().GetTypeKind()), args, false);
llvm::Function *fun = llvm::Function::Create(retType, llvm::GlobalValue::ExternalLinkage, fds->GetName(), *_module);
llvm::BasicBlock *entry = llvm::BasicBlock::Create(_context, "entry", fun);
_builder.SetInsertPoint(entry);
_vars.push({});
funRetsTypes.push(fun->getReturnType());
functions.emplace(fun->getName(), fun);
int index = 0;
for (auto &arg : fun->args()) {
arg.setName(fds->GetArgs()[index].GetName());
llvm::AllocaInst *alloca = _builder.CreateAlloca(arg.getType(), nullptr, arg.getName());
_builder.CreateStore(&arg, alloca);
_vars.top().emplace(arg.getName().str(), alloca);
++index;
}
for (auto &stmt : fds->GetBody()) {
visit(stmt);
}
if (fds->GetRetType().GetTypeKind() == ASTTypeKind::Noth) {
_builder.CreateRetVoid();
}
funRetsTypes.pop();
_vars.pop();
return nullptr;
}
llvm::Value *
CodeGen::visitFunCallStmt(FunCallStmt *fcs) {
FunCallExpr *expr = new FunCallExpr(fcs->GetName(), fcs->GetArgs(), fcs->GetStartLoc(), fcs->GetEndLoc());
visit(expr);
delete expr;
return nullptr;
}
llvm::Value *
CodeGen::visitRetStmt(RetStmt *rs) {
if (rs->GetExpr()) {
llvm::Value *val = visit(rs->GetExpr());
return _builder.CreateRet(implicitlyCast(val, funRetsTypes.top()));
}
return _builder.CreateRetVoid();
}
llvm::Value *
CodeGen::visitBinaryExpr(BinaryExpr *be) {
llvm::Value *lhs = visit(be->GetLHS());
llvm::Value *rhs = visit(be->GetRHS());
llvm::Type *lhsType = lhs->getType();
llvm::Type *rhsType = rhs->getType();
llvm::Type *commonType = getCommonType(lhsType, rhsType);
if (lhsType != commonType) {
lhs = implicitlyCast(lhs, commonType);
lhsType = lhs->getType();
}
else if (rhsType != commonType) {
rhs = implicitlyCast(rhs, commonType);
rhsType = rhs->getType();
}
switch (be->GetOp().GetKind()) {
case TkPlus:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFAdd(lhs, rhs);
}
return _builder.CreateAdd(lhs, rhs);
case TkMinus:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFSub(lhs, rhs);
}
return _builder.CreateSub(lhs, rhs);
case TkStar:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFMul(lhs, rhs);
}
return _builder.CreateMul(lhs, rhs);
case TkSlash:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFDiv(lhs, rhs);
}
return _builder.CreateSDiv(lhs, rhs);
case TkPercent:
if (commonType->isFloatingPointTy()) {
_builder.CreateFRem(lhs, rhs);
}
return _builder.CreateSRem(lhs, rhs);
case TkLogAnd:
return _builder.CreateLogicalAnd(lhs, rhs);
case TkLogOr:
return _builder.CreateLogicalOr(lhs, rhs);
case TkAnd:
return _builder.CreateAnd(lhs, rhs);
case TkOr:
return _builder.CreateOr(lhs, rhs);
case TkGt:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpOGT(lhs, rhs);
}
return _builder.CreateICmpSGT(lhs, rhs);
case TkGtEq:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpOGE(lhs, rhs);
}
return _builder.CreateICmpSGE(lhs, rhs);
case TkLt:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpOLT(lhs, rhs);
}
return _builder.CreateICmpSLT(lhs, rhs);
case TkLtEq:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpOLE(lhs, rhs);
}
return _builder.CreateICmpSLE(lhs, rhs);
case TkEqEq:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpOEQ(lhs, rhs);
}
return _builder.CreateICmpEQ(lhs, rhs);
case TkNotEq:
if (commonType->isFloatingPointTy()) {
return _builder.CreateFCmpONE(lhs, rhs);
}
return _builder.CreateICmpNE(lhs, rhs);
default: {}
}
return nullptr;
}
llvm::Value *
CodeGen::visitUnaryExpr(UnaryExpr *ue) {
llvm::Value *rhs = visit(ue->GetRHS());
switch (ue->GetOp().GetKind()) {
case TkMinus:
if (rhs->getType()->isFloatingPointTy()) {
return _builder.CreateFNeg(rhs);
}
return _builder.CreateNeg(rhs);
case TkBang:
return _builder.CreateNot(rhs);
default: {}
}
return nullptr;
}
llvm::Value *
CodeGen::visitVarExpr(VarExpr *ve) {
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(ve->GetName().str()); var != varsCopy.top().end()) {
if (auto glob = llvm::dyn_cast<llvm::GlobalVariable>(var->second)) {
if (_vars.size() == 1) {
return glob->getInitializer();
}
return _builder.CreateLoad(glob->getValueType(), glob, var->first + ".load");
}
if (auto local = llvm::dyn_cast<llvm::AllocaInst>(var->second)) {
return _builder.CreateLoad(local->getAllocatedType(), local, var->first + ".load");
}
return var->second;
}
varsCopy.pop();
}
return nullptr;
}
llvm::Value *
CodeGen::visitLiteralExpr(LiteralExpr *le) {
switch (le->GetVal().GetType().GetTypeKind()) {
#define CONST_INT(func, field) llvm::ConstantInt::get(llvm::Type::func(_context), le->GetVal().GetData().field)
#define CONST_FP(func, field) llvm::ConstantFP::get(llvm::Type::func(_context), le->GetVal().GetData().field)
case ASTTypeKind::Bool:
return CONST_INT(getInt1Ty, boolVal);
case ASTTypeKind::Char:
return CONST_INT(getInt8Ty, charVal);
case ASTTypeKind::I16:
return CONST_INT(getInt16Ty, i16Val);
case ASTTypeKind::I32:
return CONST_INT(getInt32Ty, i32Val);
case ASTTypeKind::I64:
return CONST_INT(getInt64Ty, i64Val);
case ASTTypeKind::F32:
return CONST_FP(getFloatTy, f32Val);
case ASTTypeKind::F64:
return CONST_FP(getDoubleTy, f64Val);
default: {}
#undef CONST_FP
#undef CONST_INT
}
return nullptr;
}
llvm::Value *
CodeGen::visitFunCallExpr(FunCallExpr *fce) {
std::vector<llvm::Value *> args(fce->GetArgs().size());
for (int i = 0; i < fce->GetArgs().size(); ++i) {
args[i] = visit(fce->GetArgs()[i]);
}
llvm::Function *fun = functions.at(fce->GetName().str());
return _builder.CreateCall(fun, args, fce->GetName() + ".call");
}
llvm::Type *
CodeGen::getCommonType(llvm::Type *left, llvm::Type *right) {
if (left == right) {
return left;
}
else if (left->isIntegerTy() || right->isIntegerTy()) {
if (left->isIntegerTy() && right->isIntegerTy()) {
unsigned leftWidth = left->getIntegerBitWidth();
unsigned rightWidth = right->getIntegerBitWidth();
return leftWidth > rightWidth ? left : right;
}
else if (left->isFloatingPointTy() || right->isFloatingPointTy()) {
return left->isFloatingPointTy() ? left : right;
}
}
else if (left->isFloatingPointTy() && right->isFloatingPointTy()) {
return left->isDoubleTy() && right->isFloatTy() ? left : right;
}
else if (left->isDoubleTy() || right->isDoubleTy()) {
return llvm::Type::getDoubleTy(_context);
}
return nullptr;
}
llvm::Value *
CodeGen::implicitlyCast(llvm::Value *src, llvm::Type *expectType) {
llvm::Type *destType = src->getType();
if (destType == expectType) {
return src;
}
else if (destType->isIntegerTy() && expectType->isIntegerTy()) {
unsigned long valWidth = destType->getIntegerBitWidth();
unsigned long expectedWidth = expectType->getIntegerBitWidth();
if (valWidth > expectedWidth) {
return _builder.CreateTrunc(src, expectType, "trunc.tmp");
}
else {
return _builder.CreateSExt(src, expectType, "sext.tmp");
}
}
else if (destType->isFloatingPointTy() && expectType->isFloatingPointTy()) {
if (destType->isFloatTy() && expectType->isDoubleTy()) {
return _builder.CreateFPExt(src, expectType, "fpext.tmp");
}
else {
return _builder.CreateFPTrunc(src, expectType, "fptrunc.tmp");
}
}
else if (destType->isIntegerTy() && expectType->isFloatingPointTy()) {
return _builder.CreateSIToFP(src, expectType, "sitofp.tmp");
}
return nullptr;
}
llvm::SMRange
CodeGen::getRange(llvm::SMLoc start, int len) const {
return llvm::SMRange(start, llvm::SMLoc::getFromPointer(start.getPointer() + len));
}
llvm::Type *
CodeGen::typeKindToLLVM(ASTTypeKind kind) {
switch (kind) {
#define TYPE(func) llvm::Type::func(_context);
case ASTTypeKind::Bool:
return TYPE(getInt1Ty);
case ASTTypeKind::Char:
return TYPE(getInt8Ty);
case ASTTypeKind::I16:
return TYPE(getInt16Ty);
case ASTTypeKind::I32:
return TYPE(getInt32Ty);
case ASTTypeKind::I64:
return TYPE(getInt64Ty);
case ASTTypeKind::F32:
return TYPE(getFloatTy);
case ASTTypeKind::F64:
return TYPE(getDoubleTy);
case ASTTypeKind::Noth:
return TYPE(getVoidTy);
#undef TYPE
}
}Для LLVM есть разница между локальной и глобальной переменными, но они всё равно так или иначе являются производными от llvm::Value*. Если область видимости - глобальная (размер стека переменных = 1), то создаем глобальную переменную (причем обязательно передать инициализатор как константное значение с помощью llvm::dyn_cast). Однако в противном случае мы создаем локальную переменную (llvm::AllocaInst) и загружаем в неё значение инициализатора с помощью _builder. Рассказать вам всё про LLVM я не смогу, по крайней мере в одной статье (если будет желание от вас, то сделаю ещё одну статью про этот же язык, но с новыми фичами и мы продолжим изучать LLVM). Статью уже пора заканчивать, но осталось ещё самое главное - main.cpp.
Самое главное
int
main(int argc, char **argv) {
if (argc < 2) {
llvm::errs() << llvm::errs().RED << "Usage: onyxc <input file>\n" << llvm::errs().RESET;
return 1;
}
llvm::cl::HideUnrelatedOptions(onyx::OnyxCat);
llvm::cl::ParseCommandLineOptions(argc, argv, "Onyx Compiler\n");
std::string fileName = onyx::InputFilename;
llvm::SourceMgr srcMgr;
auto bufferOrErr = llvm::MemoryBuffer::getFile(fileName);
if (std::error_code ec = bufferOrErr.getError()) {
llvm::errs() << llvm::errs().RED << "Could not open file: " << llvm::errs().RESET << ec.message() << '\n';
return 1;
}
srcMgr.AddNewSourceBuffer(std::move(*bufferOrErr), llvm::SMLoc());
onyx::DiagnosticEngine diag(srcMgr);
onyx::Lexer lex(srcMgr, diag);
onyx::Parser parser(lex, diag);
std::vector<onyx::Stmt *> ast;
while (1) {
onyx::Stmt *stmt = parser.ParseStmt();
if (!stmt) {
break;
}
ast.push_back(stmt);
}
if (diag.HasErrors()) {
return 1;
}
diag.ResetErrors();
onyx::SemanticAnalyzer sema(diag);
for (auto &stmt : ast) {
sema.visit(stmt);
}
if (diag.HasErrors()) {
return 1;
}
diag.ResetErrors();
onyx::CodeGen codegen(fileName);
for (auto &stmt : ast) {
codegen.visit(stmt);
}
if (diag.HasErrors()) {
return 1;
}
std::unique_ptr<llvm::Module> mod = codegen.GetModule();
onyx::InitializeLLVMTargets();
std::string tripleStr = llvm::sys::getDefaultTargetTriple();
llvm::Triple triple(tripleStr);
llvm::StringRef stem = llvm::sys::path::stem(fileName);
std::string outputName;
if (!onyx::OutputFilename.empty()) {
outputName = onyx::OutputFilename;
}
else {
switch (onyx::EmitAction) {
case onyx::EmitAST:
outputName = "";
break;
case onyx::EmitLLVM:
outputName = (stem + ".ll").str();
break;
case onyx::EmitObj:
outputName = (stem + ".o").str();
break;
case onyx::EmitBinary:
outputName = stem.str();
if (triple.isOSWindows()) {
outputName += ".exe";
}
break;
}
}
if (onyx::EmitAction == onyx::EmitAST) {
onyx::ASTPrinter printer;
for (auto stmt : ast) {
printer.visit(stmt);
llvm::outs() << '\n';
}
return 0;
}
onyx::Optimizer::Level optLvl;
switch (onyx::OptimizationLevel) {
case onyx::O1:
optLvl = onyx::Optimizer::O1;
break;
case onyx::O2:
optLvl = onyx::Optimizer::O2;
break;
case onyx::O3:
optLvl = onyx::Optimizer::O3;
break;
default:
optLvl = onyx::Optimizer::O0;
break;
}
if (onyx::OptimizationLevel > onyx::O0) {
onyx::Optimizer optimizer;
optimizer.Optimize(*mod, optLvl);
}
if (onyx::EmitAction == onyx::EmitLLVM) {
std::error_code ec;
llvm::raw_fd_ostream os(outputName, ec);
if (ec) {
llvm::errs() << ec.message();
return 1;
}
mod->print(os, nullptr);
return 0;
}
std::string objFile = (onyx::EmitAction == onyx::EmitObj) ? outputName : (stem + ".o").str();
if (!onyx::EmitObjectFile(&*mod, objFile, tripleStr)) {
return 1;
}
if (onyx::EmitAction == onyx::EmitBinary) {
onyx::LinkObjectFile(objFile, onyx::GetOutputName(fileName, triple));
llvm::sys::fs::remove(objFile);
}
llvm::outs().flush(); // explicitly flushing the buffer
return 0;
}void
InitializeLLVMTargets();
bool
EmitObjectFile(llvm::Module *mod, const std::string &fileName, std::string targetTripleStr = "");
void
LinkObjectFile(const std::string &objFile, const std::string &exeFile);
std::string
GetOutputName(const std::string &inputFile, const llvm::Triple &triple);
class Optimizer {
public:
enum Level {
O0,
O1,
O2,
O3
};
static void
Optimize(llvm::Module &M, Level L);
};void
Optimizer::Optimize(llvm::Module &mod, Level level) {
if (level == Level::O0) {
return;
}
llvm::LoopAnalysisManager LAM;
llvm::FunctionAnalysisManager FAM;
llvm::CGSCCAnalysisManager CGAM;
llvm::ModuleAnalysisManager MAM;
llvm::PassBuilder PB;
PB.registerModuleAnalyses(MAM);
PB.registerCGSCCAnalyses(CGAM);
PB.registerFunctionAnalyses(FAM);
PB.registerLoopAnalyses(LAM);
PB.crossRegisterProxies(LAM, FAM, CGAM, MAM);
llvm::OptimizationLevel LLVMLvl;
switch (level) {
case Level::O1:
LLVMLvl = llvm::OptimizationLevel::O1;
break;
case Level::O2:
LLVMLvl = llvm::OptimizationLevel::O2;
break;
case Level::O3:
LLVMLvl = llvm::OptimizationLevel::O3;
break;
default:
LLVMLvl = llvm::OptimizationLevel::O0;
break;
}
llvm::ModulePassManager MPM;
if (LLVMLvl == llvm::OptimizationLevel::O3) {
MPM = PB.buildPerModuleDefaultPipeline(LLVMLvl);
}
else {
MPM = PB.buildPerModuleDefaultPipeline(LLVMLvl);
}
MPM.run(mod, MAM);
}static llvm::cl::OptionCategory OnyxCat("Onyx Compiler Options");
static llvm::cl::opt<std::string> InputFilename(
llvm::cl::Positional, llvm::cl::desc("<input file>"), llvm::cl::Required, llvm::cl::cat(OnyxCat)
);
enum OptLevel {
O0,
O1,
O2,
O3
};
static llvm::cl::opt<OptLevel> OptimizationLevel(
llvm::cl::desc("Optimization level:"),
llvm::cl::values(
clEnumValN(O0, "O0", "No optimization"),
clEnumValN(O1, "O1", "Basic optimization"),
clEnumValN(O2, "O2", "Default optimization"),
clEnumValN(O3, "O3", "Aggressive optimization")),
llvm::cl::init(O0), llvm::cl::cat(OnyxCat)
);
enum ActionKind {
EmitAST,
EmitLLVM,
EmitObj,
EmitBinary
};
static llvm::cl::opt<ActionKind> EmitAction(
"emit", llvm::cl::desc("The kind of output to produce:"),
llvm::cl::values(
clEnumValN(EmitAST, "ast", "Print the AST to stdout"),
clEnumValN(EmitLLVM, "llvm", "Emit LLVM IR (.ll)"),
clEnumValN(EmitObj, "obj", "Emit object file (.o)"),
clEnumValN(EmitBinary, "bin", "Emit executable (default)")),
llvm::cl::init(EmitBinary), llvm::cl::cat(OnyxCat)
);
static llvm::cl::opt<std::string> OutputFilename(
"o", llvm::cl::desc("Override output filename"), llvm::cl::value_desc("filename"), llvm::cl::cat(OnyxCat)
);Вот так и выглядит самое в компиляторе - парсинг аргументов командной строки, запуск парсера, семантики и кодгена, линковка, вывод. В последнем блоке кода описан как раз парсинг аргументов с помощью утилиты командной строки llvm::cl. Компилятор первым делом получает имя исходного файла. Затем могут идти аргументы, например, emit, который заканчивает выполнение компиляции на каком-либо этапе (но после парсинга, семантики и кодгена). emit=ast позволяет вывести в консоль всё AST дерево как набор команд. emit=llvm позволяет сохранить в файл читаемый LLVM IR код (имя файла такое же, что и имя исходного файла, но с расширением .ll). emit=obj позволяет сохранить сгенерированный код в объектный файл (имя файла такое же, что и имя исходного файла, но с расширением .o). emit=bin позволяет сохранить сгенерированный код в бинарник (по умолчанию стоит именно этот режим и писать его вручную не нужно. Флаги O0, O1, O2 и O3 отвечают за поптимизации кода на базе оптимизаторов LLVM (их реализация в предпоследнем блоке кода). Флаг -o позволяет задать вручную имя выходного файла. Ах да, точно, вот вам реализация линковщика:
void
InitializeLLVMTargets() {
llvm::InitializeAllTargetInfos();
llvm::InitializeAllTargets();
llvm::InitializeAllTargetMCs();
llvm::InitializeAllAsmParsers();
llvm::InitializeAllAsmPrinters();
}
bool
EmitObjectFile(llvm::Module *mod, const std::string &fileName, std::string targetTripleStr) {
if (targetTripleStr.empty()) {
targetTripleStr = llvm::sys::getDefaultTargetTriple();
}
llvm::Triple triple(targetTripleStr);
mod->setTargetTriple(triple);
std::string error;
const llvm::Target *target = llvm::TargetRegistry::lookupTarget(triple.getTriple(), error);
if (!target) {
llvm::errs() << llvm::errs().RED << "Error looking up target: " << llvm::errs().RESET << error << '\n';
return false;
}
std::string cpu = "generic";
std::string features = "";
llvm::TargetOptions opt;
std::optional<llvm::Reloc::Model> rm = llvm::Reloc::Model::PIC_;
auto *targetMachine = target->createTargetMachine(triple.getTriple(), cpu, features, opt, rm);
mod->setDataLayout(targetMachine->createDataLayout());
std::error_code ec;
llvm::raw_fd_ostream dest(fileName, ec, llvm::sys::fs::OF_None);
if (ec) {
llvm::errs() << llvm::errs().RED << "Could not open file: " << ec.message() << '\n' << llvm::errs().RESET;
return false;
}
llvm::legacy::PassManager pass;
auto fileType = llvm::CodeGenFileType::ObjectFile;
if (targetMachine->addPassesToEmitFile(pass, dest, nullptr, fileType)) {
llvm::errs() << llvm::errs().RED << "TargetMachine can't emit a file of this type\n" << llvm::errs().RESET;
return false;
}
pass.run(*mod);
dest.flush();
return true;
}
void
LinkObjectFile(const std::string &objFile, const std::string &exeFile) {
std::string cmd = "clang " + objFile + " -o " + exeFile;
system(cmd.c_str());
}
std::string
GetOutputName(const std::string &inputFile, const llvm::Triple &triple) {
llvm::StringRef stem = llvm::sys::path::stem(inputFile);
std::string outputExe = stem.str();
if (triple.isOSWindows()) {
outputExe += ".exe";
}
return outputExe;
}Его цель запустить системы LLVM для линковки вашего кода в объектный файл, а затем вызвать в терминале компилятор clang, который за вас этот объектный файл переведет в бинарь. В main мы парсим аргументы, создаем llvm::SourceMgr, лексер, парсер, семантику и кодген. Создаем вектор AST с помощью парсера и проходимся по нему в семантике и кодогенераторе. Если на каком-либо этапе возникнет ошибка, то выходим из функции с кодом 1. Анализируем пропарсенные флаги, применяем оптимизации, если они есть, выводим AST, если нужно, ну и тд.
Заключение
На этом пожалуй всё. Надеюсь я кому-то помог понять, как примерно работают компиляторы и как их писать. Давайте посмотрим на примеры кода на моём языке:
var a: i32 = 10;
var b: i32; // инициализация нулем
const pi: f32 = 3.14159265359f;
fun get_pi() : f32 {
return pi;
}
fun main() : i32 {
var c: i32 = a + 2;
b += c;
a *= b + c;
var radius: i32 = 5;
var circle_sqr: f32 = radius * radius * get_pi();
return 0;
}