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();
  }
}

// Хранит множество всех уникальных декорированных строк
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);
  }
}

bool ExprAST::isTrue() { 
  return false; 
}

bool ExprAST::isLValue() {
  return false;
}

bool IntExprAST::isTrue() {
  return Val != 0;
}

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<FuncTypeAST>(ExprType)
      || isa<FuncTypeAST>(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);
}

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());
}

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);
}

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());
}

static SymbolAST* resolveFunctionCall(Scope *scope, SymbolAST* func,
                                      CallExprAST* args) {
  // Проверяем, что это функция
  if (isa<FuncDeclAST>(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<IdExprAST>(Callee)) {
    SymbolAST* sym = ((IdExprAST*)Callee)->ThisSym;

    // Идентификатор может ссылаться только на функцию
    if (isa<FuncDeclAST>(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);
}

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;
}

TypeAST* SymbolAST::getType() {
  assert(0 && "SymbolAST::getType should never be reached");
  return nullptr;
}

void SymbolAST::semantic(Scope* scope) {
  // Пропускаем семантический анализ для этой фазы, если она уже 
  // была завершена
  if (SemaState > 0) {
    return;
  }

  // Произвести семантический анализ и переход к следующей стадии
  doSemantic(scope);
  ++SemaState;
}

void SymbolAST::semantic2(Scope* scope) {
  // Пропускаем семантический анализ для этой фазы, если она уже 
  // была завершена
  assert(SemaState >= 1);
  if (SemaState > 1) {
    return;
  }

  // Произвести семантический анализ и переход к следующей стадии
  doSemantic2(scope);
  ++SemaState;
}

void SymbolAST::semantic3(Scope* scope) {
  // Пропускаем семантический анализ для этой фазы, если она уже 
  // была завершена
  assert(SemaState >= 2);
  if (SemaState > 2) {
    return;
  }

  // Произвести семантический анализ и переход к следующей стадии
  doSemantic3(scope);
  ++SemaState;
}

void SymbolAST::semantic4(Scope* scope) {
  // Пропускаем семантический анализ для этой фазы, если она уже 
  // была завершена
  assert(SemaState >= 3);
  if (SemaState > 3) {
    return;
  }

  // Произвести семантический анализ и переход к следующей стадии
  doSemantic4(scope);
  ++SemaState;
}

void SymbolAST::semantic5(Scope* scope) {
  // Пропускаем семантический анализ для этой фазы, если она уже 
  // была завершена
  assert(SemaState >= 4);
  if (SemaState > 4) {
    return;
  }

  // Произвести семантический анализ и переход к следующей стадии
  doSemantic5(scope);
  ++SemaState;
}

void SymbolAST::doSemantic(Scope* ) {
  // Данная функция обязательна для реализации в дочерних классах
  assert(0 && "SymbolAST::semantic should never be reached");
}

void SymbolAST::doSemantic2(Scope* ) {
  // По умолчанию игнорируем данную фазу
}

void SymbolAST::doSemantic3(Scope* ) {
  // По умолчанию игнорируем данную фазу
}

void SymbolAST::doSemantic4(Scope* ) {
  // По умолчанию игнорируем данную фазу
}

void SymbolAST::doSemantic5(Scope* ) {
  // По умолчанию игнорируем данную фазу
}

SymbolAST* SymbolAST::find(Name* id, int flags) {
  // В базовой реализации только проверяем имя самой сущности
  if (id == Id) {
    return this;
  }

  return nullptr;
}

TypeAST* VarDeclAST::getType() {
  return ThisType;
}

void VarDeclAST::doSemantic(Scope* scope) {
  // Исключаем повторные объявления переменных
  if (scope->find(Id)) {
    scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
    return;
  }
  // Добавляем переменную в список объявленных переменных в текущей
  // области видимости
  ((ScopeSymbol*)scope->CurScope)->Decls[Id] = this;
  Parent = scope->CurScope;
  // Так же добавляем переменную к списку объявленных переменных в
  // функции, если она была объявлена в функции (нужны для 
  // генерации кода)
  if (scope->EnclosedFunc) {
    scope->EnclosedFunc->FuncVars.push_back(this);
  }
  // Производим семантический анализ для типа переменной
  ThisType = ThisType->semantic(scope);
}

void VarDeclAST::doSemantic3(Scope* scope) {
  // Проверяем наличие инициализатора
  if (Val) {
    // Производим семантический анализ инициализирующего выражения
    Val = Val->semantic(scope);

    // Запрещаем использования выражений с типов "void" в 
    // инициализации
    if (!Val->ExprType || Val->ExprType->isVoid()) {
      scope->report(Loc, diag::ERR_SemaVoidInitializer);
      return;
    }

    // Если типы не совпадают, то добавляем преобразование
    if (!Val->ExprType->equal(ThisType)) {
      Val = new CastExprAST(Loc, Val, ThisType);
      Val = Val->semantic(scope);
    }
  }
}

ScopeSymbol::~ScopeSymbol() {
}

SymbolAST* ScopeSymbol::find(Name* id, int /*flags*/) {
  // Производим поиск в объявленных в данном блоке объявлениях
  SymbolMap::iterator it = Decls.find(id);

  if (it == Decls.end()) {
    return nullptr;
  }

  return it->second;
}

TypeAST* ParameterSymbolAST::getType() {
  return Param->Param;
}

void ParameterSymbolAST::doSemantic(Scope* ) {
}

SymbolAST* ParameterSymbolAST::find(Name* id, int ) {
  if (id == Param->Id) {
    return this;
  }

  return nullptr;
}

TypeAST* FuncDeclAST::getType() {
  return ThisType;
}

void FuncDeclAST::doSemantic(Scope* scope) {
  // Производим семантический анализ для прототипа функции
  ThisType = ThisType->semantic(scope);
  Parent = scope->CurScope;
  // Настраиваем тип возвращаемого значения
  ReturnType = ((FuncTypeAST*)ThisType)->ReturnType;
  
  // Отдельная проверка для функции "main"
  if (Id->Length == 4 && memcmp(Id->Id, "main", 4) == 0) {
    FuncTypeAST* thisType = (FuncTypeAST*)ThisType;

    // Должна не иметь параметров
    if (thisType->Params.size()) {
      scope->report(Loc, diag::ERR_SemaMainParameters);
      return;
    }
    
    // Должна возвращать "float"
    if (ReturnType != BuiltinTypeAST::get(TypeAST::TI_Float)) {
      scope->report(Loc, diag::ERR_SemaMainReturnType);
      return;
    }
  }

  // Проверяем, что идентификатор еще не был объявлен ранее
  if (SymbolAST* fncOverload = scope->findMember(Id, 1)) {
    scope->report(Loc, diag::ERR_SemaFunctionRedefined, Id->Id);
    return;
  }

  // Добавляем функцию к списку объявлений
  ((ScopeSymbol*)Parent)->Decls[Id] = this;
}

void FuncDeclAST::doSemantic5(Scope* scope) {
  FuncTypeAST* func = (FuncTypeAST*)ThisType;
  // Проверяем наличие тела функции (если его нет, то это прототип)
  if (Body) {
    // Создаем новую область видимости и устанавливаем текущую
    // функции в данной области видимости
    Scope* s = scope->push(this);
    s->EnclosedFunc = this;

    // Производим проверку всех параметров функции
    for (ParameterList::iterator it = func->Params.begin(),
         end = func->Params.end(); it != end; ++it) {
      ParameterAST* p = *it;
      // Особая обработка для именованных параметров
      if (p->Id) {
        // Запрещаем переопределение
        if (find(p->Id)) {
          scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
          return;
        }

        // Для каждого параметра в прототипе, создаем отдельную 
        // переменную в самой функции
        SymbolAST* newSym = new ParameterSymbolAST(p);
        Decls[p->Id] = newSym;
        FuncVars.push_back(newSym);
      }
    }

    // Устанавливаем новый LandingPadAST
    LandingPadAST* oldLandingPad = s->LandingPad;
    LandingPad = new LandingPadAST();
    s->LandingPad = LandingPad;

    // Производим семантический анализ тела функции
    Body = Body->semantic(s);

    // Восстанавливаем старый LandingPadAST
    s->LandingPad = oldLandingPad;

    // Проверяем, что функция с типов возвращаемого значения 
    // отличным от "void" вернуло значение
    if (!ReturnType->isVoid() && !Body->hasReturn()) {
      scope->report(Loc,
                    diag::ERR_SemaMissingReturnValueInFunction);
      return;
    }

    // Удаляем область видимости для данной функции
    s->pop();
  }
}

// Функции, которые будут доступны из simple
extern "C" void lle_X_printDouble(double val) {
  outs() << val;
}

extern "C" void lle_X_printLine() {
  outs() << "\n";
}

/// Добавить прототип функции и связать ее с функцией C++
FuncDeclAST* addDynamicFunc(const char* protoString,
                            const char* newName,
                            ModuleDeclAST* modDecl,
                            void* fncPtr) {
  // Разбор прототипа функции
  FuncDeclAST* func = (FuncDeclAST*)parseFuncProto(protoString);
  // Добавляем функцию и указываем, что ее компиляция уже была 
  // произведена
  func->CodeValue = Function::Create(
    (FunctionType*)func->ThisType->getType(),
    Function::ExternalLinkage,
    Twine(newName),
    getSLContext().TheModule
  );
  func->Compiled = true;
  modDecl->Members.insert(modDecl->Members.begin(), func);

  // Делаем функцию доступной из LLVM
  ExitOnError ExitOnErr;

  ExitOnErr(getJIT().addSymbol(newName, fncPtr));

  return func;
}

void initRuntimeFuncs(ModuleDeclAST* modDecl) {
  addDynamicFunc("fn print(_: float)", "lle_X_printDouble", 
                 modDecl, (void*)lle_X_printDouble);
  addDynamicFunc("fn printLn()", "lle_X_printLine",
                 modDecl, (void*)lle_X_printLine);
}

void ModuleDeclAST::semantic() {
  Scope s(this);
  
  // Инициализация runtime функций
  initRuntimeFuncs(this);

  // Производим семантический анализ всех базовых типов
  for (int i = TypeAST::TI_Void; i <= TypeAST::TI_Float; ++i) {
    BuiltinTypeAST::get(i)->semantic(&s);
  }

  // Производим семантический анализ для всех объявлений 
  // (кроме функций)
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    if (!isa<FuncDeclAST>(*it))
      (*it)->semantic(&s);
  }

  // Производим семантический анализ всех функций
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    if (isa<FuncDeclAST>(*it))
      (*it)->semantic(&s);
  }

  // Запускаем 2-ю фазу семантического анализа для всех объявлений
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    (*it)->semantic2(&s);
  }

  // Запускаем 3-ю фазу семантического анализа для всех объявлений
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    (*it)->semantic3(&s);
  }

  // Запускаем 4-ю фазу семантического анализа для всех объявлений
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    (*it)->semantic4(&s);
  }

  // Запускаем 5-ю фазу семантического анализа для всех объявлений
  for (SymbolList::iterator it = Members.begin(),
       end = Members.end(); it != end; ++it) {
    (*it)->semantic5(&s);
  }
}