Создаем свой собственный язык программирования с использованием LLVM. Часть 2: Семантический анализ
В предыдущей статье мы закончили на том, что мы написали лексический и синтаксический анализаторы для нашего учебного языка. В данной статье мы продолжим начатое и рассмотрим следующую стадию анализа исходного кода программы — семантический анализ.
Семантический анализ
Основная задача семантического анализа заключается в проверки того, что программа корректна с точки зрения языка, например:
Все переменные в программе объявлены;
Все выражения совершаются над корректными типами;
Если в программе используется безусловный/условный переход, то метка, на которую совершается переход должна существовать;
Функция возвращает значение корректного типа.
Замечание. Нужно понимать, что семантический анализ не может выловить все ошибки в программе, а только те их типы, которые были заложены разработчиком компилятора или описаны в спецификации языка. Например в языке C++ компилятор не сможет обнаружить все ошибки работы с памятью, даже если разработчик компилятора внес специальную обработку для выявления ошибок такого типа. Но в Rust ошибки такого типа исключаются на уровне самого языка.
Все семантические правила обычно описываются в спецификации конкретного языка и описывают критерии нахождения не корректных программ на данном языке.
Область видимости (Scope)
Область видимости — это часть программы, в пределах которой идентификатор, объявленный как имя некоторой программной сущности (обычно — переменной, типа данных или функции), остаётся связанным с этой сущностью, то есть позволяет посредством себя обратиться к ней.
Часто в спецификации языка описаны правила, для формирования областей видимости, например может быть глобальная область видимости, область видимости класса, область видимости функции и др. Обычно области видимости образуют иерархию и для поиска сущности, на которую ссылается идентификатор в конкретном месте программы, может понадобиться поиск этого идентификатора во всех уровнях этой иерархии.
В simple есть следующие виды областей видимости:
Модуль (все объявления объявленные на самом верхнем уровне файла);
Класс/Структура (более подробно будут рассмотрены в последующих частях серии);
Функция;
Блок в функции.
Так же в simple объявления не могут перекрывать другие объявление доступные в данной области видимости (за исключением перегрузки функций (рассмотри в последующих частях серии)). В simple, любые переменная объявленная в функции может быть использована в любом месте после ее объявления, любое имя объявленное в модуле может быть использовано в любом месте в этом модуле (т. е. разрешено использовать имя класса до его объявления, если оно находится в этом же модуле).
Более подробно про области видимости можно почитать в [1].
Для работы с областью видимости будем использовать следующий класс:
struct Scope {
Scope(DiagnosticsEngine &D) ;
Scope(Scope* enclosed) ;
Scope(ModuleDeclAST* thisModule) ;
// Поиск идентификатора во всех доступных в данной точке областях видимости
SymbolAST* find(Name* id);
// Поиск идентификатора — члена класса или структуры
SymbolAST* findMember(Name* id, int flags = 0);
// Создать новую область видимости
Scope* push();
// Создать новую область видимости на основе объявления
Scope* push(ScopeSymbol* sym);
// Закрыть текущую область видимости (возвращает родительский Scope)
Scope* pop();
// Воссоздать список областей видимости для иерархии классов
static Scope* recreateScope(Scope* scope, SymbolAST* sym);
// Очистка списка областей видимости и оставить только область видимости
// самого модуля
static void clearAllButModule(Scope* scope);
// Вывод сообщения об ошибке
template
void report(SMLoc Loc, unsigned DiagID, Args &&...Arguments) {
Diag.report(Loc, DiagID, std::forward(Arguments)...);
}
Scope* Enclosed; ///< родительский Scope
ModuleDeclAST* ThisModule; ///< родительский модуль
/// символ для текущей области видимости (например функция или класс)
SymbolAST* CurScope;
/// функция к которой принадлежит область видимости
FuncDeclAST* EnclosedFunc;
StmtAST* BreakLoc; ///< цикл для инструкции break
StmtAST* ContinueLoc; ///< цикл для инструкции continue
LandingPadAST* LandingPad; ///< нужно для генерации кода (см. описание ниже)
DiagnosticsEngine &Diag; ///< модуль диагностики
}; Ниже приведу реализацию данного класса:
Hidden text
SymbolAST* Scope::find(Name* id) {
Scope* s = this;
// Если идентификатор не указан, то это глобальная область
// видимости
if (!id) {
return ThisModule;
}
// Циклический поиск объявления во всех доступных из данной точки
// областях видимости
for ( ; s; s = s->Enclosed) {
if (s->CurScope) {
SymbolAST* sym = s->CurScope->find(id);
if (sym) {
return sym;
}
}
}
return nullptr;
}
SymbolAST* Scope::findMember(Name* id, int flags) {
if (CurScope) {
return CurScope->find(id, flags);
}
return nullptr;
}
Scope* Scope::push() {
Scope* s = new Scope(this);
return s;
}
Scope* Scope::push(ScopeSymbol* sym) {
Scope* s = push();
s->CurScope = sym;
return s;
}
Scope* Scope::pop() {
Scope* res = Enclosed;
delete this;
return res;
}
Scope* Scope::recreateScope(Scope* scope, SymbolAST* sym) {
Scope* p = scope;
// Поиск области видимости самого верхнего уровня (модуля)
while (p->Enclosed) {
p = p->Enclosed;
}
// Создаем список все родительских объявлений
SymbolList symList;
SymbolAST* tmp = sym;
while (tmp->Parent) {
symList.push_back(tmp);
tmp = tmp->Parent;
}
// Воссоздаем все области видимости в обратном порядке объявленных
// сущностей. Нужно для поиска в имени в иерархии классов
for (SymbolList::reverse_iterator it = symList.rbegin(),
end = symList.rend(); it != end; ++it) {
p = p->push((ScopeSymbol*)*it);
}
// Возвращаем созданный Scope
return p;
}
void Scope::clearAllButModule(Scope* scope) {
Scope* p = scope;
while (p->Enclosed) {
p = p->pop();
}
}Проверка типов
Суть проверки типов заключается в том, что бы проверить, что все операции выполняемые в программе производятся с операндами корректных типов.
Проверка типов бывает:
Статическая (данная проверка происходит на этапе компиляции программы);
Динамическая (данная проверка происходит на этапе выполнения программы).
Более подробно можно почитать в [2].
В simple у нас будет статическая проверка и все типы будут определяться во время анализа исходного кода программы. В последующих частях мы добавим классы с поддержкой виртуальных функций, при вызове которых результирующая функция будет разрешаться во время выполнения программы.
Семантический анализ типов
Для начала рассмотрим какие именно функции члены иерархии типов будут отвечать за семантический анализ этих ветвей AST:
struct TypeAST {
...
/// Производит семантический анализ для типа
virtual TypeAST* semantic(Scope* scope) = 0;
/// Проверка на то, что данный тип может быть преобразован в "newType"
virtual bool implicitConvertTo(TypeAST* newType) = 0;
/// Проверка на то, что данный тип совпадает с "otherType"
bool equal(TypeAST* otherType);
/// Сгенерировать и поместить в буфер декорированную строку для
/// данного типа (реализуется в потомках)
virtual void toMangleBuffer(llvm::raw_ostream& output) = 0;
/// Сгенерировать декорированную строку для данного типа
void calcMangle();
llvm::StringRef MangleName; ///< декорированная строка с именем данного типа
};Если посмотреть на приведенный выше код, то можно увидеть, что функция semantic возвращает TypeAST*, это нужно для того, что бы при необходимости можно было бы вернуть новый тип в замен старого. Например в simple можно объявить переменную с типом A и на момент построения дерева мы не можем сказать, какой именно тип будет иметь данная переменная, поэтому во время парсинга будет создан экземпляр типа QualifiedTypeAST, который во время семантического анализа будет заменен типом StructTypeAST или ClassTypeAST (все эти типы будут рассмотрены в последующих частях серии).
Так же можно увидеть, что существуют функции для создания декорированного имени, данная функция генерирует уникальное имя типа в системе и если два объекта производные от TypeAST имеют одинаковое декорированное имя, то эти типы совпадают. Так же декорация имен нужна для создания уникальных имен функций, например функция
fn check(s: string, a: float, b: float)после декорации будет иметь следующие имя
_P5checkPKcffБолее подробнее про декорирование имен (Name mangling) можно посмотреть тут [3].
Теперь мы можем рассмотреть реализацию семантического анализа для иерархии типов:
Hidden text
// Хранит множество всех уникальных декорированных строк
StringSet< > TypeAST::TypesTable;
void TypeAST::calcMangle() {
// Ничего не делаем, если декорированное имя для типа уже задано
if (!MangleName.empty()) {
return;
}
// Для большинства типов 128 байт будет достаточно
llvm::SmallString< 128 > s;
llvm::raw_svector_ostream output(s);
// Пишем декорированное имя в буфер и добавляем в множество имен,
// т. к. StringRef требует выделенный блок памяти со строкой
toMangleBuffer(output);
TypesTable.insert(output.str());
// Устанавливаем внутреннее состояние MangleName на основе записи
// созданной в множестве имен
StringSet< >::iterator pos = TypesTable.find(s);
assert(pos != TypesTable.end());
MangleName = pos->getKeyData();
}
bool TypeAST::equal(TypeAST* otherType) {
// Два типа эквивалентны, если их "MangleName" совпадают, для
// сложных типов это может быть гораздо быстрее, чем сравнивать
// их структуру
assert(!MangleName.empty() && !otherType->MangleName.empty());
return MangleName == otherType->MangleName;
}
TypeAST* BuiltinTypeAST::semantic(Scope* scope) {
// Для базовых типов для проверки семантики достаточно произвести
// декорирование имени типа
calcMangle();
return this;
}
bool BuiltinTypeAST::implicitConvertTo(TypeAST* newType) {
// Список разрешенных преобразований
static bool convertResults[TI_Float + 1][TI_Float + 1] = {
// void bool int float
{ false, false, false, false }, // void
{ false, true, true, true }, // bool
{ false, true, true, true }, // int
{ false, true, true, true }, // float
};
// Только базовые типы могут быть преобразованы друг в друга
if (newType->TypeKind > TI_Float) {
return false;
}
return convertResults[TypeKind][newType->TypeKind];
}
void BuiltinTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
switch (TypeKind) {
case TI_Void : output << "v"; break;
case TI_Bool : output << "b"; break;
case TI_Int : output << "i"; break;
case TI_Float : output << "f"; break;
default: assert(0 && "Should never happen"); break;
}
}
TypeAST* FuncTypeAST::semantic(Scope* scope) {
if (!ReturnType) {
// Если у функции не был задан тип возвращаемого значения, то
// установить как "void"
ReturnType = BuiltinTypeAST::get(TypeAST::TI_Void);
}
// Произвести семантический анализ для типа возвращаемого
// значения
ReturnType = ReturnType->semantic(scope);
// Произвести семантический анализ для всех параметров
for (ParameterList::iterator it = Params.begin(),
end = Params.end(); it != end; ++it) {
(*it)->Param = (*it)->Param->semantic(scope);
}
calcMangle();
return this;
}
bool FuncTypeAST::implicitConvertTo(TypeAST* newType) {
return false;
}
void FuncTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
// Добавляем "v", если функция возвращает "void"
if (Params.empty()) {
output << "v";
return;
}
ParameterList::iterator it = Params.begin(), end = Params.end();
// Произвести декорацию имен для всех параметров
for ( ; it != end; ++it) {
(*it)->Param->toMangleBuffer(output);
}
}На данной стадии у нас есть только несколько базовых типов и семантический анализ для иерархии типов достаточно прост, мы просто генерируем декорированные имена для каждого типа. Но в последующих статьях с добавлением более сложных типов семантический анализ усложнится и список преобразований между типами будет так же расширен.
Семантический анализ выражений
Для начала рассмотрим какие именно функции члены иерархии выражений будут отвечать за семантический анализ этих ветвей AST:
struct ExprAST {
...
/// Проверка, что это целочисленная константа
bool isIntConst() { return ExprKind == EI_Int; }
/// Проверка, что это константное выражение
bool isConst() {
return ExprKind == EI_Int || ExprKind == EI_Float;
}
/// Проверяем, что константное выражение имеет истинное значение
virtual bool isTrue();
/// Проверка на то, что данное выражение может быть использовано
/// в качестве значения с левой стороны от "="
virtual bool isLValue();
/// Произвести семантический анализ выражения
virtual ExprAST *semantic(Scope *scope) = 0;
/// Сделать копию ветви дерева
virtual ExprAST *clone() = 0;
TypeAST *ExprType; ///< тип выражения
};Так же, как и у типов, ExprAST после семантического анализа может быть изменено (например можно сделать оптимизацию и произвести вычисление константных выражений, но в нашем случае мы будем использовать это для замены некоторых выражений их аналогами, что бы упростить генерацию кода).
Рассмотрим более подробно сам семантический анализ для выражений:
Hidden text
bool ExprAST::isTrue() {
return false;
}
bool ExprAST::isLValue() {
return false;
}
bool IntExprAST::isTrue() {
return true;
}
ExprAST* IntExprAST::semantic(Scope* ) {
return this;
}
ExprAST* IntExprAST::clone() {
return new IntExprAST(Loc, Val);
}
bool FloatExprAST::isTrue() {
return Val != 0.0;
}
ExprAST* FloatExprAST::semantic(Scope* ) {
return this;
}
ExprAST* FloatExprAST::clone() {
return new FloatExprAST(Loc, Val);
}
bool IdExprAST::isLValue() {
return true;
}
ExprAST* IdExprAST::semantic(Scope* scope) {
// Если "ThisSym" задан, то семантический анализ над данным
// выражением уже был ранее завершен
if (!ThisSym) {
// Ищем объявление в текущей области видимости
ThisSym = scope->find(Val);
if (!Val) {
return this;
}
if (!ThisSym) {
// Объявление не найдено, возвращаем ошибку
scope->report(Loc, diag::ERR_SemaUndefinedIdentifier,
Val->Id);
return nullptr;
}
// Устанавливаем тип данного выражения в соответствии с типом
// объявленной переменной
ExprType = ThisSym->getType();
}
return this;
}
ExprAST* IdExprAST::clone() {
return new IdExprAST(Loc, Val);
}
ExprAST* CastExprAST::semantic(Scope* scope) {
if (SemaDone) {
return this;
}
// Проверяем, что тип был корректно задан и что это не "void"
assert(ExprType != nullptr && "Type for cast not set");
if (ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaCastToVoid);
return nullptr;
}
// Производим семантический анализ выражения для преобразования
Val = Val->semantic(scope);
// Проверяем, что тип исходного выражения корректный
if (!Val->ExprType || Val->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaCastToVoid);
return nullptr;
}
// Запрещаем преобразования функций
if (isa(ExprType)
|| isa(Val->ExprType)) {
scope->report(Loc, diag::ERR_SemaFunctionInCast);
return nullptr;
}
// Проверяем, что типы совместимы
if (!Val->ExprType->implicitConvertTo(ExprType)) {
scope->report(Loc, diag::ERR_SemaInvalidCast);
return nullptr;
}
SemaDone = true;
return this;
}
ExprAST* CastExprAST::clone() {
return new CastExprAST(Loc, Val->clone(), ExprType);
} Т.к. все выражения с одним операндом могут быть переписаны в виде эквивалентного выражения с двумя операндами, то для упрощения кодогенерации при семантическом анализе мы проверяем корректность операнда и возвращаем эквивалентный аналог:
Hidden text
ExprAST* UnaryExprAST::semantic(Scope* scope) {
// Проверяем, что операнд был корректно задан
if (!Val) {
assert(0 && "Invalid expression value");
return nullptr;
}
// Производим семантический анализ для операнда
Val = Val->semantic(scope);
// Проверяем корректность типа операнда, т. к. он может быть
// "void"
if (!Val->ExprType || Val->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaOperandIsVoid);
return nullptr;
}
// Исключаем операции над булевыми значениями
if (Val->ExprType->isBool() && (Op == tok::Plus
|| Op == tok::Minus)) {
scope->report(Loc, diag::ERR_SemaInvalidBoolForUnaryOperands);
return nullptr;
}
// Список замен:
// +Val to Val
// -Val to 0 - Val
// ~intVal to intVal ^ -1
// ++id to id = id + 1
// --id to id = id - 1
// !Val to Val == 0
ExprAST* result = this;
// Проверяем тип оператора, для необходимой замены
switch (Op) {
// "+" - noop
case tok::Plus: result = Val; break;
case tok::Minus:
// Преобразовываем в 0 - Val с учетом типа Val
if (Val->ExprType->isFloat()) {
result = new BinaryExprAST(Val->Loc, tok::Minus,
new FloatExprAST(Val->Loc, 0),
Val);
} else {
result = new BinaryExprAST(Val->Loc, tok::Minus,
new IntExprAST(Val->Loc, 0),
Val);
}
break;
case tok::Tilda:
// ~ можно применять только к целочисленным выражениям
if (!Val->ExprType->isInt()) {
scope->report(Loc,
diag::ERR_SemaInvalidOperandForComplemet);
return nullptr;
} else {
// Преобразуем в Val ^ -1
result = new BinaryExprAST(Val->Loc, tok::BitXor, Val,
new IntExprAST(Val->Loc, -1));
break;
}
case tok::PlusPlus:
case tok::MinusMinus: {
// "++" и "--" можно вызывать только для IdExprAST в
// качестве операнда и только для целочисленного типа
if (!Val->ExprType->isInt() || !Val->isLValue()) {
scope->report(Loc,
diag::ERR_SemaInvalidPostfixPrefixOperand);
return nullptr;
}
// Необходимо заменить "++" id или "--" id на id = id + 1
// или id = id + -1
ExprAST* val = Val;
ExprAST* valCopy = Val->clone();
result = new BinaryExprAST(Val->Loc, tok::Assign,
val,
new BinaryExprAST(Val->Loc, tok::Plus,
valCopy,
new IntExprAST(Val->Loc,
(Op == tok::PlusPlus) ? 1 : -1)));
}
break;
case tok::Not:
// Заменяем на Val == 0
result = new BinaryExprAST(Val->Loc, tok::Equal, Val,
new IntExprAST(Val->Loc,
0));
break;
default:
// Никогда не должно произойти
assert(0 && "Invalid unary expression");
return nullptr;
}
if (result != this) {
// Т.к. старое выражение было заменено, очищаем память и
// производим семантический анализ нового выражения
Val = nullptr;
delete this;
return result->semantic(scope);
}
return result;
}
ExprAST* UnaryExprAST::clone() {
return new UnaryExprAST(Loc, Op, Val->clone());
}Рассмотрим семантический анализ выражений с двумя операндами:
Hidden text
ExprAST* BinaryExprAST::semantic(Scope* scope) {
// Семантический анализ уже был произведен ранее
if (ExprType) {
return this;
}
// Производим семантический анализ операнда с левой стороны
LeftExpr = LeftExpr->semantic(scope);
// Проверяем на "++" или "--", т. к. эти операции имеют только
// один операнд
if (Op == tok::PlusPlus || Op == tok::MinusMinus) {
// "++" и "--" можно вызывать только для IdExprAST в качестве
// операнда и только для целочисленного типа
if (!LeftExpr->isLValue() || !LeftExpr->ExprType->isInt()) {
scope->report(Loc,
diag::ERR_SemaInvalidPostfixPrefixOperand);
return nullptr;
}
// Устанавливаем результирующий тип выражения
ExprType = LeftExpr->ExprType;
return this;
}
// Производим семантический анализ операнда с правой стороны
RightExpr = RightExpr->semantic(scope);
// Проверяем, что оба операнда имеют корректные типы
if (!LeftExpr->ExprType || !RightExpr->ExprType) {
scope->report(Loc,
diag::ERR_SemaUntypedBinaryExpressionOperands);
return nullptr;
}
// "," имеет специальную обработку и тип выражения совпадает с
// типом операнда с правой стороны
if (Op == tok::Comma) {
ExprType = RightExpr->ExprType;
return this;
}
// Исключаем операции, если хотя бы один операнд имеет тип "void"
if (LeftExpr->ExprType->isVoid()
|| RightExpr->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaOperandIsVoid);
return nullptr;
}
// Проверка на операторы сравнения, т. к. их результат всегда
// будет иметь тип "bool"
switch (Op) {
case tok::Less:
case tok::Greater:
case tok::LessEqual:
case tok::GreaterEqual:
case tok::Equal:
case tok::NotEqual:
// Если левый операнд "bool", то сначала конвертируем его в
// "int"
if (LeftExpr->ExprType->isBool()) {
LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr,
BuiltinTypeAST::get(TypeAST::TI_Int));
LeftExpr = LeftExpr->semantic(scope);
}
// Операнды для "<", "<=", ">", ">=", "==" и "!=" всегда
// должны иметь одинаковые типы, если они отличаются, то
// нужно сделать преобразование
if (!LeftExpr->ExprType->equal(RightExpr->ExprType)) {
RightExpr = new CastExprAST(RightExpr->Loc, RightExpr,
LeftExpr->ExprType);
RightExpr = RightExpr->semantic(scope);
}
// Результирующий тип выражения — "bool"
ExprType = BuiltinTypeAST::get(TypeAST::TI_Bool);
return this;
case tok::LogOr:
case tok::LogAnd:
// Для логических операций оба операнда должны
// конвертироваться в "bool"
if (!LeftExpr->ExprType->implicitConvertTo(
BuiltinTypeAST::get(TypeAST::TI_Bool))
|| !RightExpr->ExprType->implicitConvertTo(
BuiltinTypeAST::get(TypeAST::TI_Bool))) {
scope->report(Loc, diag::ERR_SemaCantConvertToBoolean);
return nullptr;
}
// Результирующий тип выражения — "bool"
ExprType = BuiltinTypeAST::get(TypeAST::TI_Bool);
return this;
default:
// Остальные варианты обрабатываем ниже
break;
}
// Если левый операнд "bool", то сначала конвертируем его в "int"
if (LeftExpr->ExprType == BuiltinTypeAST::get(TypeAST::TI_Bool)) {
LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr,
BuiltinTypeAST::get(TypeAST::TI_Int));
LeftExpr = LeftExpr->semantic(scope);
}
// Результирующий тип выражения будет совпадать с типом левого
// операнда
ExprType = LeftExpr->ExprType;
// Для "=" тоже есть специальная обработка
if (Op == tok::Assign) {
// Если типы левого и правого операнда отличаются, то нужно
// сделать преобразование
if (!LeftExpr->ExprType->equal(RightExpr->ExprType)) {
RightExpr = new CastExprAST(RightExpr->Loc, RightExpr,
LeftExpr->ExprType);
RightExpr = RightExpr->semantic(scope);
}
// Проверяем, что операнд с левой стороны является адресом
if (!LeftExpr->isLValue()) {
scope->report(Loc, diag::ERR_SemaMissingLValueInAssignment);
return nullptr;
}
// Выражение корректно, завершаем анализ
return this;
}
// Если операнды имеют различные типы, то нужно произвести
// преобразования
if (!LeftExpr->ExprType->equal(RightExpr->ExprType)) {
// Если операнд с правой стороны имеет тип "float", то
// результат операции тоже будет "float"
if (RightExpr->ExprType->isFloat()) {
ExprType = RightExpr->ExprType;
LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr,
RightExpr->ExprType);
LeftExpr = LeftExpr->semantic(scope);
} else {
// Преобразуем операнд с правой стороны к типу операнда с
// левой стороны
RightExpr = new CastExprAST(RightExpr->Loc, RightExpr,
LeftExpr->ExprType);
RightExpr = RightExpr->semantic(scope);
}
}
// "int" и "float" имеют отличный набор допустимых бинарных
// операций
if (ExprType == BuiltinTypeAST::get(TypeAST::TI_Int)) {
// Проверяем допустимые операции над "int"
switch (Op) {
case tok::Plus:
case tok::Minus:
case tok::Mul:
case tok::Div:
case tok::Mod:
case tok::BitOr:
case tok::BitAnd:
case tok::BitXor:
case tok::LShift:
case tok::RShift:
return this;
default:
// Никогда не должны сюда попасть, если только нет ошибки
// в парсере
assert(0 && "Invalid integral binary operator");
return nullptr;
}
} else {
// Проверяем допустимые операции над "float"
switch (Op) {
case tok::Plus:
case tok::Minus:
case tok::Mul:
case tok::Div:
case tok::Mod:
case tok::Less:
return this;
default:
// Сообщаем об ошибке, т. к. данная операция не допустима
scope->report(Loc,
diag::ERR_SemaInvalidBinaryExpressionForFloatingPoint);
return nullptr;
}
}
}
ExprAST* BinaryExprAST::clone() {
return new BinaryExprAST(Loc, Op, LeftExpr->clone(),
RightExpr ? RightExpr->clone() : nullptr);
}Семантический анализ тернарного оператор:
Hidden text
bool CondExprAST::isLValue() {
return IfExpr->isLValue() && ElseExpr->isLValue();
}
ExprAST* CondExprAST::semantic(Scope* scope) {
if (SemaDone) {
return this;
}
// Производим семантический анализ условия и всех операндов
Cond = Cond->semantic(scope);
IfExpr = IfExpr->semantic(scope);
ElseExpr = ElseExpr->semantic(scope);
// Проверяем, что условие не является "void"
if (Cond->ExprType == nullptr || Cond->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaConditionIsVoid);
return nullptr;
}
// Проверяем, что условие может быть преобразовано в "bool"
if (!Cond->ExprType->implicitConvertTo(
BuiltinTypeAST::get(TypeAST::TI_Bool))) {
scope->report(Loc, diag::ERR_SemaCantConvertToBoolean);
return nullptr;
}
// Результирующий тип совпадает с тем, что задан в ветке с
// выражением, если условие истинно
ExprType = IfExpr->ExprType;
// Если обе части имеют одинаковые типы, то больше семантический
// анализ завершен
if (IfExpr->ExprType->equal(ElseExpr->ExprType))
SemaDone = true;
return this;
}
// Исключаем вариант, когда один из операндов имеет тип "void",
// но разрешаем если оба операнда имеют тип "void"
if (!IfExpr->ExprType || !ElseExpr->ExprType ||
IfExpr->ExprType->isVoid() || ElseExpr->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaOperandIsVoid);
return nullptr;
}
// Приводим типы к единому
ElseExpr = new CastExprAST(ElseExpr->Loc, ElseExpr, ExprType);
ElseExpr = ElseExpr->semantic(scope);
SemaDone = true;
return this;
}
ExprAST* CondExprAST::clone() {
return new CondExprAST(Loc, Cond->clone(), IfExpr->clone(),
ElseExpr->clone());
}Семантический анализ вызова функции:
Hidden text
static SymbolAST* resolveFunctionCall(Scope *scope, SymbolAST* func,
CallExprAST* args) {
// Проверяем, что это функция
if (isa(func)) {
FuncDeclAST* fnc = static_cast< FuncDeclAST* >(func);
FuncTypeAST* type = static_cast< FuncTypeAST* >(fnc->ThisType);
// Количество аргументов должно совпадать с количеством
// параметров у функции
if (args->Args.size() != type->Params.size()) {
scope->report(args->Loc,
diag::ERR_SemaInvalidNumberOfArgumentsInCall);
return nullptr;
}
ExprList::iterator arg = args->Args.begin();
ParameterList::iterator it = type->Params.begin();
// Проверяем все аргументы
for (ParameterList::iterator end = type->Params.end();
it != end; ++it, ++arg) {
// Проверяем, что аргумент может быть использован для вызова
// и диагностируем об ошибке, если нет
if (!(*arg)->ExprType->implicitConvertTo((*it)->Param)) {
scope->report(args->Loc,
diag::ERR_SemaInvalidTypesOfArgumentsInCall);
return nullptr;
}
}
// Вызов функции может быть произведен с данными аргументами
return func;
}
return nullptr;
}
ExprAST* CallExprAST::semantic(Scope* scope) {
if (ExprType) {
return this;
}
// Производим семантический анализ выражения до "("
Callee = Callee->semantic(scope);
// Мы можем использовать только IdExprAST в качестве выражения
// для вызова
if (isa(Callee)) {
SymbolAST* sym = ((IdExprAST*)Callee)->ThisSym;
// Идентификатор может ссылаться только на функцию
if (isa(sym)) {
TypeAST* returnType = nullptr;
// Производим семантический анализ для всех аргументов
// функции
for (ExprList::iterator arg = Args.begin(), end = Args.end();
arg != end; ++arg) {
*arg = (*arg)->semantic(scope);
}
// Ищем функцию для вызова
if (SymbolAST* newSym = resolveFunctionCall(scope, sym,
this)) {
FuncDeclAST* fnc = static_cast< FuncDeclAST* >(newSym);
FuncTypeAST* type = static_cast< FuncTypeAST* >(
fnc->ThisType);
ExprList::iterator arg = Args.begin();
ParameterList::iterator it = type->Params.begin();
// Производим сопоставление аргументов и параметров
for (ParameterList::iterator end = type->Params.end();
it != end; ++it, ++arg) {
// Если тип аргумента отличается от типа параметра,
// производим преобразование типа
if (!(*arg)->ExprType->equal((*it)->Param)) {
ExprAST* oldArg = (*arg);
*arg = new CastExprAST(oldArg->Loc, oldArg->clone(),
(*it)->Param);
*arg = (*arg)->semantic(scope);
delete oldArg;
}
}
// Определяем тип возвращаемого значения и устанавливаем
// тип для результата вызова функции
if (!returnType) {
ExprType = ((FuncDeclAST*)newSym)->ReturnType;
} else {
ExprType = returnType;
}
// Устанавливаем объявление функции для вызова для
// дальнейшей работы
CallFunc = newSym;
return this;
}
}
}
// Диагностируем ошибку
scope->report(Loc, diag::ERR_SemaInvalidArgumentsForCall);
return nullptr;
}
ExprAST* CallExprAST::clone() {
ExprList exprs;
ExprList::iterator it = Args.begin();
ExprList::iterator end = Args.end();
for ( ; it != end; ++it) {
exprs.push_back((*it)->clone());
}
return new CallExprAST(Loc, Callee->clone(), exprs);
} Семантический анализ инструкций
Для начала рассмотрим какие именно функции члены иерархии инструкций будут отвечать за семантический анализ этих ветвей AST:
struct StmtAST {
...
/// Проверяет есть ли выход из функции в данной ветви дерева
virtual bool hasReturn();
/// Проверяет есть ли инструкция выхода из цикла или возврат из функции в
/// данной ветви дерева
virtual bool hasJump();
/// Произвести семантический анализ для инструкции
StmtAST* semantic(Scope* scope);
/// Произвести семантический анализ для инструкции (должна быть реализована
// в потомках, вызывается только через "semantic"
virtual StmtAST* doSemantic(Scope* scope);
int SemaState; ///< стадия семантического анализа для текущей инструкции
}; Так же, как и у типов и выражений, StmtAST после семантического анализа может быть изменено (например одна инструкция может быть реализована через другую).
Один из важных классов для работы семантического анализа (и генерации кода) является LandingPadAST (более подробное описание зачем он нужен рассмотрим в следующей части серии, на данный момент приведу только те члены класса, которые нужны для семантического анализа):
struct LandingPadAST {
LandingPadAST* Prev; ///< родительский LandingPadAST
StmtAST* OwnerBlock; ///< блок к которому относится данный LandingPadAST
int Breaks; ///< количество инструкций выхода из цикла в ветви дерева
/// количество инструкций возврата из функции в ветви дерева
int Returns;
/// количество инструкций перехода к следующей итерации цикла в ветви дерева
int Continues;
bool IsLoop; ///< LandingPadAST находится частью цикла
};Рассмотрим более подробно сам семантический анализ для инструкций:
Hidden text
bool StmtAST::hasReturn() {
return false;
}
bool StmtAST::hasJump() {
return false;
}
StmtAST* StmtAST::semantic(Scope* scope) {
// Защита от повторного вызова
if (SemaState > 0) {
return this;
}
++SemaState;
return doSemantic(scope);
}
StmtAST* StmtAST::doSemantic(Scope* ) {
assert(0 && "StmtAST::semantic should never be reached");
return this;
}
StmtAST* ExprStmtAST::doSemantic(Scope* scope) {
if (Expr) {
// Проверка семантики выражения
Expr = Expr->semantic(scope);
// После окончания семантического анализа хранимого выражения
// у него должен быть задан тип
if (!Expr->ExprType) {
scope->report(Loc, diag::ERR_SemaNoTypeForExpression);
return nullptr;
}
}
return this;
}
bool BlockStmtAST::hasReturn() {
return HasReturn;
}
bool BlockStmtAST::hasJump() {
return HasJump;
}
StmtAST* BlockStmtAST::doSemantic(Scope* scope) {
// Для блока мы должны создать новую область видимости
ThisBlock = new ScopeSymbol(Loc, SymbolAST::SI_Block, nullptr);
Scope* s = scope->push((ScopeSymbol*)ThisBlock);
// Создать LandingPadAST для данного блока
LandingPad = new LandingPadAST(s->LandingPad);
LandingPad->OwnerBlock = this;
s->LandingPad = LandingPad;
ExprList args;
// Проверяем все ветви дерева принадлежащие данному блоку
for (StmtList::iterator it = Body.begin(), end = Body.end();
it != end; ++it) {
// Если в предыдущей инструкции был "break", "continue" или
// "return", то диагностируем об ошибке (предотвращаем
// появление кода, который не может быть достижимым
if (HasJump) {
scope->report(Loc, diag::ERR_SemaDeadCode);
return nullptr;
}
// Проверяем семантику вложенной инструкции
*it = (*it)->semantic(s);
// Проверяем, что это "break", "continue" или "return"
if ((*it)->isJump()) {
HasJump = true;
// Проверяем, что это "return"
if ((*it)->hasReturn()) {
HasReturn = true;
}
} else {
// Это обычная инструкция, но все равно проверяем, наличие
// "break", "continue" или "return" в дочерних ветках
// инструкции
HasJump = (*it)->hasJump();
HasReturn = (*it)->hasReturn();
}
}
// Удаляем область видимости
s->pop();
return this;
}
StmtAST* DeclStmtAST::doSemantic(Scope* scope) {
// Производим семантический анализ для всех объявлений
for (SymbolList::iterator it = Decls.begin(), end = Decls.end();
it != end; ++it) {
(*it)->semantic(scope);
(*it)->semantic2(scope);
(*it)->semantic3(scope);
(*it)->semantic4(scope);
(*it)->semantic5(scope);
}
return this;
}
bool BreakStmtAST::hasJump() {
return true;
}
StmtAST* BreakStmtAST::doSemantic(Scope* scope) {
// Проверяем, что мы находимся в цикле, т. к. "break" может быть
// только в цикле
if (!scope->BreakLoc) {
scope->report(Loc, diag::ERR_SemaInvalidJumpStatement);
return nullptr;
}
// Запоминаем местоположение точки, куда нужно перевести
// управление для выхода из цикла
BreakLoc = scope->LandingPad;
++BreakLoc->Breaks;
return this;
}
// ContinueStmtAST implementation
bool ContinueStmtAST::hasJump() {
return true;
}
StmtAST* ContinueStmtAST::doSemantic(Scope* scope) {
// Проверяем, что мы находимся в цикле, т. к. "continue" может
// быть только в цикле
if (!scope->ContinueLoc) {
scope->report(Loc, diag::ERR_SemaInvalidJumpStatement);
return nullptr;
}
// Запоминаем местоположение точки, куда нужно перевести
// управление для перехода к следующей итерации цикла
ContinueLoc = scope->LandingPad;
++ContinueLoc->Continues;
return this;
}
bool ReturnStmtAST::hasReturn() {
return true;
}
bool ReturnStmtAST::hasJump() {
return true;
}
StmtAST* ReturnStmtAST::doSemantic(Scope* scope) {
assert(scope→LandingPad);
// Сохраняем местоположения точки, куда нужно перевести
// управление для выхода из функции
ReturnLoc = scope->LandingPad;
++ReturnLoc->Returns;
// Проверка наличия возвращаемого значения
if (Expr) {
// Если тип возвращаемого значения функции "void", то
// сигнализируем об ошибке
if (!scope->EnclosedFunc->ReturnType
|| scope->EnclosedFunc->ReturnType->isVoid()) {
scope->report(Loc, diag::ERR_SemaReturnValueInVoidFunction);
return nullptr;
}
// Производим семантический анализ возвращаемого значения
Expr = Expr->semantic(scope);
// Если тип возвращаемого значения не совпадает с типом
// возвращаемого значения самой функции, то мы должны
// произвести преобразование типов
if (!scope->EnclosedFunc->ReturnType->equal(Expr->ExprType)) {
Expr = new CastExprAST(Loc, Expr,
scope->EnclosedFunc->ReturnType);
Expr = Expr->semantic(scope);
}
return this;
}
// У нас нет выражения для возврата. Проверяем, что тип
// возвращаемого значения самой функции "void" и сигнализируем
// об ошибке, если он отличен от "void"
if (scope->EnclosedFunc->ReturnType
&& !scope->EnclosedFunc->ReturnType->isVoid()) {
scope->report(Loc, diag::ERR_SemaReturnVoidFromFunction);
return nullptr;
}
return this;
}
bool WhileStmtAST::hasReturn() {
// Всегда возвращаем "false", т. к. может быть 0 итераций
return false;
}
StmtAST* WhileStmtAST::doSemantic(Scope* scope) {
// Производим семантический анализ условия цикла
Cond = Cond->semantic(scope);
// Условие цикла должно иметь не "void" тип
if (!Cond->ExprType || Cond->ExprType->isVoid()) {
scope->report(Loc, diag::ERR_SemaConditionIsVoid);
return nullptr;
}
// Проверяем, что условие цикла может быть преобразовано в "bool"
if (!Cond->ExprType->implicitConvertTo(
BuiltinTypeAST::get(TypeAST::TI_Bool))) {
scope->report(Loc, diag::ERR_SemaCantConvertToBoolean);
return nullptr;
}
// Делаем копии для точек возврата из цикла и перехода к
// следующей итерации
StmtAST* oldBreak = scope->BreakLoc;
StmtAST* oldContinue = scope->ContinueLoc;
// Устанавливаем данный цикл в качестве точек возврата из цикла
// и перехода к следующей итерации
scope->BreakLoc = this;
scope->ContinueLoc = this;
// Создаем новую LandingPadAST для всех вложенных инструкций
LandingPad = new LandingPadAST(scope->LandingPad);
LandingPad->IsLoop = true;
scope->LandingPad = LandingPad;
// Производим семантический анализ тела цикла
Body = Body->semantic(scope);
// Восстанавливаем предыдущие значения для точек возврата
scope->BreakLoc = oldBreak;
scope->ContinueLoc = oldContinue;
scope->LandingPad = LandingPad->Prev;
if (PostExpr) {
// Производим семантический анализ для "PostExpr", который был
// создан в процессе конвертации цикла "for" в цикл "while"
PostExpr = PostExpr->semantic(scope);
}
return this;
}
StmtAST* ForStmtAST::doSemantic(Scope* scope) {
// Заменяем цикл "for" эквивалентным аналогом цикла "while", что
// бы упростить генерацию кода, но предварительно проверив
// семантику
// {
// init
// while (cond) {
// body
// continueZone: post
// }
// }
StmtAST* init = nullptr;
// Если в цикле задано выражение для инициализации или объявлены
// переменные цикла, то нужно создать на их основе
// соответствующие инструкции
if (InitExpr) {
init = new ExprStmtAST(Loc, InitExpr);
} else if (!InitDecls.empty()) {
init = new DeclStmtAST(Loc, InitDecls);
}
if (Cond) {
// У нас есть условие выхода из цикла
StmtList stmts;
// Если у нас есть блок инициализации цикла, то добавляем его
// к телу новой конструкции
if (init) {
stmts.push_back(init);
}
// Создаем новый цикл "while" на основе данного цикла "for" и
// добавляем его к списку инструкций в блоке
WhileStmtAST* newLoop = new WhileStmtAST(Loc, Cond, Body);
newLoop->PostExpr = Post;
stmts.push_back(newLoop);
// Очищаем и удаляем данную ветку
InitExpr = nullptr;
InitDecls.clear();
Cond = nullptr;
Post = nullptr;
Body = nullptr;
delete this;
// Создаем новы блочный элемент для нового цикла и производим
// его семантический анализ
StmtAST* res = new BlockStmtAST(Loc, stmts);
return res->semantic(scope);
} else {
// У нас нет условия выхода из цикла
StmtList stmts;
// Если у нас есть блок инициализации цикла, то добавляем его
// к телу новой конструкции
if (init) {
stmts.push_back(init);
}
// Создаем новый цикл "while" на основе данного цикла "for" и
// добавляем его к списку инструкций в блоке
WhileStmtAST* newLoop = new WhileStmtAST(Loc,
new IntExprAST(Loc, 1),
Body);
newLoop->PostExpr = Post;
stmts.push_back(newLoop);
// Очищаем и удаляем данную ветку
InitExpr = nullptr;
InitDecls.clear();
Cond = nullptr;
Post = nullptr;
Body = nullptr;
delete this;
// Создаем новы блочный элемент для нового цикла и производим
// его семантический анализ
StmtAST* res = new BlockStmtAST(Loc, stmts);
return res->semantic(scope);
}
}
bool IfStmtAST::hasReturn() {
if (!ElseBody) {
return false;
}
// Возвращаем "true" только если обе ветки имеют инструкции
// возврата из функции
return ThenBody->hasReturn() && ElseBody->hasReturn();
}
bool IfStmtAST::hasJump() {
if (!ElseBody) {
return false;
}
// Возвращаем "true" только если обе ветки имеют инструкции
// возврата из функции или выхода из цикла
return ThenBody->hasJump() && ElseBody->hasJump();
}
StmtAST* IfStmtAST::doSemantic(Scope* scope) {
// Производим семантический анализ условия
Cond = Cond->semantic(scope);
// Запрещаем условия с типом "void"
if (!Cond->ExprType
|| Cond->ExprType == BuiltinTypeAST::get(TypeAST::TI_Void)) {
scope->report(Loc, diag::ERR_SemaConditionIsVoid);
return nullptr;
}
// Проверяем, что условие может быть преобразовано в "bool"
if (!Cond->ExprType->implicitConvertTo(
BuiltinTypeAST::get(TypeAST::TI_Bool))) {
scope->report(Loc, diag::ERR_SemaCantConvertToBoolean);
return nullptr;
}
// Создаем новый LandingPadAST
LandingPad = new LandingPadAST(scope->LandingPad);
scope->LandingPad = LandingPad;
// Производим семантический анализ ветки, если условие истинно
ThenBody = ThenBody->semantic(scope);
// Производим семантический анализ ветки, если условие ложно,
// если она есть
if (ElseBody) {
ElseBody = ElseBody->semantic(scope);
}
// Восстанавливаем старый LandingPadAST
scope->LandingPad = LandingPad->Prev;
return this;
}Семантический анализ для объявлений
Для начала рассмотрим какие именно функции члены иерархии объявлений будут отвечать за семантический анализ этих ветвей AST:
struct SymbolAST {
/// Получить тип объявления
virtual TypeAST *getType();
/// Произвести 1 фазу семантического анализа
void semantic(Scope *scope);
/// Произвести 2 фазу семантического анализа
void semantic2(Scope *scope);
/// Произвести 3 фазу семантического анализа
void semantic3(Scope *scope);
/// Произвести 4 фазу семантического анализа
void semantic4(Scope *scope);
/// Произвести 5 фазу семантического анализа
void semantic5(Scope *scope);
/// Произвести 1 фазу семантического анализа (должна быть переопределена в
/// потомках, вызывается только через "semantic")
virtual void doSemantic(Scope *scope);
/// Произвести 2 фазу семантического анализа (может быть переопределена в
/// потомках, вызывается только через "semantic2")
virtual void doSemantic2(Scope *scope);
/// Произвести 3 фазу семантического анализа (может быть переопределена в
/// потомках, вызывается только через "semantic3")
virtual void doSemantic3(Scope *scope);
/// Произвести 4 фазу семантического анализа (может быть переопределена в
/// потомках, вызывается только через "semantic4")
virtual void doSemantic4(Scope *scope);
/// Произвести 5 фазу семантического анализа (может быть переопределена в
/// потомках, вызывается только через "semantic5")
virtual void doSemantic5(Scope *scope);
/// Поиск дочернего объявления ("flags" — 1 если не нужен поиск в
/// родительских классах)
virtual SymbolAST *find(Name *id, int flags = 0);
/// область видимости, в которой было объявлено данное объявление
SymbolAST *Parent;
int SemaState; ///< текущая стадия семантического анализа
}; Из-за правил поиска идентификаторов в simple, весь семантический анализ был разбит на 5 фаз:
Создание списка всех объявлений в области видимости;
Разрешение типов базовых классов;
Разрешение типов для имен переменных и функций членов структур и классов;
Построение таблиц виртуальных функций, конструкторов и деструкторов;
Анализ функций и их тел.
Разбивка семантики на несколько фаз позволяет упростить грамматику языка, т. к. не нужно вводить дополнительные конструкции для объявления и определения (т. е. введение имени в программу (что бы оно могло быть использовано) и описание ее реализации (т. е. для классов это описание всех его функций и переменных членов, а для функций ее тело). Например в C++ можно сперва объявить класс (написать «class A;»), что позволяет использовать имя этого класса в других объявлениях (например в качестве параметра функции), а потом в другой части исходного кода произвести определение — описать все функции и переменные члены класса. При разбивке семантического анализа на части, такие разграничения объявления и определения на разные сущности просто не нужны, т. к. даже циклические зависимости могут быть спокойно разрешены, т. к. в каждой фазе происходят действия, которые позволят продолжить анализ на следующих стадиях.
Ниже р
