Создаем свой собственный язык программирования с использованием LLVM. Часть 4: Поддержка составных типов

В предыдущей статье мы закончили на том, что реализовали полностью законченное подмножество нашего учебного языка, в котором есть целые и вещественные числа, функции и множество управляющих конструкций, такие как: циклы, операторы ветвления и некоторые другие. В этой части мы продолжим расширять данный язык и добавим в него: строки, указатели, массивы и структуры, а так же операции для работы с ними.

Оглавление серии

1. Лексический и синтаксический анализ

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

3. Генерация кода

4. Поддержка составных типов

5. Поддержка классов и перегрузки функций

Введение

Для начала опишем, что именно мы хотим получить в результате.

1. Добавить два базовых типа "char" и "string";

2. Добавить поддержку двух новых типов констант:

• Строковые литералы (например "Hello, world");

• Символьные литералы (например 'd').

3. Массивы (например int[10]) и операции получения элемента массива по индексу;

4. Указатели (например int*) и операции над ними (такие как: ++/--, & и *), а так же поддержка индексации;

5. Структуры (например struct A { a: int; b: float; }), а так же возможность обращаться к членам структуры через оператор ".".

Для реализации всего этого нам нужно будет внести изменения во все 4 части нашего интерпретатора: лексический, синтаксический и семантический анализ, а так же в генерацию кода.

Примечание: В статье будут приведены только изменения, которые нужно внести для реализации всех вышеперечисленных компонентов, полный исходный код можно посмотреть в репозитории на github.

Примечание: В языке составные типы считаются с правой стороны, т. е. для "int*[2][3]" тип будет массив из 3 элементов типа массив из 2 элементов типа указателей на int. Что может быть не совсем удобным для использования в операторах индексирования, т. к. мы сможем записать a[2][1], но не a[1][2] (т. к. для второго индекса максимальное к-во элементов — 2, не 3).

Лексический и синтаксический анализ

Первое, что нам нужно сделать это добавить новые типы лексем в include/Basic/TokenKinds.def.

Новые ключевые слова:

KEYWORD(String, "string") 
KEYWORD(Char, "char") 
KEYWORD(Struct, "struct") 
KEYWORD(New, "new") 
KEYWORD(Delete, "del") 

Новые литералы:

TOK(CharLiteral, "")
TOK(StringConstant, "") 

Новые операторы:

TOK(Dot, ".")
TOK(OpenBrace, "[")
TOK(CloseBrace, "]")

Так же нам необходимо внести изменения в описание Name:

struct Name { 
  ...
  static Name *New;    ///< ключевое слово "new"
  static Name *Delete; ///< ключевое слово "del" 
}; 

Так же нам нужно инициализировать эти переменные в Lexer во время инициализации ключевых слов:

void NamesMap::addKeywords() { 
  if (IsInit) { 
    return; 
  } 

#define KEYWORD(NAME, TEXT)                               \ 
  addName(StringRef(TEXT), tok::NAME); 
#include "simple/Basic/TokenKinds.def" 

  Name::New = getName("new"); 
  Name::Delete = getName("delete"); 

  IsInit = true; 
}

Объявление этих переменных необходимы, т. к. в дальнейшем мы будем использовать их для того, что бы связать системные функции выделения блока памяти и освобождения блока памяти с этими именами, позже мы будем использовать их и для конструкторов и деструкторов классов.

Следующее, что нам нужно сделать, это добавить поддержку новых операторов и литералов в лексическом анализаторе (поддержка новых ключевых слов дополнительных доработок в нем не требует):

Hidden text

void Lexer::next(Token &Result) { 
  // Устанавливаем токен в качестве недействительного
  Result.Kind = tok::Invalid; 

  // Сохраняем текущую позицию во входном потоке и будем 
  // использовать эту позицию для чтения, что бы не испортить 
  // состояние лексического анализатора
  const char *p = CurPos; 

  // Считываем символы, пока не найдем корректный токен
  while (Result.Kind == tok::Invalid) { 
    const char *tokenStart = p;
    ...
    // Переходим к следующему символу, но запоминаем его значение и 
    // смотрим что это за символ
    switch (char ch = *p++) { 
      ...
      // Анализ новых операторов состоящих из одного символа
      CHECK_ONE('[', tok::OpenBrace); 
      CHECK_ONE(']', tok::CloseBrace); 
      CHECK_ONE('.', tok::Dot); 

      ...
      case '\'': { 
        // Это символьный литерал
        char resultCh = ' '; 
        // Проверяем на закрытие литерала, и если есть какой-либо 
        // символ, то сохраняем его
        if (*p != '\'') { 
          resultCh = *p; 
          ++p; 
        } 
        // Проверяем, что литерал имеет закрывающую '
        if (*p != '\'') { 
          Diags.report(getLoc(p), 
                       diag::ERR_UnterminatedCharOrString); 
        } 

        ++p; 
        // Создаем токен на основе полученной информации
        Result.Length = (int)(p - tokenStart); 
        Result.Chr = resultCh; 
        Result.Kind = tok::CharLiteral; 
        break; 
      } 

      case '"': { 
        // Это строковый литерал
        llvm::SmallString<32> str; 
        // Считываем, пока у нас во входном потоке еще есть данные
        while (*p != 0) { 
          // Проверяем, что это "
          if (*p == '"') { 
            // Проверяем, что это не "
            if (p[1] != '"') { 
              // Заканчиваем чтение строкового литерала
              break; 
            } 

            // Заменяем "" на "
            p += 2; 
            str.push_back('"'); 
          } else if (*p == '\\') { 
            // Проверяем на эскейп последовательность
            ++p; 
            // Обрабатываем только \n 
            if (*p == 'n') { 
              str.push_back('\n'); 
              ++p; 
             // и \\
            } else if (*p == '\\') { 
              str.push_back('\\'); 
              ++p; 
            } else { 
              Diags.report(getLoc(p), 
                           diag::ERR_InvalidEscapeSequence); 
            }
          } else if (*p == '\r' || *p == '\n') { 
            // Мы встретили конец строки в литерале, сообщаем об 
            // ошибке
            Diags.report(getLoc(p), diag::ERR_NewLineInString); 
          } else { 
            // Добавляем символ к строке
            str.push_back(*p); 
            ++p; 
          } 
        } 
        // Проверяем, что у нас есть завершающий символ " 
        if (*p != '"') { 
          Diags.report(getLoc(p),
                       diag::ERR_UnterminatedCharOrString); 
        } 
        // Пропускаем "
        ++p; 
        // Создаем токен на основе полученной информации
        Result.Kind = tok::StringConstant; 
        Result.Length = str.size(); 
        Result.Literal = new char[Result.Length + 1]; 
        memcpy(Result.Literal, str.c_str(), Result.Length); 
        Result.Literal[Result.Length] = 0; 
        break; 
      } 
      ...
    } 
    Result.Ptr = tokenStart; 
  } 

  // Обновляем текущую позицию в лексическом анализаторе
  CurPos = p; 
}

В синтаксическом анализаторе нам нужно будет добавить поддержку всех новых конструкций языка.

Поддержка новых литералов:

Hidden text

/// primary-expr 
///   ::= floating-point-literal 
///   ::= integral-literal 
///   ::= '.'? identifier 
///   ::= char-literal 
///   ::= string-literal 
///   ::= '(' expr ')' 
ExprAST *Parser::parsePrimaryExpr() { 
  ExprAST *result = nullptr; 

  switch (CurPos->getKind()) { 
    ...
    case tok::CharLiteral: 
      // Это символьная константа. Строим ветку дерева и считываем
      // следующий токен
      result = new IntExprAST(CurPos.getLocation(), 
                              CurPos->getChar()); 
      ++CurPos; 
      return result; 
    case tok::StringConstant: 
      // Это строковая константа. Строим ветку дерева и считываем
      // следующий токен
      result = new StringExprAST(CurPos.getLocation(), 
                                 CurPos->getLiteral()); 
      ++CurPos; 
      return result; 
    case tok::Dot: 
      // Идентификаторы могут начинаться с ".", проверяем этот 
      // случай
      if ((CurPos + 1) != tok::Identifier) { 
        check(tok::Identifier); 
      } 
      // Сам идентификатор будет разобран в parsePostfixExpr, здесь 
      // нам нужно только указать, что это глобальная область
      // видимости 
      return new IdExprAST(CurPos.getLocation(), nullptr); 
      ...
  } 
} 

Так же необходимо добавить поддержку новых постфиксных операторов, такие как индексация в массиве и доступ к члену структуры:

Hidden text

/// call-arguments 
///   ::= assign-expr 
///   ::= call-arguments ',' assign-expr 
/// postfix-expr 
///   ::= primary-expr 
///   ::= postfix-expr '++' 
///   ::= postfix-expr '--' 
///   ::= postfix-expr '(' call-arguments ? ')' 
///   ::= postfix-expr '[' expr ']' 
///   ::= postfix-expr '.' identifier 
ExprAST *Parser::parsePostfixExpr() { 
  ExprAST *result = parsePrimaryExpr(); 

  for (;;) { 
    llvm::SMLoc loc = CurPos.getLocation(); 

    switch (int op = CurPos->getKind()) { 
      ...
      case tok::OpenBrace: { 
        // Это индексация элемента в массиве. Пропускаем [ 
        check(tok::OpenBrace); 
        // Считываем выражение
        ExprAST *expr = parseExpr(); 
        // Проверяем на наличие ]
        check(tok::CloseBrace); 
        // Создаем ветку дерева
        result = new IndexExprAST(loc, result, expr); 
        continue; 
      } 

      case tok::Dot: { 
        // Это обращение к члену структуры или класса, их может
        // несколько, поэтому обрабатываем их в цикле
        while (CurPos == tok::Dot) { 
          // Пропускаем .
          ++CurPos; 

          Name *name = nullptr; 
          // Если это идентификатор, то сохраняем его
          if (CurPos == tok::Identifier) { 
            name = CurPos->getIdentifier(); 
          } 
          // Считываем идентификатор или диагностируем об ошибке
          check(tok::Identifier); 
          // Создаем ветку дерева
          result = new MemberAccessExprAST(loc, result, name); 
        } 

        continue; 
      } 

      default: 
        return result; 
    } 
  } 
} 

В синтаксическом анализе выражений с одним операндом нам нужно добавить поддержку новых операторов, такие как: взятие адреса, разыменование указателей, а так же выделение и освобождение блока памяти:

Hidden text

/// unary-expr 
///   ::= postfix-expr 
///   ::= '+' unary-expr 
///   ::= '-' unary-expr 
///   ::= '++' unary-expr 
///   ::= '--' unary-expr 
///   ::= '~' unary-expr 
///   ::= '!' unary-expr 
///   ::= '*' unary-expr 
///   ::= '&' unary-expr 
///   ::= 'del' unary-expr 
///   ::= 'new' type ('[' assign-expr ']')? 
ExprAST *Parser::parseUnaryExpr() { 
  ExprAST *result = nullptr; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (int op = CurPos->getKind()) { 
    ...
    case tok::Mul: 
      // Это разыменование указателя. Пропускаем "*" и считываем 
      // следующее выражение с одним операндом
      ++CurPos; 
      result = parseUnaryExpr(); 
      // Создаем ветку дерева
      return new DerefExprAST(loc, result); 

    case tok::BitAnd: 
      // Это операция взятия адреса. Пропускаем "&" и считываем 
      // следующее выражение с одним операндом
      ++CurPos; 
      result = parseUnaryExpr(); 
      // Создаем ветку дерева
      return new AddressOfExprAST(loc, result); 

    case tok::Delete: { 
      // Это операция освобождения памяти. Пропускаем "del" и 
      // считываем следующее выражение с одним операндом
      ++CurPos; 
      result = parsePostfixExpr(); 
      // Создаем ветку дерева
      return new DeleteExprAST(loc, result); 
    } 

    case tok::New: { 
      // Это операция выделения памяти. Пропускаем "new"
      ++CurPos; 
      // Считываем тип
      TypeAST *type = parseType(); 
      ExprList args; 
      ExprAST *dynamicSize = nullptr; 

      // Проверяем "[" expression "]" , т.к. "[" integral-literal "]"
      // может быть обработано ранее в parseType 
      if (CurPos == tok::OpenBrace) { 
        // Проверяем, что слева от "[" у нас нету структуры или 
        // класса, т. к. мы их не поддерживаем
        if (isa<QualifiedTypeAST>(type)) { 
          getDiagnostics().report(CurPos.getLocation(), 
                                  diag::ERR_DynArrayAggregate); 
        } 
        // Пропускаем "[" и считываем выражение между "[" и "]"
        ++CurPos; 
        dynamicSize = parseAssignExpr(); 
        // Проверяем наличие "]"
        check(tok::CloseBrace); 
      } 
      // Создаем ветку дерева
      return new NewExprAST(loc, type, dynamicSize, args); 
    } 

    default: 
      return parsePostfixExpr(); 
  } 
} 

Так же нужно добавить поддержку новых типов в объявлениях:

Hidden text

/// basic-type 
///  ::= 'int' 
///  ::= 'float' 
///  ::= 'void' 
///  ::= 'char' 
///  ::= 'string' 
///  ::= '.'? identifier ('.' identifier)* 
/// type 
///   ::= basic-type 
///   ::= type '*' 
///   ::= type '[' integral-literal ']' 
TypeAST *Parser::parseType() { 
  TypeAST *type = nullptr; 
  bool isVoid = false; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (CurPos->getKind()) { 
    ...

    case tok::Char: 
      // "char"
      ++CurPos; 
      type = BuiltinTypeAST::get(TypeAST::TI_Char); 
      break; 

    case tok::String: 
      // "string"
      ++CurPos; 
      type = BuiltinTypeAST::get(TypeAST::TI_String); 
      break; 

    case tok::Dot: 
    case tok::Identifier: { 
      // Это должно быть полное имя, например A.B или .A
      Name *name = nullptr; 
      QualifiedName qualName; 

      if (CurPos == tok::Identifier) { 
        // Сохраняем идентификатор, если это был он (т. к. могла 
        // быть ".")
        name = CurPos->getIdentifier(); 
        ++CurPos; 
      } 
      // Добавляем ранее считанный идентификатор или "." в список
      qualName.push_back(name); 
      // Полный идентификатор может состоять из серии 
      // идентификаторов разделенных ".". Считываем их все
      while (CurPos == tok::Dot) { 
        ++CurPos; 

        // Сохраняем идентификатор для последующего использования
        if (CurPos == tok::Identifier) { 
          name = CurPos->getIdentifier(); 
        } 
        // Проверяем, что мы встретили идентификатор и переходим к 
        // следующему токену
        check(tok::Identifier); 
        // Добавляем идентификатор к полному имени
        qualName.push_back(name); 
      } 
      // Создаем ветку дерева
      type = new QualifiedTypeAST(qualName); 
      break; 
    } 

    default: 
      getDiagnostics().report(CurPos.getLocation(), 
                              diag::ERR_InvalidType); 
      return nullptr; 
  } 
  // После простого типа мы можем иметь составные типы
  for (;;) { 
    switch (CurPos->getKind()) { 
      case tok::OpenBrace: { 
        // Это "[", но исключаем вариант с "void["
        if (isVoid) { 
          getDiagnostics().report(loc, diag::ERR_VoidAsNonPointer); 
          return nullptr; 
        } 
        // Пропускаем "["
        ++CurPos; 

        int dim = 0; 

        if (CurPos == tok::IntNumber) { 
          // Это обычный целочисленный литерал. Сохраняем его 
          // значение
          dim = atoi(CurPos->getLiteral().data()); 
        } else { 
          // Считаем, что это "[" expression "]", которое может быть 
          // считано позже или выдана ошибка. Поэтому мы 
          // возвращаемся к предыдущему токену и завершаем разбор
          // типа 
          --CurPos; 
          break; 
        } 
       // Считываем integral-literal и "]"
        check(tok::IntNumber); 
        check(tok::CloseBrace); 
       // Создаем ветку дерева
        type = new ArrayTypeAST(type, dim); 
        continue; 
      } 

      case tok::Mul: 
        // Это указатель. Переходим к следующему токену и создаем 
        // ветку дерева
        ++CurPos; 
        type = new PointerTypeAST(type, false); 
        continue; 

      default: 
        break; 
    } 
 
    break; 
  } 

  if (type == BuiltinTypeAST::get(TypeAST::TI_Void)) { 
    getDiagnostics().report(loc, diag::ERR_VoidAsNonPointer); 
    return nullptr; 
  } 

  return type; 
} 

В разборе прототипа функции нам нужно добавить поддержку двух специальных функций "new" и "del" (на данный момент они будут использоваться только для системных функций, но в дальнейшем их использование будет расширено):

Hidden text

/// parameter ::= identifier ':' type 
/// parameters-list 
///   ::= parameter 
///   ::= parameter-list ',' parameter 
/// return-type ::= ':' type 
/// func-proto
///   ::= identifier '(' parameters-list ? ')' return-type ? 
SymbolAST *Parser::parseFuncProto() { 
  Name *name = nullptr; 
  TypeAST *returnType = BuiltinTypeAST::get(TypeAST::TI_Void); 
  ParameterList params; 
  int Tok = CurPos->getKind(); 
  llvm::SMLoc loc = CurPos.getLocation(); 
  // При вызове этой функции текущий токен всегда "fn" (в дальнейшем 
  // этот список будет расширен)
  ++CurPos; 

  // После ключевого слова объявления функции всегда должен быть 
  // идентификатор
  if (CurPos == tok::Identifier) { 
    // Сохраняем имя функции для ее прототипа и переходим к 
    // следующему токену
    name = CurPos->getIdentifier(); 
    ++CurPos; 
  // Специальная обработка для "new" в качестве имени функции
  } else if (CurPos == tok::New) { 
    ++CurPos; 
    name = Name::New; 
  // Специальная обработка для "del" в качестве имени функции
  } else if (CurPos == tok::Delete) { 
    ++CurPos; 
    name = Name::Delete; 
  } else { 
    check(tok::Identifier); 
  } 

  ...
} 

В объявлениях мы должны добавить поддержку структур:

Hidden text

/// decls 
///  ::= func-decl 
///  ::= decls func-decl 
///  ::= struct-decl 
/// 
/// struct-decl 
///   ::= 'struct' identifier '{' decl-stmt * '}' 
SymbolList Parser::parseDecls() { 
  SymbolList result; 
  // Производим анализ всех доступных объявлений
  for (;;) { 
    SymbolList tmp; 
    llvm::SMLoc loc = CurPos.getLocation(); 

    switch (int Tok = CurPos->getKind()) { 
      ...
 
      case tok::Struct: { 
        // Объявление структуры
        ++CurPos; 
        Name *name = nullptr; 

        // Сохраняем имя структуры для дальнейшего использования
        if (CurPos == tok::Identifier) { 
          name = CurPos->getIdentifier(); 
        } 

        // Проверяем наличие идентификатора и "{"
        check(tok::Identifier); 
        check(tok::BlockStart); 

        // Считываем все переменные, объявленные как ее члены
        while (CurPos != tok::BlockEnd) { 
          SymbolList tmp2 = parseDecl(true, true); 
          tmp.append(tmp2.begin(), tmp2.end()); 
        } 

        // Проверяем наличие "}" и создаем ветку дерева
        check(tok::BlockEnd); 
        result.push_back(new StructDeclAST(loc, name, tmp)); 
        continue; 
      } 

      case tok::EndOfFile: 
        break; 

      default: 
        break; 
    } 

    break; 
  } 

  return result; 
} 

В разборе объявлений переменных необходимо добавить поддержку того, что эти переменные могут быть объявлены как члены структур:

Hidden text

/// var-init ::= '=' assign-expr 
/// var-decl ::= identifier ':' type var-init? 
/// var-decls 
///   ::= var-decl 
///   ::= var-decls ',' var-decl 
/// decl-stmt ::= var-decls ';' 
SymbolList Parser::parseDecl(bool needSemicolon,
                             bool isClassMember) { 
  SymbolList result; 
  // Производим анализ списка объявлений переменных
  for (;;) { 
    llvm::SMLoc loc = CurPos.getLocation(); 

    if (CurPos != tok::Identifier) { 
      // Объявление всегда должно начинаться с идентификатора, если
      // это что-то другое, то сообщаем об ошибке
      getDiagnostics().report(CurPos.getLocation(), 
                              diag::ERR_ExpectedIdentifierInDecl); 
    } else { 
      // Сохраняем имя переменной
      Name *name = CurPos->getIdentifier(); 
      ExprAST *value = nullptr; 
      // Переходим к следующему токену
      ++CurPos; 
      // Проверяем на наличие ":"
      check(tok::Colon); 
      // Считываем тип переменной
      TypeAST *type = parseType(); 

      if (CurPos == tok::Assign) { 
        // Запрещаем инициализаторы для массивов и структур/классов
        if (isa<ArrayTypeAST>(type) || isa<QualifiedTypeAST>(type)) { 
          getDiagnostics().report(
            CurPos.getLocation(), 
            diag::ERR_AggregateOrArrayInitializer
          ); 
          return result; 
        } 

        // Если у переменной есть инициализатор, то считываем "=" и 
        // инициализирующее значение
        ++CurPos; 
        value = parseAssignExpr(); 
      } 
      // Добавляем новую переменную к списку
      result.push_back(new VarDeclAST(loc, type, name, value, 
                                      isClassMember)); 

      if (CurPos != tok::Comma) { 
        // Если это не ",", то список объявлений завершен
        break; 
      } 
      // Пропускаем ","
      ++CurPos; 
    } 
  } 

  if (needSemicolon) {
    // Если объявление должно заканчиваться ";", то проверяем его 
    // наличие 
    check(tok::Semicolon); 
  } 

  return result; 
} 

И последняя правка, которую нужно произвести это добавить поддержку новых операторов в разборе инструкций:

Hidden text

/// block-stmt ::= '{' stmt* '}' 
/// for-init 
///   ::= 'let' decl-stmt 
///   ::= expr 
/// for-stmt ::= 'for' for-init? ';' expr? ';' expr? block-stmt 
/// stmt 
///   ::= expr? ';' 
///   ::= 'let' decl-stmt 
///   ::= 'if' expr block-stmt ( 'else' block-stmt )? 
///   ::= 'while' expr block-stmt 
///   ::= for-stmt 
///   ::= 'break' 
///   ::= 'continue' 
///   ::= 'return' expr? ';' 
///   ::= block-stmt 
StmtAST *Parser::parseStmt() { 
  StmtAST *result = nullptr; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (CurPos->getKind()) { 
    ...
    case tok::Plus: 
    case tok::Minus: 
    case tok::PlusPlus: 
    case tok::MinusMinus: 
    case tok::Tilda: 
    case tok::Not: 
    case tok::Identifier: 
    case tok::IntNumber: 
    case tok::FloatNumber: 
    // Новые операторы, с которых могут начинаться выражения
    case tok::OpenParen: 
    case tok::Delete: 
    case tok::Mul: 
    case tok::BitAnd: 
    case tok::New: 
    case tok::Dot: { 
      ExprAST *expr = parseExpr(); 
      check(tok::Semicolon); 
      return new ExprStmtAST(loc, expr); 
    } 
    ...
  } 
}

Изменения в структуре AST

Для поддержки всех новых конструкций в языке для начала нужно внести некоторые правки в базовые класс корневых элементов AST. Для типов:

struct TypeAST { 
  enum TypeId { 
    TI_Void,     ///< void 
    TI_Bool,     ///< булево значение 
    TI_Int,      ///< int
    TI_Float,    ///< float 
    TI_Char,     ///< char
    TI_String,   ///< string 
    TI_Pointer,  ///< указатель 
    TI_Array,    ///< массив 
    TI_Struct,   ///< структура 
    TI_Function, ///< функция 
    TI_Qualified ///< квалифицированное имя (полное имя класса или структуры)
  }; 
  ...
  /// Проверка на то, что это тип строки
  bool isString() { 
    return TypeKind == TI_String; 
  } 
  /// Проверка на то, что это тип символа
  bool isChar() { 
    return TypeKind == TI_Char; 
  } 
  /// Проверка на то, что это тип структуры или класса
  bool isAggregate() { 
    return TypeKind == TI_Struct; 
  } 

  /// Получить SymbolAST связанный с данным типом (доступен только для
  ///   StructTypeAST) 
  virtual SymbolAST* getSymbol(); 
  ...
}; 

Для выражений:

struct ExprAST { 
  /// Expression's identifiers 
  enum ExprId { 
    EI_Int,         ///< целочисленные константы
    EI_Float,       ///< константы для чисел с плавающей точкой
    EI_Char,          ///< символьная константа
    EI_String,        ///< строковая константа
    EI_Proxy,         ///< прокси выражение
    EI_Id,          ///< использование переменной 
    EI_Cast,        ///< преобразование типов
    EI_Index,         ///< операция индексирования
    EI_MemberAccess,  ///< доступ к члену структуры или класса
    /// доступ к члену структуры или класса, если экземпляр является 
    /// указателем
    EI_PointerAccess,
    EI_Deref,         ///< разыменование указателя
    EI_AddressOf,     ///< операция взятия адреса
    EI_Unary,       ///< унарная операция
    EI_Binary,      ///< бинарная операция
    EI_Call,        ///< вызов функции
    EI_New,           ///< оператор выделение памяти
    EI_Delete,        ///< оператор очистки выделенной ранее памяти
    EI_Cond         ///< тернарный оператор 
  }; 

  ...
  /// Проверка на то, что выражение является константой 
  bool isConst() { 
    return ExprKind == EI_Int
      || ExprKind == EI_Float
      || ExprKind == EI_String; 
  } 
  /// Получить SymbolAST соответствующий агрегату
  virtual SymbolAST *getAggregate(Scope *scope); 
  /// Может ли значение быть null 
  virtual bool canBeNull(); 
  ...
}; 

И для символов (объявлений):

struct SymbolAST { 
  enum SymbolId { 
    SI_Variable,    ///< переменная
    SI_Struct,      ///< структура
    SI_Function,    ///< функция 
    SI_Module,      ///< модуль 
    SI_Parameter,   ///< параметр функции 
    SI_Block        ///< блочная декларация
  }; 
  ...
  /// Проверка на то, что символ является структурой или классом
  bool isAggregate() { 
    return SymbolKind == SI_Struct; 
  } 
  /// Проверка на то, что необходим this (true - член class/struct) 
  virtual bool needThis(); 
  /// Проверка на то, что данный символ содержит тип \c type 
  /// в качестве дочерней сущности
  /// \note Позволяет обнаружить кольцевые ссылки
  virtual bool contain(TypeAST *type); 
  /// Может ли данный символ быть null 
  /// \note Должна возвращать true только для переменных с типом указателя
  virtual bool canBeNull(); 
 ...
}; 

Дальше рассмотрим правки, которые нужно внести в описание некоторых ранее рассматриваемых веток дерева, а так же описание новых веток:

Hidden text

struct BuiltinTypeAST : TypeAST { 
  ...
  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Void || 
      T->TypeKind == TI_Bool || 
      T->TypeKind == TI_Int || 
      T->TypeKind == TI_Float || 
      T->TypeKind == TI_Char || 
      T->TypeKind == TI_String; 
  } 
  ...
}; 
 
/// Ветка дерева для типа "массив"
struct ArrayTypeAST : TypeAST { 
  ArrayTypeAST(TypeAST* next, int dim) ;

  TypeAST* semantic(Scope* scope); 
  bool implicitConvertTo(TypeAST* newType); 
  void toMangleBuffer(llvm::raw_ostream& output); 

  llvm::Type* getType(); 

  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Array; 
  } 

  TypeAST* Next; ///< базовый тип
  int Dim; ///< размер массива
}; 

/// Ветка дерева для типа "указатель"
struct PointerTypeAST : TypeAST { 
  PointerTypeAST(TypeAST* next, bool isConst) ;

  TypeAST* semantic(Scope* scope); 
  bool implicitConvertTo(TypeAST* newType); 
  void toMangleBuffer(llvm::raw_ostream& output); 

  llvm::Type* getType(); 

  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Pointer; 
  } 
 
  TypeAST* Next; ///< базовый тип
  bool IsConstant; ///< true - если значение является константой
}; 

/// Ветка дерева для типа "структура"
struct StructTypeAST : TypeAST { 
  StructTypeAST(SymbolAST* thisDecl) ;

  TypeAST* semantic(Scope* scope); 
  bool implicitConvertTo(TypeAST* newType); 
  void toMangleBuffer(llvm::raw_ostream& output); 
  SymbolAST* getSymbol(); 

  llvm::Type* getType(); 

  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Struct; 
  } 

  SymbolAST* ThisDecl; ///< объявление самой структуры
}; 

/// Квалифицированное имя
typedef llvm::SmallVector< Name*, 4 > QualifiedName; 

/// Ветка дерева для квалифицированного имени 
/// \note Вспомогательный класс, который будет заменен на тип 
/// оригинал после семантического анализа (например на 
/// StructTypeAST)
struct QualifiedTypeAST : TypeAST { 
  QualifiedTypeAST(const QualifiedName& qualName);

  TypeAST* semantic(Scope* scope); 
  bool implicitConvertTo(TypeAST* newType); 
  void toMangleBuffer(llvm::raw_ostream& output); 

  llvm::Type* getType(); 

  static bool classof(const TypeAST *T) { 
    return T->TypeKind == TI_Qualified; 
  } 

  QualifiedName QualName; ///< квалифицированное имя
}; 

/// Ветка дерева для строковой константы
struct StringExprAST : ExprAST { 
  StringExprAST(llvm::SMLoc loc, llvm::StringRef str) ;

  bool isTrue(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_String; 
  } 

  llvm::SmallString< 32 > Val; ///< хранимое значение
}; 

/// Ветка для прокси выражения
/// \note Некоторые выражения могут копировать дочерние выражения
/// во время семантического анализа. Этот класс позволяет 
/// заблокировать это поведение, путем копирования только себя, 
/// а дочернее выражение оставляет без изменений
struct ProxyExprAST : ExprAST { 
  ProxyExprAST(llvm::SMLoc loc, ExprAST *orig) ;

  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_Proxy; 
  } 

  ExprAST* OriginalExpr; ///< вложенное выражение
}; 

/// Ветка дерева для оператора "new"
struct NewExprAST : ExprAST { 
  NewExprAST(llvm::SMLoc loc, TypeAST *type, ExprAST *dynamicSize, 
    const ExprList& args) ;

  ~NewExprAST();

  bool canBeNull(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_New; 
  } 

  TypeAST* NewType; ///< тип, под который нужно выделить память
  ExprList Args; ///< аргументы для конструктора
  ExprAST* CallExpr; ///< вызов функции allocMem
  ExprAST* DynamicSize; ///< выражение с динамическим размером
  /// размер для выделения памяти одного элемента
  IntExprAST* SizeExpr;
  /// true — если необходимо произвести преобразование после 
  /// выделения памяти
  bool NeedCast;
}; 

/// Ветка дерева для оператора "del"
struct DeleteExprAST : ExprAST { 
  DeleteExprAST(llvm::SMLoc loc, ExprAST *val) ;

  ~DeleteExprAST();

  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_Delete; 
  } 

  ExprAST* Val; ///< выражение для очистки памяти
  ExprAST* DeleteCall; ///< вызов функции freeMem
}; 

struct IdExprAST : ExprAST { 
  ...
  SymbolAST* getAggregate(Scope *scope); 
  bool canBeNull(); 
  ...
}; 

/// Ветка дерева для выражения взятия индекса
struct IndexExprAST : ExprAST { 
  IndexExprAST(llvm::SMLoc loc, ExprAST *left, ExprAST *right) ;

  ~IndexExprAST();

  bool isLValue(); 
  SymbolAST* getAggregate(Scope *scope); 
  bool canBeNull(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getLValue(SLContext& Context); 
  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_Index; 
  } 

  ExprAST* Left; ///< индексируемое значение
  ExprAST* Right; ///< индекс
}; 

/// Ветка дерева для доступа к члену класса/структуры
struct MemberAccessExprAST : ExprAST { 
  MemberAccessExprAST(llvm::SMLoc loc, ExprAST *val,
                      Name *memberName) ;

  ~MemberAccessExprAST();

  bool isLValue(); 
  SymbolAST* getAggregate(Scope *scope); 
  bool canBeNull(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getLValue(SLContext& Context); 
  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_MemberAccess; 
  } 

  ExprAST* Val; ///< экземпляр класса/структуры
  Name* MemberName; ///< имя члена класса/структуры
  /// символ с объявлением члена класса/структуры
  SymbolAST* ThisSym;
  /// символ с объявлением класса/структуры 
  SymbolAST* ThisAggr; 
  bool SemaDone; ///< true — если семантический анализ был завершен
}; 

/// Ветка дерева для доступа к члену класса/структуры через
/// указатель
struct PointerAccessExprAST : ExprAST { 
  PointerAccessExprAST(llvm::SMLoc loc, 
    ExprAST *val, 
    Name *memberName) ;

  ~PointerAccessExprAST();

  bool isLValue(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getLValue(SLContext& Context); 
  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_PointerAccess; 
  } 

  ExprAST* Val; ///< экземпляр класса/структуры
  Name* MemberName; ///< имя члена класса/структуры
  /// символ с объявлением члена класса/структуры
  SymbolAST* ThisSym;
}; 

/// Ветка дерева для разыменования указателя
struct DerefExprAST : ExprAST { 
  DerefExprAST(llvm::SMLoc loc, ExprAST *val) ;

  ~DerefExprAST();

  bool isLValue(); 
  SymbolAST* getAggregate(Scope *scope); 
  bool canBeNull(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getLValue(SLContext& Context); 
  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_Deref; 
  } 

  ExprAST* Val; ///< выражение для разыменования
}; 

/// Ветка дерева для операции взятия адреса
struct AddressOfExprAST : ExprAST { 
  AddressOfExprAST(llvm::SMLoc loc, ExprAST *val) ;

  ~AddressOfExprAST();

  SymbolAST* getAggregate(Scope *scope); 
  bool canBeNull(); 
  ExprAST* semantic(Scope* scope); 
  ExprAST* clone(); 

  llvm::Value* getRValue(SLContext& Context); 

  static bool classof(const ExprAST *E) { 
    return E->ExprKind == EI_AddressOf; 
  } 

  ExprAST* Val; ///< выражение, адрес которого необходимо получить
}; 

/// Ветка для объявления переменной или члена класса/структуры
struct VarDeclAST : SymbolAST { 
  VarDeclAST(llvm::SMLoc loc, TypeAST *varType, Name *id, 
    ExprAST* value, bool inClass) ;
  ...
  bool needThis(); 
  bool canBeNull(); 
  bool contain(TypeAST* type); 
  ...
  int OffsetOf; ///< индекс поля в классе/структуре
  bool NeedThis; ///< true — если это член класса/структуры 
}; 

/// Ветка для объявления структуры
struct StructDeclAST : ScopeSymbol { 
  StructDeclAST(llvm::SMLoc loc, Name *id, 
                const SymbolList &vars) ;

  ~StructDeclAST();

  TypeAST* getType(); 
  void doSemantic(Scope* scope); 
  void doSemantic3(Scope* scope); 
  bool contain(TypeAST* type); 

  llvm::Value* generateCode(SLContext& Context); 
  llvm::Value* getValue(SLContext& Context); 

  static bool classof(const SymbolAST *T) { 
    return T->SymbolKind == SI_Struct; 
  } 

  SymbolList Vars; ///< список объявлений членов структуры
  TypeAST* ThisType; ///< тип данного объявления
}; 

/// Ветка для параметра функции
struct ParameterSymbolAST : SymbolAST { 
  ...
  bool canBeNull(); 
  ...
}; 

Изменения в семантике для AST

Рассмотрим основные семантические правила, которые добавлены в язык с появлением новых типов и операций.

1. Тип char является однобайтным целочисленным типом, который представляет собой один символ в строке;

2. Строка — является указателем типа char, с тем отличием от обычных указателей, что элементы не могут быть изменены (поэтому поддерживает ограниченный набор операций над указателями). Переменные данного типа могут быть инициализированы строковыми литералами;

3. Указатель — является адресом на начала блока памяти и поддерживает операции ++/--, индексации, +/- с целочисленной константой, а так же операцию разыменование указателя *. Переменные данного типа могут быть инициализированы значением указателя или массива совместимого типа или константой 0. Указатель на char может быть преобразован в строку;

4. Массивы — блок памяти определенного размера, состоящих из элементов одного и того же типа. Поддерживают только операцию индексирования. Не могут иметь инициализаторов. Массив char может быть преобразован в строку. Данный тип не может быть использован в качестве возвращаемого значения для функции;

5. Структуры — именованный тип содержащий набор полей различных типов. Поддерживает только операцию обращения к собственным полям. Данный тип не может быть использован в качестве параметра и возвращаемого значения для функции. Также структуры не могут иметь циклические ссылки (за исключением случая циклических ссылок через указатели);

6. Операция обращения к полям структуры может применяться к переменным с типом указателям на структуру без дополнительного разыменования указателя;

7. Массивы могут быть преобразованы к указателям, если они имеют общий базовый тип;

8. Операция взятия адреса может быть применена только к lvalue значениям;

9. Операции new и del могут быть использованы для выделения и очистки блоков памяти.

Далее рассмотрим изменения в семантики более подробно.

Семантика типов:

Hidden text

SymbolAST* TypeAST::getSymbol() {
  return nullptr;
}

TypeAST *BuiltinTypeAST::get(int type) {
  static TypeAST *builtinTypes[] = {
    new BuiltinTypeAST(TI_Void),
    new BuiltinTypeAST(TI_Bool),
    new BuiltinTypeAST(TI_Int),
    new BuiltinTypeAST(TI_Float),
    new BuiltinTypeAST(TI_Char),
    new BuiltinTypeAST(TI_String)
  };

  assert(type >= TI_Void && type <= TI_String);
  return builtinTypes[type];
}

bool BuiltinTypeAST::implicitConvertTo(TypeAST* newType) {
  // Список разрешенных преобразований
  static bool convertResults[TI_String + 1][TI_String + 1] = {
    // void  bool   int    float  char   string
    { false, false, false, false, false, false }, // void
    { false, true,  true,  true,  true,  false }, // bool
    { false, true,  true,  true,  true,  false }, // int
    { false, true,  true,  true,  false, false }, // float
    { false, true,  true,  true,  true,  false }, // char
    { false, true,  false, false, false, true  }  // string
  };
  // Только базовые типы могут быть преобразованы друг в друга
  if (newType->TypeKind > TI_String) {
    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;
    case TI_Char : output << "c"; break;
    case TI_String : output << "PKc"; break;
    default: assert(0 && "Should never happen"); break;
  }
}

TypeAST* ArrayTypeAST::semantic(Scope* scope) {
  // Проверить семантику базового типа
  Next = Next->semantic(scope);
  // создаем MangleName
  calcMangle();
  return this;
}

bool ArrayTypeAST::implicitConvertTo(TypeAST* newType) {
  TypeAST* next1 = Next;
  TypeAST* next2 = nullptr;

  // char[] можно преобразовать в string
  if (Next->isChar() && newType->isString()) {
    return true;
  }

  // Если newType не массив или указатель, то мы запрещаем 
  // преобразование
  if (!(isa<PointerTypeAST>(newType)
        || isa<ArrayTypeAST>(newType))) {
    return false;
  }

  // Получаем базовый тип для указателей или массивов
  if (isa<PointerTypeAST>(newType)) {
    next2 = ((PointerTypeAST*)newType)->Next;
  } else if (isa<ArrayTypeAST>(newType)) {
    ArrayTypeAST* arrayType = (ArrayTypeAST*)newType;

    // Для массивов нужно проверить еще и размеры
    if (arrayType->Dim != Dim) {
      return false;
    }

    next2 = arrayType->Next;
  }

  // Разрешаем преобразование любого массива в void*
  if (next2->isVoid()) {
    return true;
  }

  // Допустимы только преобразования самого верхнего уровня
  return next1->equal(next2);
}

void ArrayTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
  output << "A" << Dim << "_";
  Next->toMangleBuffer(output);
}

TypeAST* PointerTypeAST::semantic(Scope* scope) {
  // Проверить семантику базового типа
  Next = Next->semantic(scope);
  // создаем MangleName
  calcMangle();
  return this;
}

bool PointerTypeAST::implicitConvertTo(TypeAST* newType) {
  // Разрешаем преобразование указателя в bool
  if (newType->isBool()) {
    return true;
  }
  
  // Разрешаем преобразование char* в string
  if (Next->isChar() && newType->isString()) {
    return true;
  }
  
  // Запрещаем любое преобразование в тип отличный от указателя
  if (!isa<PointerTypeAST>(newType)) {
    return false;
  }

  PointerTypeAST* ptr2 = (PointerTypeAST*)newType;
  // Получаем базовый тип для newType
  TypeAST* next2 = ptr2->Next;

  // Разрешаем преобразование, если типы совпадают
  if (Next->equal(next2)) {
    return true;
  }

  TypeAST* next1 = Next;

  // Разрешаем преобразование указателя любого типа в void*
  if (next2->isVoid()) {
    return true;
  }

  return false;
}

void PointerTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
  output << "P";
  Next->toMangleBuffer(output);
}

void mangleAggregateName(llvm::raw_ostream& output,
                         SymbolAST* thisSym) {
  assert(thisSym && thisSym->isAggregate());
  SymbolAST* sym = thisSym;

  output << "N";

  // Создаем строку вида N Длина Имя E для классов/структур или 
  // N Длина1 Имя1 Длина2 Имя2 E для вложенных классов/структур
  // Например:
  //   A.B.C будет N1A1B1CE
  //   A будет N1AE

  for ( ; ; ) {
    if (!sym || !sym->isAggregate()) {
      output << "E";
      return;
    }

    output << sym->Id->Length << StringRef(sym->Id->Id,
                                           sym->Id->Length);
    sym = sym->Parent;
  }
}

TypeAST* StructTypeAST::semantic(Scope* scope) {
  calcMangle();
  return this;
}

bool StructTypeAST::implicitConvertTo(TypeAST* newType) {
  return false;
}

void StructTypeAST::toMangleBuffer(llvm::raw_ostream& output) {
  mangleAggregateName(output, ThisDecl);
}

SymbolAST* StructTypeAST::getSymbol() {
  return ThisDecl;
}

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

    // Запрещаем использовать классы и структуры в качестве 
    // параметров функции 
    if ((*it)->Param->isAggregate()) {
      scope->report(SMLoc(),
                    diag::ERR_SemaAggregateAsFunctionParameter);
      return nullptr;
    }
  }
    
  // Запрещаем использование массивов и классов/структур в качестве
  // возвращаемого значения функций
  if (ReturnType && (ReturnType->isAggregate()
                     || isa<ArrayTypeAST>(ReturnType))) {
    scope->report(SMLoc(),
                  diag::ERR_SemaArrayOrAggregateAsReturnType);
    return nullptr;
  }

  calcMangle();
  return this;
}

TypeAST* QualifiedTypeAST::semantic(Scope* scope) {
  SymbolAST* sym = nullptr;
  
  // Мы должны найти объявление по полному имени
  for (QualifiedName::iterator it = QualName.begin(),
       end = QualName.end(); it != end; ++it) {

    if (sym) {
      // Ищем символ в качестве дочернего
      sym = sym->find((*it));

      if (!sym) {
        scope->report(SMLoc(), diag::ERR_SemaUndefinedIdentifier, 
                      (*it)->Id);
        return nullptr;
      }
    } else {
      // Ищем имя в текущей области видимости
      sym = scope->find((*it));

      if (!sym) {
        scope->report(SMLoc(), diag::ERR_SemaUndefinedIdentifier, 
                      (*it)->Id);
        return nullptr;
      }
    }
  }

  // Возвращаем тип найденного символа
  return sym->getType();
}

bool QualifiedTypeAST::implicitConvertTo(TypeAST* ) {
  assert(0 && "QualifiedTypeAST::implicitConvertTo should never "
         " be reached");
  return false;
}

void QualifiedTypeAST::toMangleBuffer(llvm::raw_ostream& ) {
  assert(0 && "QualifiedTypeAST::toMangleBuffer should never be "
         "reached");
}

Семантика выражений:

Hidden text

SymbolAST* ExprAST::getAggregate(Scope *) {
  assert(0 && "ExprAST::getAggregaet should never be reached");
  return nullptr;
}

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

bool StringExprAST::isTrue() {
  return true;
}

ExprAST* StringExprAST::semantic(Scope* ) {
  return this;
}

ExprAST* StringExprAST::clone() {
  return new StringExprAST(Loc, StringRef(Val));
}

ExprAST* ProxyExprAST::semantic(Scope* scope) {
  // Проверяем, что было использовано для выражения, которое не 
  // заменяет себя после семантического анализа
  ExprAST* tmp = OriginalExpr->semantic(scope);
  assert(tmp == OriginalExpr);
  ExprType = OriginalExpr->ExprType;
  return this;
}

ExprAST* ProxyExprAST::clone() {
  return new ProxyExprAST(Loc, OriginalExpr);
}

bool NewExprAST::canBeNull() {
  return true;
}

ExprAST* NewExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (ExprType) {
    return this;
  }

  // Производим семантический анализ для типа
  NewType = NewType->semantic(scope);

  // Проверяем на то, что это массив с фиксированным размером
  if (isa<ArrayTypeAST>(NewType) && !DynamicSize) {
    // Мы выделяем память как для массива, но результирующий тип 
    // будет указателем
    ArrayTypeAST* arrayType = (ArrayTypeAST*)NewType;
    ExprType = new PointerTypeAST(arrayType->Next, false);
    ExprType = ExprType->semantic(scope);
  } else {
    // Результирующий тип будет указателем
    ExprType = new PointerTypeAST(NewType, false);
    ExprType = ExprType->semantic(scope);
  }

  // Создаем новое выражение для хранения размера NewType на 
  // целевой платформе и оборачиваем его в прокси, т. к. 
  // реальный размер будет известен только во время генерации кода
  SizeExpr = new IntExprAST(Loc, 0);
  ExprAST* proxy = new ProxyExprAST(Loc, SizeExpr);

  // Для массивов с динамическим размером, мы должны посчитать
  // актуальный размер
  if (DynamicSize) {
    proxy = new BinaryExprAST(Loc, tok::Mul, DynamicSize, proxy);
  }

  // Создаем вызов функции allocMem для выделения блока памяти
  // нужного размера
  ExprList args;
  args.push_back(proxy);
  CallExpr = new CallExprAST(Loc, new IdExprAST(Loc, Name::New),
                             args);

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

  return this;
}

ExprAST* NewExprAST::clone() {
  ExprList exprs;
  ExprList::iterator it = Args.begin();
  ExprList::iterator end = Args.end();

  // Делаем клонирование всех аргументов (если они есть)
  for ( ; it != end; ++it) {
    exprs.push_back((*it)->clone());
  }

  return new NewExprAST(Loc, NewType, DynamicSize, exprs);
}

ExprAST* DeleteExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (DeleteCall) {
    return this;
  }

  // Производим семантический анализ выражения для очистки
  Val = Val->semantic(scope);

  // Запрещаем удаление выражений с типом void
  if (!Val->ExprType || Val->ExprType->isVoid()) {
    scope->report(Loc, diag::ERR_SemaCantDeleteVoid);
    return nullptr;
  }

  // Мы можем производить очистку только для указателей
  if (!isa<PointerTypeAST>(Val->ExprType)) {
    scope->report(Loc, diag::ERR_SemaCantDeleteNonPointer);
    return nullptr;
  }

  PointerTypeAST* ptrType = (PointerTypeAST*)Val->ExprType;

  ExprAST* deleteArg = Val->clone();
  ExprList args;

  // Создаем список аргументов для вызова freeMem
  // Замечание: Это может быть либо Val, либо результат вызова 
  // деструктора
  args.push_back(deleteArg);
  
  // Создание вызова freeMem и проверка его семантики
  DeleteCall = new CallExprAST(
    Loc,
    new IdExprAST(Loc, Name::Delete),
    args
  );
  DeleteCall = DeleteCall->semantic(scope);
  // Результат операции будет void
  ExprType = BuiltinTypeAST::get(TypeAST::TI_Void);

  return this;
}

ExprAST* DeleteExprAST::clone() {
  return new DeleteExprAST(Loc, Val->clone());
}

bool IdExprAST::isLValue() {
  // Исключаем неизменяемые указатели, т. к. мы их не можем 
  // изменить
  if (isa<PointerTypeAST>(ExprType)) {
    return !((PointerTypeAST*)ExprType)->IsConstant;
  }

  return true;
}

SymbolAST* IdExprAST::getAggregate(Scope *) {
  return ThisSym;
}

bool IdExprAST::canBeNull() {
  return ThisSym->canBeNull();
}

bool IndexExprAST::isLValue() {
  // Мы не можем изменять строки
  if (Left->ExprType->isString()) {
    return false;
  }

  return true;
}

SymbolAST* IndexExprAST::getAggregate(Scope *scope) {
  // Мы не можем получить символ для агрегата, если это не 
  // структура или класс
  if (!ExprType->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaNonAggregateDotOperand);
    return nullptr;
  }
  // Возвращаем объявление выражения
  return ExprType->getSymbol();
}

bool IndexExprAST::canBeNull() {
  // Если тип результирующего выражения указатель, то он может 
  // быть null
  if (isa<PointerTypeAST>(ExprType)) {
    return true;
  }

  return false;
}

ExprAST* IndexExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (ExprType) {
    return this;
  }

  // Производим семантический анализ обоих операндов
  Left = Left->semantic(scope);
  Right = Right->semantic(scope);

  // Мы можем индексировать только массивы, указатели и строки
  if (Left->ExprType && !isa<ArrayTypeAST>(Left->ExprType)
    && !isa<PointerTypeAST>(Left->ExprType)
    && !Left->ExprType->isString()) {
    scope->report(Loc, diag::ERR_SemaNonIndexableType);
    return nullptr;
  }

  // Произвести преобразование типа индекса к int, если это 
  // необходимо
  if (!Right->ExprType->isInt()) {
    Right = new CastExprAST(
      Right->Loc,
      Right,
      BuiltinTypeAST::get(TypeAST::TI_Int)
    );
    Right = Right->semantic(scope);
  }

  // Определяем тип результата работы выражения
  if (isa<ArrayTypeAST>(Left->ExprType)) {
    ExprType = ((ArrayTypeAST*)Left->ExprType)->Next;
  } else if (isa<PointerTypeAST>(Left->ExprType)) {
    ExprType = ((PointerTypeAST*)Left->ExprType)->Next;
  } else {
    ExprType = BuiltinTypeAST::get(TypeAST::TI_Char);
  }

  return this;
}

ExprAST* IndexExprAST::clone() {
  return new IndexExprAST(Loc, Left->clone(), Right->clone());
}

bool MemberAccessExprAST::isLValue() {
  return true;
}

SymbolAST* MemberAccessExprAST::getAggregate(Scope *) {
  return ThisSym;
}

bool MemberAccessExprAST::canBeNull() {
  return Val->canBeNull();
}

ExprAST* MemberAccessExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (SemaDone) {
    return this;
  }

  // Проверяем семантику левого операнда
  Val = Val->semantic(scope);

  // Специальная обработка для символа в глобальной области 
  // видимости
  if (isa<IdExprAST>(Val) && !((IdExprAST*)Val)->Val) {
    // Получить объявление модуля
    SymbolAST* moduleSym = scope->find(0);
    assert(moduleSym);
    // Поиск объявления в модуле
    SymbolAST* thisSym = moduleSym->find(MemberName);

    // Диагностика ошибки, если символ не найден
    if (!thisSym) {
      scope->report(Loc, diag::ERR_SemaUndefinedMember,
                    MemberName->Id);
      return nullptr;
    }

    // Заменяем MemberAccessExprAST на IdExprAST с предопределенными
    // значениями
    IdExprAST* newExpr = new IdExprAST(Loc, MemberName);

    newExpr->ExprType = thisSym->getType();

    newExpr->ThisSym = thisSym;
    delete this;
    return newExpr;
  }
  
  // Проверяем на корректность типа операнда
  if (!Val->ExprType) {
    scope->report(Loc, diag::ERR_SemaInvalidOperandForMemberAccess);
    return nullptr;
  }

  // Если Val является указателем на агрегат, то нам нужно 
  // произвести разыменование указателя. Т.е. в семантики C++,
  // мы считаем agg->a эквивалентом (*agg).a
  if (isa<PointerTypeAST>(Val->ExprType) && 
    ((PointerTypeAST*)Val->ExprType)->Next->isAggregate()) {
    // Создание разыменования указателя и проверка его семантики
    Val = new DerefExprAST(Loc, Val);
    Val = Val->semantic(scope);
  }

  // Val должно быть lvalue
  if (!Val->isLValue()) {
    scope->report(Loc, diag::ERR_SemaNonLValueForMemberAccess);
    return nullptr;
  }

  // Получить агрегат
  SymbolAST* aggSym = Val->getAggregate(scope);

  // Запрещаем использование A.b, где A — класс или структура. 
  // Это должно быть a.b, где a экземпляр A
  if (isa<IdExprAST>(Val) && aggSym && aggSym->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaMemberAccessOnAggregateType);
    return nullptr;
  }
  
  // Исключаем операции над не агрегатами
  if (!aggSym || !aggSym->getType()->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaNonAggregateDotOperand);
    return nullptr;
  }

  // Получить объявление агрегата
  if (!aggSym->isAggregate()) {
    aggSym = aggSym->getType()->getSymbol();
  }

  // Поиск символа в агрегате
  ThisSym = aggSym->find(MemberName);
  ThisAggr = aggSym;

  // Проверка на то, что данный агрегат имеет член с таким именем
  if (!ThisSym) {
    scope->report(Loc, diag::ERR_SemaUndefinedMember,
                  MemberName->Id);
    return nullptr;
  }
  
  // Запрет конструкции вида a.A, где A это агрегат
  if (ThisSym->isAggregate()) {
    scope->report(Loc,
                  diag::ERR_SemaAggregateTypeAsMemberAccessOperand);
    return nullptr;
  }

  // Установка типа результата операции
  ExprType = ThisSym->getType();
  SemaDone = true;

  return this;
}

ExprAST* MemberAccessExprAST::clone() {
  return new MemberAccessExprAST(Loc, Val->clone(), MemberName);
}

bool PointerAccessExprAST::isLValue() {
  return true;
}

ExprAST* PointerAccessExprAST::semantic(Scope* scope) {
  // Переписываем expr->member в виде (*expr).member, производим 
  // семантический анализ и удаляем старое выражение 
  ExprAST* newExpr = new DerefExprAST(Loc, Val);
  newExpr = new MemberAccessExprAST(Loc, newExpr, MemberName);
  Val = nullptr;
  delete this;
  return newExpr->semantic(scope);
}

ExprAST* PointerAccessExprAST::clone() {
  return new PointerAccessExprAST(Loc, Val->clone(), MemberName);
}

bool DerefExprAST::isLValue() {
  return true;
}

SymbolAST* DerefExprAST::getAggregate(Scope *scope) {
  // Мы не можем получить символ для агрегата, если это не 
  // структура или класс
  if (!ExprType->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaNonAggregateDotOperand);
    return nullptr;
  }
  // Возвращаем объявление выражения
  return ExprType->getSymbol();
}

bool DerefExprAST::canBeNull() {
  return true;
}

ExprAST* DerefExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (ExprType) {
    return this;
  }

  // Проверяем семантику операнда
  Val = Val->semantic(scope);

  // Проверяем, что это операция взятия адреса
  if (isa<AddressOfExprAST>(Val)) {
    // Удаляем * и &
    ExprAST* result = ((AddressOfExprAST*)Val)->Val->clone();
    delete this;
    return result->semantic(scope);
  }

  // Проверяем на корректность типов
  if (Val->ExprType) {
    // Специальный случай для строк
    if (Val->ExprType->isString()) {
      // Запрет разыменования константных строк
      if (Val->isConst()) {
        scope->report(Loc, diag::ERR_SemaConstStringDeRef);
        return nullptr;
      }
      // Устанавливаем тип результата операции, как char
      ExprType = BuiltinTypeAST::get(TypeAST::TI_Char);
      return this;
    // Запрещаем работу с не указателями
    } else if (!isa<PointerTypeAST>(Val->ExprType)) {
      scope->report(Loc, diag::ERR_SemaUnDereferencableType);
      return nullptr;
    }
  } else {
    scope->report(Loc, diag::ERR_SemaUnDereferencableType);
    return nullptr;
  }
  // Установка типа для результата операции
  ExprType = ((PointerTypeAST*)Val->ExprType)->Next;
  return this;
}

ExprAST* DerefExprAST::clone() {
  return new DerefExprAST(Loc, Val->clone());
}

SymbolAST* AddressOfExprAST::getAggregate(Scope *scope) {
  return Val->getAggregate(scope);
}

bool AddressOfExprAST::canBeNull() {
  // Специальная проверка для идентификаторов
  if (isa<IdExprAST>(Val) && !Val->canBeNull()) {
    return false;
  }

  return true;
}

ExprAST* AddressOfExprAST::semantic(Scope* scope) {
  // Исключаем повторный запуск семантического анализа
  if (ExprType) {
    return this;
  }

  // Проверяем семантику для операнда
  Val = Val->semantic(scope);

  // Проверяем корректность типа операнда
  if (!Val->ExprType) {
    scope->report(Loc, diag::ERR_SemaAddressExpressionNoType);
    return nullptr;
  }

  // Проверяем на разыменование
  if (isa<DerefExprAST>(Val)) {
    // Удаляем & и *
    ExprAST* result = ((DerefExprAST*)Val)->Val->clone();
    delete this;
    return result->semantic(scope);
  }

  // Мы можем взять адрес только у lvalue
  if (!Val->isLValue()) {
    scope->report(Loc, diag::ERR_SemaAddressOfNonLValue);
    return nullptr;
  }

  // Тип выражения будет указателем на тип операнда
  ExprType = new PointerTypeAST(Val->ExprType, false);
  ExprType = ExprType->semantic(scope);

  return this;
}

ExprAST* AddressOfExprAST::clone() {
  return new AddressOfExprAST(Loc, Val->clone());
}

ExprAST* CastExprAST::semantic(Scope* scope) {
  ...

  // Запрещаем преобразование в массив
  if (isa<ArrayTypeAST>(ExprType)) {
    scope->report(Loc, diag::ERR_SemaArrayInCast);
    return nullptr;
  }

  // Проверяем на указатель и их совместимость
  if (isa<PointerTypeAST>(ExprType) && 
    !Val->ExprType->implicitConvertTo(ExprType)) {
    scope->report(Loc, diag::ERR_SemaIncompatiblePointerTypes);
    return nullptr;
  }

  // Проверяем, что типы совместимы
  if (!Val->ExprType->implicitConvertTo(ExprType)) {
    scope->report(Loc, diag::ERR_SemaInvalidCast);
    return nullptr;
  }

  SemaDone = true;
  return this;
}

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->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaAggregateAsExpression);
    return nullptr;
  }

  // Для строк разрешаем только ++/--
  if (Val->ExprType->isString() && (Op != tok::MinusMinus 
                                    && Op != tok::PlusPlus)) {
    scope->report(Loc,
                  diag::ERR_SemaInvalidUnaryExpressionForString);
    return nullptr;
  }

  // Запрещаем операции над массивами
  if (isa<ArrayTypeAST>(Val->ExprType)) {
    scope->report(Loc,
                  diag::ERR_SemaInvalidUnaryExpressionForArray);
    return nullptr;
  }

  // Для указателей разрешаем только ++/--
  if (isa<PointerTypeAST>(Val->ExprType) 
    && (Op != tok::MinusMinus && Op != tok::PlusPlus)) {
    scope->report(Loc,
                  diag::ERR_SemaInvalidUnaryExpressionForPointer);
    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:
      if ((!Val->ExprType->isInt() 
        && !isa<PointerTypeAST>(Val->ExprType)
        && !Val->ExprType->isString()) || !Val->isLValue()) {
        scope->report(Loc, 
                      diag::ERR_SemaInvalidPostfixPrefixOperand);
        return nullptr;
      } else {
        // Специальная обработка для IndexExprAST и MemberAccessAST 
        // и строк
        if (isa<IndexExprAST>(Val) || isa<MemberAccessExprAST>(Val)
          || Val->ExprType->isString()) {
          ExprType = Val->ExprType;
          return this;
        }
        // Специальная обработка для указателей
        if (isa<PointerTypeAST>(Val->ExprType)) {
          // Заменяем ++ ptr или -- ptr на ptr = &ptr[1] или 
          // ptr = &ptr[-1]
          ExprAST* val = Val;
          ExprAST* valCopy = Val->clone();
          result = new BinaryExprAST(
            Val->Loc,
            tok::Assign,
            val,
            new AddressOfExprAST(
              Val->Loc,
              new IndexExprAST(
                Val->Loc,
                valCopy, 
                new IntExprAST(
                  Val->Loc,
                  (Op == tok::PlusPlus) ? 1 : -1
                )
              )
            )
          );
        } else {
          // Необходимо заменить "++" id или "--" id на id = id + 1 
          // or 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* BinaryExprAST::semantic(Scope* scope) {
  // Семантический анализ уже был произведен ранее
  if (ExprType) {
    return this;
  }

  // Производим семантический анализ операнда с левой стороны
  LeftExpr = LeftExpr->semantic(scope);

  // Проверяем на "++" или "--", т. к. эти операции имеют только 
  // один операнд
  if (Op == tok::PlusPlus || Op == tok::MinusMinus) {
    // Проверка на корректности типов для операнда ++/--
    if (!LeftExpr->isLValue() || (!LeftExpr->ExprType->isInt()
      && !isa<PointerTypeAST>(LeftExpr->ExprType)
      && !LeftExpr->ExprType->isString())) {
      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 (LeftExpr->ExprType->isAggregate()
      || RightExpr->ExprType->isAggregate()) {
    scope->report(Loc, diag::ERR_SemaAggregateAsExpression);
    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:
      // Запрет использование строк, указателей и массивов в 
      // качестве операндов для операций сравнения
      if (LeftExpr->ExprType->isString()
        || isa<PointerTypeAST>(LeftExpr->ExprType)
        || isa<ArrayTypeAST>(LeftExpr->ExprType)
        || RightExpr->ExprType->isString()
        || isa<PointerTypeAST>(RightExpr->ExprType)
        || isa<ArrayTypeAST>(RightExpr->ExprType)) {
        scope->report(Loc, diag::ERR_SemaInvalidTypeForComparison);
        return nullptr;
      }

      // Если левый операнд "bool", то сначала конвертируем его в 
      // "int"
      if (LeftExpr->ExprType->isBool()) {
        LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr, 
          BuiltinTypeAST::get(TypeAST::TI_Int));
        LeftExpr = LeftExpr->semantic(scope);
      }

      // Если левый операнд имеет тип char, то преобразовываем его
      // в int
      if (LeftExpr->ExprType->isChar()) {
        LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr, 
          BuiltinTypeAST::get(TypeAST::TI_Int));
        LeftExpr = LeftExpr->semantic(scope);
      }

      // Операнды для "<", "<=", ">", ">=", "==" и "!=" всегда 
      // должны иметь одинаковые типы, если они отличаются, то
      // нужно сделать преобразование
      if (!LeftExpr->ExprType->equal(RightExpr->ExprType)) {
        // Perform conversion
        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 (isa<PointerTypeAST>(ExprType)) {
      // Проверяем на то, что это целочисленная константа и она не 
      // равна 0
      if (RightExpr->isIntConst()
        && ((IntExprAST*)RightExpr)->Val != 0) {
        scope->report(Loc, diag::ERR_SemaPointerInitialization);
        return nullptr;
      // Проверяем, что операнды совместимы по типам
      } else if (!RightExpr->ExprType->implicitConvertTo(
        ExprType)) {
        scope->report(Loc, diag::ERR_SemaPointerInitialization);
        return nullptr;
      } else {
        // Производим преобразование
        RightExpr = new CastExprAST(
          RightExpr->Loc, 
          RightExpr, 
          LeftExpr->ExprType
        );
        RightExpr = RightExpr->semantic(scope);
      }
    } else {
      // Если типы левого и правого операнда отличаются, то нужно 
      // сделать преобразование
      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 (isa<ArrayTypeAST>(LeftExpr->ExprType) 
    || isa<ArrayTypeAST>(RightExpr->ExprType)) {
    scope->report(Loc, 
                  diag::ERR_SemaCantUseArrayInBinaryExpression);
    return nullptr;
  }

  // Для указателей и строк мы можем использовать только 
  // определенный набор операций
  if (isa<PointerTypeAST>(LeftExpr->ExprType)
    || LeftExpr->ExprType->isString()
    || isa<PointerTypeAST>(RightExpr->ExprType)
    || RightExpr->ExprType->isString()) {
    // Если это не "-" или "+", то это ошибка
    if (Op != tok::Plus && Op != tok::Minus) {
      scope->report(Loc,
        diag::ERR_SemaPointerOrStringInBinaryExpression);
      return nullptr;
    }

    // Проверяем, что левый операнд является строкой или 
    // указателем
    if (isa<PointerTypeAST>(LeftExpr->ExprType)
      || LeftExpr->ExprType->isString()) {
      // Правый операнд может быть только целочисленным выражением
      if (!RightExpr->ExprType->isInt()) {
        scope->report(Loc,
                      diag::ERR_SemaPointerArithmeticsForNonInt);
        return nullptr;
      }

      ExprType = LeftExpr->ExprType;
      return this;
    } else {
      scope->report(Loc,
                    diag::ERR_SemaPointerArithmeticsForNonInt);
      return nullptr;
    }
  }

  // Если левый операнд имеет тип char то преобразуем его в int
  if (LeftExpr->ExprType->isChar()) {
    LeftExpr = new CastExprAST(LeftExpr->Loc, LeftExpr, 
      BuiltinTypeAST::get(TypeAST::TI_Int));
    LeftExpr = LeftExpr->semantic(scope);
    ExprType = LeftExpr->ExprType;
  }

  // Если операнды имеют различные типы, то нужно произвести 
  // преобразования
  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;
    }
  }
}

Семантика объявлений:

Hidden text

bool SymbolAST::needThis() {
  return false;
}

bool SymbolAST::canBeNull() {
  return true;
}

bool SymbolAST::contain(TypeAST* type) {
  return false;
}

bool VarDeclAST::needThis() {
  return NeedThis;
}

void VarDeclAST::doSemantic(Scope* scope) {
  // Исключаем повторные объявления переменных
  if (needThis()) {
    // Но разрешаем переопределять переменные в родителях
    if (scope->findMember(Id, 1)) {
      scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
      return;
    }
  } else {
    if (scope->find(Id)) {
      scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
      return;
    }
  }

  ...
}

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

    // Если это структура или класс, то запрещаем инициализацию
    if (ThisType->isAggregate()) {
      scope->report(Loc, diag::ERR_SemaConstructionCallInStruct);
      return;
    }

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

    // Специальная обработка для указателей
    if (isa<PointerTypeAST>(ThisType)) {
      // Выражение для инициализации имеет тип int
      if (Val->ExprType->isInt()) {
        // Разрешаем только присвоение 0
        if (Val->isIntConst() && ((IntExprAST*)Val)->Val != 0) {
          scope->report(Loc, diag::ERR_SemaPointerInitialization);
        }

        return;
      // Проверяем, что типы совместимы
      } else if (!Val->ExprType->implicitConvertTo(ThisType)) {
        scope->report(Loc, diag::ERR_SemaPointerInitialization);
        return;
      }
    }

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

bool VarDeclAST::contain(TypeAST* type) {
  // Проверяем, что типы совпадают
  if (ThisType->equal(type)) {
    return true;
  }

  return false;
}

bool VarDeclAST::canBeNull() {
  // Если это не указатель, то возвращаем false
  if (!isa<PointerTypeAST>(ThisType)) {
    return false;
  }
  // Возвращаем true, т. к. указатель может содержать значение null
  return true;
}

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

void StructDeclAST::doSemantic(Scope* scope) {
  // Запрещаем переопределение
  if (scope->find(Id)) {
    scope->report(Loc, diag::ERR_SemaIdentifierRedefinition);
    return;
  }

  // Добавляем новую область видимости
  Scope* s = scope->push(this);
  // Производим семантику объявления типа
  ThisType = ThisType->semantic(s);

  // Добавление объявления в родительскую область видимости и 
  // сохраняем объявление родителя
  ((ScopeSymbol*)scope->CurScope)->Decls[Id] = this;
  Parent = scope->CurScope;
  
  // Удаляем область видимости для данного объявления
  s->pop();
}

void StructDeclAST::doSemantic3(Scope* scope) {
  // Создаем новую область видимости
  Scope* s = scope->push(this);
  int curOffset = 0;

  // Проверка всех дочерних объявлений
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
    it != end; ++it) {
    VarDeclAST* var = (VarDeclAST*)(*it);
    
    // Производим семантическую проверку для члена структуры
    // и получаем индекс для данного члена
    var->semantic(s);
    var->OffsetOf = curOffset++;
  }

  // Проверка на наличие циклических зависимостей
  if (contain(ThisType)) {
    scope->report(Loc, diag::ERR_SemaCricularReference, Id->Id);
    return;
  }

  // Удаляем область видимости для данного объявления
  s->pop();
}

bool StructDeclAST::contain(TypeAST* type) {
  // Проверяем все переменные члены структуры на циклы
  for (SymbolList::iterator it = Vars.begin(), end = Vars.end();
   it != end; ++it) {
    if ((*it)->contain(type)) {
      return true;
    }
  }

  return false;
}

bool ParameterSymbolAST::canBeNull() {
  // Если параметр не является указателем, то возвращаем false
  if (!isa<PointerTypeAST>(Param->Param)) {
    return false;
  }
  // Возвращаем true, т. к. указатель может содержать значение null
  return true;
}

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

extern "C" void lle_X_printDouble(double val) {
  outs() << val;
}

extern "C" void lle_X_printChar(char val) {
  outs() << val;
}

extern "C" void lle_X_printString(char* str) {
  outs() << str;
}

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

extern "C" void* lle_X_new(int size) {
  return malloc(size);
}

extern "C" void lle_X_delete(void* block) {
  free(block);
}

void initRuntimeFuncs(ModuleDeclAST* modDecl) {
  addDynamicFunc(
    "fn printChar(_: char)", 
    "lle_X_printChar", 
    modDecl, 
    (void*)lle_X_printChar
  );
  addDynamicFunc(
    "fn printInt(_: int)", 
    "lle_X_printInt", 
    modDecl, 
    (void*)lle_X_printInt
  );
  addDynamicFunc(
    "fn printFloat(_: float)", 
    "lle_X_printDouble", 
    modDecl, 
    (void*)lle_X_printDouble
  );
  addDynamicFunc(
    "fn printString(_: string)", 
    "lle_X_printString",
    modDecl, 
    (void*)lle_X_printString
  );
  addDynamicFunc(
    "fn printLn(_: string)",
    "lle_X_printLine", 
    modDecl, 
    (void*)lle_X_printLine
  );
  addDynamicFunc(
    "fn new(_: int) : void*",
    "lle_X_new",
    modDecl, 
    (void*)lle_X_new
  );
  addDynamicFunc(
    "fn delete(_: void*)", 
    "lle_X_delete", 
    modDecl, 
    (void*)lle_X_delete
  );
}

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

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

  ...
}

GetElementPtr

Для того, что бы мы могли получать доступ к элементу массива или полю в структуре, в LLVM существует инструкция GetElementPtr. Она используется для получения адреса дочернего элемента составного типа. Эта инструкция производит только расчет адреса и не обращается к самой памяти.

Синтаксис этой инструкции имеет вид (ниже будет приведен только один из способов ее записи, более подробнее можно прочитать в [1]:

<result> = getelementptr <ty>, ptr <ptrval>{, [inrange] <ty> <idx>}*

Первый аргумент всегда является тип, который будет использоваться за основу при расчете. Второй всегда будет указателем или вектором указателей, который содержит базовый адрес с которого нужно произвести расчет. После чего идет список индексов, которые зависят от индексируемого типа. Первый индекс всегда индексирует значение указателя из второго аргумента, следующий индекс индексирует значение типа, на который указывают (не обязательно значение, на которое прямо указывает, т. к. первый индекс может быть отличным от 0) и т. д. Первый индексируемый тип должен быть значением указателя, последующие могут быть массивом, структурой или вектором. Но последующие индексируемые типы не могут быть указателями, т. к. для начала нужно загрузить его значение, для продолжения вычисления.

Например, для получения адреса 3 элемента в массиве %arr из 10 элементов типа i32, инструкцию GetElementPtr можно записать следующим образом:

%1 = getelementptr inbounds [10 x i32], ptr %arr, i64 0, i64 3

Если %arr является двумерным массивом 10x10, то для получения адреса 2 элемента внутри 1 элемента массива можно записать:

%1 = getelementptr inbounds [10 x [10 x i32]], ptr %arr, i64 0, i64 1, i64 2

Что также может быть записано в виде:

%1 = getelementptr inbounds [10 x [10 x i32]], ptr %arr, i64 0, i64 1
%2 = getelementptr inbounds [10 x i32], ptr %1, i64 0, i64 2

Замечание: В нашей реализации мы будем использовать более длинный вариант состоящий из 2-х инструкций.

Аналогично и со структурами. Для структуры вида %struct.C = type { i32, i32 }, получение второго поля, можно записать:

%1 = getelementptr inbounds %struct.C, ptr %c, i32 0, i32 1

Более подробно про особенности использования инструкцию можно почитать в [2], а примеры использования можно почитать в [3].

Изменения в генерации кода

Генерация кода для типов будет иметь следующий вид:

Hidden text

Type* BuiltinTypeAST::getType() {
  static Type* builtinTypes[] = {
    Type::getVoidTy(getGlobalContext()),
    Type::getInt1Ty(getGlobalContext()),
    Type::getInt32Ty(getGlobalContext()),
    Type::getDoubleTy(getGlobalContext()),
    Type::getInt8Ty(getGlobalContext()),
    PointerType::get(
      getGlobalContext(),
      getSLContext().TheTarget->getProgramAddressSpace()
    )
  };

  if (ThisType) {
    return ThisType;
  }

  return ThisType = builtinTypes[TypeKind];
}

Type* ArrayTypeAST::getType() {
  // Генерируем тип только один раз
  if (ThisType) {
    return ThisType;
  }

  // Генерируем тип для массива
  return ThisType = ArrayType::get(Next->getType(), Dim);
}

Type* PointerTypeAST::getType() {
  // Генерируем тип только один раз
  if (ThisType) {
    return ThisType;
  }

  // Генерируем тип для указателя
  return ThisType = PointerType::get(
    getGlobalContext(),
    getSLContext().TheTarget->getProgramAddressSpace()
  );
}

/// Сгенерировать строку с именем агрегата
/// \param[in] output — результат
/// \param[in] thisSym — агрегат имя которого нужно сгенерировать
/// \note Генерирует строку вида A.B.C для вложенных агрегатов
void calcAggregateName(llvm::raw_ostream& output,
                       SymbolAST* thisSym) {
  assert(thisSym && thisSym->isAggregate());
  SymbolAST* sym = thisSym;

  // Для генерируем результирующую строку для всех вложенных 
  // агрегатов
  for ( ; ; ) {
    output << StringRef(sym->Id->Id, sym->Id->Length);
    sym = sym->Parent;

    if (!sym || !sym->isAggregate()) {
      return;
    }

    output << ".";
  }
}

Type* StructTypeAST::getType() {
  // Генерируем тип только один раз
  if (ThisType) {
    return ThisType;
  }

  llvm::SmallString< 128 > s;
  llvm::raw_svector_ostream output(s);

  // Для структур имя типа всегда начинается с "struct."
  output << "struct.";
  calcAggregateName(output, ThisDecl);

  // Замечание: нужно присвоить тип агрегата сейчас, т. к. 
  // дочерние объявления могут ссылаться на саму структуру
  ThisType = StructType::create(getGlobalContext(), output.str());

  std::vector< Type* > vars;
  StructDeclAST* structDecl = (StructDeclAST*)ThisDecl;

  // Создаем список всех вложенных объявлений
  for (SymbolList::iterator it = structDecl->Vars.begin(), 
    end = structDecl->Vars.end(); it != end; ++it) {
    vars.push_back(((VarDeclAST*)(*it))->ThisType->getType());
  }

  // Если в структуре нет ни одного члена, то добавляем поле
  // размером в один байт, что бы размер типа отличался от 0
  if (vars.empty()) {
    vars.push_back(Type::getInt8Ty(getGlobalContext()));
  }

  // Установить список дочерних объявлений для структуры и вернуть
  // полученный тип
  ((StructType*)ThisType)->setBody(vars);
  return ThisType;
}

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

Генерация кода для выражений будет иметь следующий вид:

Hidden text

/// Конвертировать тип выражения в "bool"
/// \param[in] val — значение для конвертации
/// \param[in] type — тип изначального выражения
/// \param[in] builder — конструктор LLVM IR
Value* promoteToBool(Value* val, TypeAST* type,
                     IRBuilder< >& builder) {
  if (type == BuiltinTypeAST::get(TypeAST::TI_Bool)) {
    // Это уже "bool"
    return val;
  }

  if (type->isInt() || type->isChar()) {
    // Для целочисленных типов генерируем сравнение с 0
    return builder.CreateICmpNE(
      val,
      ConstantInt::get(type->getType(), 0)
    );
  } else if (isa<PointerTypeAST>(type) || type->isString()) {
    // Для указателей или строк производим сравнение с null
    return builder.CreateICmpNE(val, 
      ConstantPointerNull::get((PointerType*)type->getType()));
  } else {
    assert(type->isFloat());
    // Для числа с плавающей точкой генерируем сравнение с 0.0
    return builder.CreateFCmpUNE(val, ConstantFP::get(
      Type::getDoubleTy(getGlobalContext()), 0.0));
  }
}

Value* StringExprAST::getRValue(SLContext& Context) {
  // Создаем глобальную строку
  GlobalValue* val = Context.TheBuilder->CreateGlobalString(Val);
  std::vector< Value* > idx;

  idx.push_back(getConstInt(0));
  idx.push_back(getConstInt(0));

  // Создаем инструкцию GetElementPtr для получения адреса ранее 
  // созданной константы
  return Context.TheBuilder->CreateInBoundsGEP(
    val->getValueType(),
    val,
    idx
  );
}

Value* ProxyExprAST::getRValue(SLContext& Context) {
  return OriginalExpr->getRValue(Context);
}

Value* NewExprAST::getRValue(SLContext& Context) {
  // Нам необходимо определить размер типа и заменить 0, который мы 
  // указали во время семантического анализа, реальным значением
  uint64_t allocSize = Context.TheTarget->getTypeAllocSize(
    NewType->getType());
  SizeExpr->Val = (int)allocSize;
  // Генерируем код для выражения вызова функции выделения блока
  // памяти
  Value* val = CallExpr->getRValue(Context);

  if (NeedCast) {
    // Необходимо произвести преобразование типов
    return Context.TheBuilder->CreateBitCast(
      val,
      ExprType->getType()
    );
  }
  
  return val;
}

Value* DeleteExprAST::getRValue(SLContext& Context) {
  Value* val = DeleteCall->getRValue(Context);
  return val;
}

Value* IndexExprAST::getLValue(SLContext& Context) {
  // У нас есть 2 отличающихся друг от друга варианта: для массивов
  // и для указателей
  if (isa<ArrayTypeAST>(Left->ExprType)) {
    // Получаем массив как lvalue и значение самого индекса
    Value* val = Left->getLValue(Context);
    Value* index = Right->getRValue(Context);

    std::vector< Value* > idx;

    idx.push_back(getConstInt(0));
    idx.push_back(index);
    // Создаем инструкцию GetElementPtr
    return Context.TheBuilder->CreateInBoundsGEP(
      Left->ExprType->getType(),
      val,
      idx
    );
  } else {
    // Для указателя мы должны получить его rvalue и значение 
    // самого индекса
    Value* val = Left->getRValue(Context);
    Value* index = Right->getRValue(Context);

    std::vector< Value* > idx;

    idx.push_back(index);
    // Создаем инструкцию GetElementPtr
    return Context.TheBuilder->CreateInBoundsGEP(
      ExprType->getType(),
      val,
      idx
    );
  }
}

Value* IndexExprAST::getRValue(SLContext& Context) {
  Value* val = getLValue(Context);
  return Context.TheBuilder->CreateLoad(ExprType->getType(), val);
}

Value* MemberAccessExprAST::getLValue(SLContext& Context) {
  // Для функций просто возвращаем ее тип
  if (isa<FuncTypeAST>(ExprType)) {
    return ThisSym->getValue(Context);
  }

  // Получаем lvalue для левой части (this)
  Value* val = Val->getLValue(Context);

  // Генерирум индекс на основе индекса члена класса/структуры
  Value* index = getConstInt(((VarDeclAST*)ThisSym)->OffsetOf);

  std::vector< Value* > idx;

  idx.push_back(getConstInt(0));
  idx.push_back(index);

  // Создаем инструкцию GetElementPtr
  return Context.TheBuilder->CreateGEP(
    ThisSym->Parent->getType()->getType(),
    val, 
    idx
  );
}

Value* MemberAccessExprAST::getRValue(SLContext& Context) {
  // Получаем lvalue для левой части (this)
  Value* val = getLValue(Context);

  // Для функций возвращаем полученное значение
  if (isa<FuncTypeAST>(ExprType)) {
    return val;
  }

  // Для rvalue необходимо создать инструкцию "load"
  return Context.TheBuilder->CreateLoad(ExprType->getType(), val);
}

Value* PointerAccessExprAST::getLValue(SLContext& Context) {
  assert(0 && "PointerAccessExprAST::getLValue should never be "
         "reached");
  return nullptr;
}

Value* PointerAccessExprAST::getRValue(SLContext& Context) {
  assert(0 && "PointerAccessExprAST::getRValue should never be "
         "reached");
  return nullptr;
}

Value* DerefExprAST::getLValue(SLContext& Context) {
  // Проверяем, что это lvalue
  if (Val->isLValue()) {
    // Получаем lvalue выражения и создаем инструкцию "load"
    Value* val = Val->getLValue(Context);
    return Context.TheBuilder->CreateLoad(
      PointerType::get(
        getGlobalContext(),
        Context.TheTarget->getProgramAddressSpace()
      ),
      val
    );
  } else {
    // Для функций и бинарных выражений генерируем rvalue
    return Val->getRValue(Context); 
  }
}

Value* DerefExprAST::getRValue(SLContext& Context) {
  // Получаем lvalue
  Value* val = getLValue(Context);

  // Для функций возвращаем полученное значение
  if (isa<FuncTypeAST>(ExprType)) {
    return val;
  }

  // Для rvalue необходимо создать инструкцию "load"
  return Context.TheBuilder->CreateLoad(ExprType->getType(), val);
}

Value* AddressOfExprAST::getRValue(SLContext& Context) {
  // Для rvalue выражения получения адреса, мы должны вернуть
  // lvalue операнда
  // Замечание: Данная операция не имеет lvalue
  return Val->getLValue(Context);
}

Value* CastExprAST::getRValue(SLContext& Context) {
  // Сначала проверяем, что это преобразование в целочисленный тип
  if (ExprType->isInt()) {
    if (Val->ExprType->isBool() || Val->ExprType->isChar()) {
      // Если исходный тип "bool" или "char", то дополняем 0
      return Context.TheBuilder->CreateZExt(
        Val->getRValue(Context), 
        ExprType->getType()
      );
    }

    assert(Val->ExprType->isFloat());
    // Генерируем преобразование "float" в "int"
    return Context.TheBuilder->CreateFPToSI(
      Val->getRValue(Context), 
      ExprType->getType()
    );
  }

  if (ExprType->isBool()) {
    // Для преобразования в "bool"
    return promoteToBool(Val->getRValue(Context), Val->ExprType, 
      *Context.TheBuilder);
    // Для преобразования в "char"
  } else if (ExprType->isChar()) {
    // Если это "bool", то дополняем 0
    if (Val->ExprType->isBool()) {
      return Context.TheBuilder->CreateZExt(
        Val->getRValue(Context),
        ExprType->getType()
      );
    }

    assert(Val->ExprType->isInt());
    // Обрезаем целочисленное значение
    return Context.TheBuilder->CreateTrunc(
      Val->getRValue(Context),
      ExprType->getType()
    );
  // Проверяем преобразование в строку
  } else if (ExprType->isString()) {
    // Проверяем, что это массив
    if (isa<ArrayTypeAST>(Val->ExprType)) {
      // Получаем lvalue исходного значения
      Value* val = Val->getLValue(Context);
      Value* tmp = getConstInt(0);

      std::vector< Value* > idx;

      idx.push_back(tmp);
      idx.push_back(tmp);

      // Проверяем, что значение является объявление переменной
      if (isa<AllocaInst>(val)) {
        AllocaInst *alloca = (AllocaInst*)val;
        // Создаем инструкцию GetElementPtr
        return Context.TheBuilder->CreateGEP(
          alloca->getAllocatedType(),
          val,
          idx
        );
      } else {
        assert(0);
      }
    } else {
      // Получаем rvalue значения
      Value* val = Val->getRValue(Context);
      // Создаем преобразование в новый тип
      return Context.TheBuilder->CreateBitCast(
        val,
        ExprType->getType()
      );
    }
  // Проверка на преобразования к указателю
  } else if (isa<PointerTypeAST>(ExprType)) {
    // Проверяем на приведение указателя
    if (isa<PointerTypeAST>(Val->ExprType)) {
      // Генерируем rvalue
      return Val->getRValue(Context);
    // Проверяем на приведение массива
    } else if (isa<ArrayTypeAST>(Val->ExprType)) {
      // Получаем lvalue исходного значения
      Value* val = Val->getLValue(Context);
      Value* tmp = getConstInt(0);

      std::vector< Value* > idx;

      idx.push_back(tmp);
      idx.push_back(tmp);

      // Проверяем, что значение является объявление переменной
      if (isa<AllocaInst>(val)) {
        AllocaInst *alloca = (AllocaInst*)val;
        // Создаем инструкцию GetElementPtr
        tmp = Context.TheBuilder->CreateGEP(
          alloca->getAllocatedType(),
          val,
          idx
        );
      } else {
        assert(0);
      }

      PointerTypeAST* ptrType = (PointerTypeAST*)ExprType;

      if (ptrType->Next->isVoid()) {
        // Создаем преобразование
        tmp = Context.TheBuilder->CreateBitCast(
          tmp,
          ptrType->getType()
        );
      }

      return tmp;
    } else {
      // Генерируем rvalue
      Value* val = Val->getRValue(Context);
      // Создаем преобразование
      return Context.TheBuilder->CreateBitCast(
        val,
        ExprType->getType()
      );
    }
  } else if (Val->ExprType->isInt() || Val->ExprType->isChar()) {
    // Преобразование "int" или "char" во "float" 
    return Context.TheBuilder->CreateSIToFP(
      Val->getRValue(Context), 
      ExprType->getType()
    );
  } else if (Val->ExprType->isBool()) {
    // Преобразование "bool" в "float"
    return Context.TheBuilder->CreateUIToFP(
      Val->getRValue(Context),
      ExprType->getType()
    );
  }

  assert(0 && "should never be reached");
  return nullptr;
}

Value* UnaryExprAST::getRValue(SLContext& Context) {
  assert(Op == tok::PlusPlus || Op == tok::MinusMinus);
  assert(isa<IndexExprAST>(Val) || isa<MemberAccessExprAST>(Val)
    || ExprType->isString());
  // Получаем lvalue
  Value* val = Val->getLValue(Context);
  // Создаем инструкцию "load" и константу 1 или -1
  Value* res = Context.TheBuilder->CreateLoad(
    ExprType->getType(),
    val
  );
  Value* tmp = getConstInt((Op == tok::PlusPlus) ? 1ULL : ~0ULL);

  if (isa<PointerTypeAST>(ExprType) || ExprType->isString()) {
    Type *resType;

    // Проверяем, что тип выражения указатель
    if (isa<PointerTypeAST>(ExprType)) {
      PointerTypeAST *ptrType = (PointerTypeAST*)ExprType;

      // Определяем тип для результата
      if (ptrType->Next->isVoid()) {
        resType = Type::getInt8Ty(getGlobalContext());
      } else {
        resType = ptrType->Next->getType();
      }
    } else {
      // Это строка, результат будет символом
      resType = Type::getInt8Ty(getGlobalContext());
    }

    // Для указателей создаем инструкцию GetElementPtr
    res = Context.TheBuilder->CreateGEP(resType, res, tmp);
  } else {
    // Создаем инструкцию "add"
    res = Context.TheBuilder->CreateAdd(res, tmp);
  }

  // Создаем инструкцию "store" для сохранения результата
  Context.TheBuilder->CreateStore(res, val);
  return res;
}

Value* BinaryExprAST::getRValue(SLContext& Context) {
  // Сначала необходимо проверить все специальные случаи

  // =
  if (Op == tok::Assign) {
    // Генерируем код для правой части выражения
    Value* right;
    
    // Специальная обработка для указателей
    if (isa<PointerTypeAST>(ExprType)) {
      // Если это константа 0, то конвертируем ее в null
      if (RightExpr->ExprType->isInt()) {
        right = ConstantPointerNull::get(
          (PointerType*)ExprType->getType()
        );
      } else {
        // Создаем rvalue
        right = RightExpr->getRValue(Context);
      }
    } else {
      // Создаем rvalue
      right = RightExpr->getRValue(Context);
    }

    // Получаем адрес по которому нужно сохранить значение
    Value* res = LeftExpr->getLValue(Context);

    // Генерируем инструкцию "store"
    Context.TheBuilder->CreateStore(right, res);
    return right;
  }

  // ,
  if (Op == tok::Comma) {
    // Генерируем код для левого и правого операнда
    LeftExpr->getRValue(Context);
    Value* rhs = RightExpr->getRValue(Context);
    // Возвращаем правый операнд
    return rhs;
  }

  // Постфиксная версия операторов ++ и --
  if (Op == tok::PlusPlus || Op == tok::MinusMinus) {
    // Получаем адрес переменной, а так же ее значение
    Value* var = LeftExpr->getLValue(Context);
    Value* val = nullptr;

    // Специальная обработка для IndexExprAST и MemberAccessExprAST
    if (isa<IndexExprAST>(LeftExpr)
        || isa<MemberAccessExprAST>(LeftExpr)) {
      // Создаем инструкцию "load"
      val = Context.TheBuilder->CreateLoad(
        ExprType->getType(),
        var
      );
    } else {
      // Генерируем rvalue
      val = LeftExpr->getRValue(Context);
    }

    if (!LeftExpr->ExprType->isInt()) {
      // Специальная обработка для указателей, т.к мы должны 
      // создать инструкцию GetElementPtr
      Value* tmp = getConstInt(
        (Op == tok::PlusPlus) ? 1ULL : ~0ULL
      );
      Type *resType;
   
      // Проверяем, что тип выражения указатель
      if (isa<PointerTypeAST>(ExprType)) {
        PointerTypeAST *ptrType = (PointerTypeAST*)ExprType;

        // Определяем тип для результата
        if (ptrType->Next->isVoid()) {
          resType = Type::getInt8Ty(getGlobalContext());
        } else {
          resType = ptrType->Next->getType();
        }
      } else {
        // Это строка, результат будет символом
        resType = Type::getInt8Ty(getGlobalContext());
      }

      // Создаем инструкцию GetElementPtr
      tmp = Context.TheBuilder->CreateGEP(resType, val, tmp);
      // Создаем инструкцию "store" и возвращаем старое значение
      Context.TheBuilder->CreateStore(tmp, var);
      return val;
    } else {
      if (Op == tok::PlusPlus) {
        // Создать целочисленную константу 1 и прибавить ее к 
        // загруженному ранее значению
        Value* tmp = getConstInt(1);
        tmp = Context.TheBuilder->CreateAdd(val, tmp, "inctmp");
        // Сохранить новое значение и вернуть старое значение
        Context.TheBuilder->CreateStore(tmp, var);
        return val;
      } else {
        // Создать целочисленную константу -1 и прибавить ее к 
        // загруженному ранее значению
        Value* tmp = getConstInt(~0ULL);
        tmp = Context.TheBuilder->CreateAdd(val, tmp, "dectmp");
        // Сохранить новое значение и вернуть старое значение
        Context.TheBuilder->CreateStore(tmp, var);
        return val;
      }
    }
  }

  ...

  // Специальная обработка для +/- над указателями
  if (isa<PointerTypeAST>(ExprType)) {
    // Получить значение для левой и правой части
    Value* ptr = LeftExpr->getRValue(Context);
    Value* index = RightExpr->getRValue(Context);

    // Для минуса нужно создать инструкцию "sub"
    if (Op == tok::Minus) {
      index = Context.TheBuilder->CreateSub(getConstInt(0), index);
    }

    // Определяем тип значения для загрузки
    PointerTypeAST *ptrType = (PointerTypeAST*)ExprType;
    Type *resType = ptrType->Next->isVoid()
      ? Type::getInt8Ty(getGlobalContext())
      : ptrType->Next->getType();
    
    // Создаем инструкцию GetElementPtr
    return Context.TheBuilder->CreateGEP(resType, ptr, index);
  }

  // Это обычное выражение с двумя операндами

  // Генерируем код для обоих операндов
  Value* lhs = LeftExpr->getRValue(Context);
  Value* rhs = RightExpr->getRValue(Context);
  ...
}

Правки для объявлений:

Hidden text

Value* VarDeclAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Получаем адрес переменной (т. к. память под саму переменную уже 
  // должна была выделена ранее во время генерации кода для функции)
  Value* val = getValue(Context);

  // Если у нас есть выражение инициализации, то нужно ее произвести
  if (Val) {
    Value* init;

    // Специальная обработка для указателей
    if (isa<PointerTypeAST>(ThisType)) {
      // Для целочисленной константы 0, создаем null
      if (Val->isIntConst()) {
        init = ConstantPointerNull::get(
          (PointerType*)ThisType->getType()
        );
      } else {
        // Специальная обработка для массивов
        if (isa<ArrayTypeAST>(Val->ExprType)) {
          // Получить lvalue выражения для инициализации
          init = Val->getLValue(Context);
          Value* tmp = getConstInt(0);

          std::vector< Value* > idx;

          idx.push_back(tmp);
          idx.push_back(tmp);

          // Проверяем, что значение является объявление переменной
          if (isa<AllocaInst>(init)) {
            AllocaInst *alloca = (AllocaInst*)init;
            // Создаем инструкцию GetElementPtr
            init = Context.TheBuilder->CreateGEP(
              alloca->getAllocatedType(), 
              init,
              idx
            );
          } else {
            assert(0);
          }
        } else {
          // Генерация кода для инициализирующего выражения
          init = Val->getRValue(Context);
        }
      }
    } else {
      // Генерация кода для инициализирующего выражения
      init = Val->getRValue(Context);
    }

    // Создание инструкции "store"
    return Context.TheBuilder->CreateStore(init, val);
  }

  return val;
}

Value* StructDeclAST::getValue(SLContext& Context) {
  // Генерируем тип для исходного типа
  ThisType->getType();
  return nullptr;
}

Value* StructDeclAST::generateCode(SLContext& Context) {
  assert(SemaState >= 5);
  // Генерируем тип для исходного типа
  ThisType->getType();
  return nullptr;
}

Заключение

В данной части мы добавили в наш учебный язык поддержку новых типов, таких как:

1. Строки;

2. Указатели;

3. Массивы;

4. Структуры.

Так же мы добавили новые операции в язык, такие как:

1. Операция разыменования указателей ("*" для одного операнда);

2. Операция взятия адреса ("&" для одного операнда);

3. Операция индексации (обращения к конкретному элементу массива);

4. Операция обращения к полю структуры;

5. Операторы "new" и "del" для выделения и очистки блока памяти.

Полный исходный код доступен на github (в папке tests есть несколько примеров, которые тестируют различные части языка). В дальнейшем мы рассмотрим, как добавить в наш язык поддержку классов с наследованием и динамической диспетчеризации методов, а так же перегрузку функций.

Полезные ссылки

1. https://llvm.org/docs/LangRef.html#getelementptr-instruction

2. https://llvm.org/docs/GetElementPtr.html

3. https://blog.yossarian.net/2020/09/19/LLVMs-getelementptr-by-example