Создаем свой собственный язык программирования с использованием LLVM. Часть 1: Лексический и синтаксический анализ

в 14:38, , рубрики: c++, LLVM, open source, Компиляторы, Программирование

Об авторе

С 2003 года, когда я поступил в ВУЗ, по нынешнее время я написал много различных парсеров, от простых (чтение конфигурационных файлов в ini, json и yaml форматах) до более сложных (полноценный парсер С++ подобного языка с поддержкой обобщенного программирования в виде шаблонов (схожих по сложности с тем что есть в языках С++ и D), ООП с множественным наследованием, pattern matching и др.), интерпретаторов для различных языков (от простых академических, таких как Brainfuck, до более серьезных скриптовых языков, которые были использованы в различных проектах (в основном различных pet-проектов), которые позволяли решать различные задачи от расчета значений математических функций для построения трехмерных сеток объектов с последующей их визуализацией, до интерпретаторов, позволяющих разработчику/пользователю расширять функционал ПО без модификации исходного кода самого приложения (например создание анимаций, рисования различных объектов, элементов управления и программирование обработчиков для этих элементов управления).

Еще когда я учился в институте мне было интересно изучать различные языки программирования. Позже мне захотелось узнать, как они были устроены внутри, как они работают. Мне было интересно, как из исходных текстов которые мы даем на вход компилятору получается программа, которая может быть запущена и которая делает то, что мы запрограммировали. Что привело меня к изучению теории компиляции и дизайну языков программирования. Я прочитал книгу, которая в свое время была классикой [1], так же во время чтения ее я наткнулся на очень интересную книгу [2], которая была больше направленна не на теорию, а на практику. И тогда у меня зародилась идея написать свой собственный компилятор, для своего собственного языка программирования, но все мои попытки воплотить мою идею в жизнь сталкивались с проблемой, что для того что бы написать хороший компилятор, который мог генерировать эффективный код и быть кросс платформенным, нужны знания, которые сложно получить по учебникам (а именно создание backend компилятора, хотя в это время я уже понимал как различные конструкции языка C++ работали под «капотом», такие как виртуальные таблицы, множественное наследование и много другое). В русском интернете эта тема была не освещена вообще, а в иностранном это что-то полезное было очень сложно найти. Но в какой-то момент я наткнулся на проект под названием LLVM. который позиционировал себя как набор библиотек и инструментов, которые могут помочь в написании компиляторов. Я начал изучать официальную документацию, но ее оказалось не достаточно, т. к. она описывала только простые кейсы использования данного «комбайна», язык Kaleidoscope демонстрировал только базовые концепты, которые могли бы помочь в создании своего языка программирования. Благо на тот момент уже были созданы различные реализации языков программирования, которые использовали LLVM в качестве backend (clang, ldc, crack и несколько других реализаций), соответственно я начал изучать как различные конструкции были реализованы в них. Так и родился simple

Simple

Изначально данный язык был задуман как обобщение всех моих знаний в теории компиляции и применении их в связке с LLVM, для создания простого языка с базовой поддержкой ООП, которые могли бы были положены в серию статей по созданию языка программирования. Изначально исходный код был написан в итеративном подходе, пригодном для написания серии статей (т. е. наращивание функционала из статьи в статью), но после написания всего планированного функционала, проект по тем или иным причинам был заброшен, поэтому сами статьи пришлось писать с нуля (т. к. исходные версии были утеряны), а сам исходный код пришлось адаптировать (т. к. осталась только финальная версия проекта, без его промежуточных частей). Финальная версия была написана около 11 лет назад (и использовался LLVM 3.0), в новой версии был взят исходный код старого проекта и произведены следующие изменения:

  1. Смена версии LLVM на 14, т. к. версии частично не совместимы, поэтому были произведены некоторые изменения что бы программа работала корректно с новыми реалиями;

  2. Изменена структура проекта (за основу был взята структура описанная в [3]).

Сам код по большей части остался в том виде, в каком он был 11 лет назад. Т.к. сам я уже 3 года не пишу на С++, и в последние годы его использования я периодически следил за историей его развития, но не применял большую часть нововведений на практике, поэтому некоторые части кода могут не подходить под правила хорошего тона в написании современных приложений на языке C++. Но для базового понимания того, как те или иные вещи можно реализовать в своем языке с использованием LLVM в качестве backend (пожелания по улучшению просьба оставлять в комментариях или в личных сообщениях).

По моему ощущению за эти 11 лет даже с появлением некоторого количества книг по LLVM, ситуация не сильно изменилась в лучшую сторону и если кто-то хочет написать что-то серьезнее чем простой язык программирования вида Kaleidoscope, то придется все равно собирать все знания по крупицам и копаться в исходных кодах компиляторов для различных языков программирования (если это не так, то был бы признателен если бы Вы поделились ссылками и своими размышлениями по данной тематике в комментариях). Поэтому не смотря на то, что данный проект был создан давно, знания которые были собраны в нем могли бы помочь многим, кто хотел бы создать свой язык программирования и не знает с чего начать и где смотреть, как можно было бы реализовать более высокоуровневые аспекты языка.

О серии

Сам цикл будет разбит на несколько статей, в которых мы реализуем данный язык.

Мы начнем с простого подмножества в котором доступны только два типа данных int и float, пользователь может объявлять локальные переменные и описывать функции, использовать различные арифметические операции над ними, а так же будут доступны управляющие конструкции if, while, for, а так же break, continue и return. Данное подмножество будет реализовано в рамках нескольких статей начиная с лексического и синтаксического анализаторов, затем мы добавим семантический анализатор (проверка типов и корректности программы) и в заключении будет реализована генерация промежуточного кода для LLVM.

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

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

fn printLn(s1: string, s2: string) {
  print(s1);
  print(s2);
  printLn("");
}

fn printLn(s: string, i: int) {
  print(s);
  print(i);
  printLn("");
}

class Shape {
  virt draw() {
  }
}

class Square extends Shape {
  side: int = 0;

  new(s: int) {
    side = s;
  }

  impl draw() {
    printLn("Square.draw side: ", side);
  }
}

class Circle extends Shape {
  radius: int = 0;

  new(r: int) {
    radius = r;
  }

  impl draw() {
    printLn("Circle.draw radius: ", radius);
  }
}

fn main(): float {
  for let i: int = 0; i < 10; ++i {
    let p: Shape* = 0;
    
    if i % 2 == 0 {
      p = new Square((i + 1) * 10);
    } else {
      p = new Circle((i + 1) * 5);
    }

    p.draw();
    del p;
  }

  return 0.0;
}

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

Для упрощения, что бы сразу можно видеть результаты работы весь генерируемый код будет запускаться в JIT, но по возможности генерацию машинного кода и исполняемых файлов можно будет добавить самим. Пример того, как это можно сделать можно посмотреть в официальном материале на сайте LLVM [4].

Замечание по генерируемому коду: в процессе написания изначальной версии я очень много времени провел изучая код, который генерировал clang для различных конструкций языка C++, поэтому на тот момент качество кода генерированного данным интерпретатором был сопоставим с тем, что генерировал clang, включая различные оптимизации по переиспользованию блоков. С тех пор прошло много времени, но код до сих пор в большинстве ситуаций совпадает с тем, что генерирует clang для программы, если ее переписать один-в-один на C++ [5].

Если данная серия будет интересна, то возможно будет ее продолжение, у меня есть несколько идей о том, что еще можно будет добавить в язык. Например это может быть:

  1. Поддержка модулей (import и export);

  2. Добавление области видимости для переменных и членов класса (private, protected, public);

  3. Добавление множественного наследования по средством интерфейсов (или полного аналога, как в C++);

  4. Вывод типов (type inference), сопоставление с образцом (pattern matching);

  5. Обобщенное программирование (generics);

  6. Вычисление во время компиляции (template metaprogramming или constant expressions).

Что такое компилятор?

Согласно Wikipedia компилятор — программа, переводящая написанный на языке программирования текст в набор машинных кодов.

Традиционно компилятор состоит из двух больших блоков:

  1. Frontend – основная задача которого заключается в чтении исходных кодов на конкретном языке программирования, анализа его на наличие как синтаксических, так семантических ошибок, а в случае их отсутствия, генерации промежуточного представления программы, которое может быть передано в backend, для последующей обработки. Один из вариантов представления полученного после успешной отработки frontend является аннотированное AST (Abstract Syntax Tree), в котором содержится вся необходимая информация о программе;

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

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

Раньше для написания backend приходилось писать генератор кода под каждую платформу и операционную систему, с появлением LLVM данная задача упростилась, т. к. достаточно написать генератор в LLVM IR и дальше все остальное можно будет сделать через утилиты, идущие с LLVM (хочу уточнить, что какую-то часть платформозависимых функций придется все равно реализовать, например поддержку ABI для платформы, но все равно большую часть LLVM берет на себя).

Frontend в свою очередь состоит из:

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

  2. Синтаксический анализатор (или парсер);

  3. Семантический анализатор (или проверка типов);

  4. Генератор промежуточного кода.

Далее мы рассмотрим более подробно первые 2 пункта, последние 2 будут более подробно описаны в следующих статьях.

Backend в свою очередь обычно состоит из:

  1. Оптимизатор промежуточного кода;

  2. Генерация кода для целевой платформы.

В рамках данной серии backend мы рассматривать не будем.

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

Лексический анализатор — часть компилятора, которая читает текст программы из входного потока и преобразовывает его в набор лексем или токенов (неделимые примитивы языка, такие как ключевые слова, идентификаторы, строковые и числовые константы, операторы и др), которые в простейшем случае представляют собой структуру содержащую информацию о типе прочитанного токена и его значение. Так же лексический анализатор часто убирает из выходного потока «шум» (конструкции языка, которые не влияют на дальнейший разбор программы, такие как комментарии и пробельные символы (в языках, где отступы не являются значимыми для разбора программы)). Причина данного шага банальна, проще работать с представлением, которое просто использовать в машинной обработке, в котором нет никаких неоднозначностей. Например для синтаксического анализатора может быть не важно значение целочисленной константы, а важно то, что это целочисленная константа. Так же часто в языках программирование одна и та же лексическая конструкция может быть записана множеством способов. Например, в языке C++ целочисленное число 10 может быть записано множеством способов

10  // Десятичная система
012 // Восьмеричная
0xA // Шестнадцатеричная
0b1010 // Двоичная

И это только некоторые способы записи, которые после лексического анализа может быть преобразовано в структуру вида

type

value

number

10

Также лексический анализатор может иметь дело с различными кодировками и специальными конструкциями, которые в результате все равно будут приводится к унифицированному набору токенов, которые будут удобны для обработки (например различные escape и Unicode последовательности в строковых литералах некоторых языков).

Обычно все лексические конструкции можно описать в виде набора регулярных выражений, которые могут распознать каждую лексическую конструкцию. Существуют программы, которые позволяют взять на себя работу по созданию лексического анализатора, на вход таких программ подается описание лексем языка в виде регулярных выражений (обычно записываются в специальном формате, понимаемых конкретной утилитой) и они на основе данного входного файла генерируют исходный код содержащий лексический анализатор (часто в виде конечного автомата, который понимает заданный язык) для заданного входного языка. Они доступны для многих языков программирования, например для C++ одна из таких утилит называется flex.

Более подробнее про лексический анализ, алгоритмы, которые можно применить для преобразования регулярных выражений в конечный автомат и другое, можно прочитать в [1].

Для данной серии мы реализуем лексический анализатор сами.

Для начала я покажу основные структуры, которые используются в лексическом анализаторе и других частях программы.

struct Name { 
  const char *Id;
  int Kind;
  size_t Length; 
};

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

Сама же таблица символов имеет следующий вид:

class NamesMap { 
  bool IsInit; 
  llvm::StringMap<Name> HashTable; 
  Name *addName(StringRef Id, tok::TokenKind TokenCode); 
public: 
  NamesMap(): IsInit(false) { } 
  void addKeywords(); 
  Name *getName(StringRef Id); 
};

Где TokenKind обычный enum вида:

namespace tok { 
enum TokenKind : unsigned short { 
#define TOK(ID, TEXT) ID, 
#include "simple/Basic/TokenKinds.def" 
}; 
} // namespace tok
Hidden text 
// simple/Basic/TokenKinds.def
#ifndef TOK 
#define TOK(ID, TEXT) 
#endif 

#ifndef KEYWORD 
#define KEYWORD(ID, TEXT) TOK(ID, TEXT) 
#endif 

KEYWORD(Int, "int") 
KEYWORD(Float, "float") 
KEYWORD(Void, "void") 
KEYWORD(Def, "fn") 
KEYWORD(If, "if") 
KEYWORD(Else, "else") 
KEYWORD(For, "for") 
KEYWORD(While, "while") 
KEYWORD(Return, "return") 
KEYWORD(Break, "break") 
KEYWORD(Continue, "continue") 
KEYWORD(Var, "let") 
TOK(Identifier, "identifier") 

TOK(IntNumber, "") 
TOK(FloatNumber, "") 
TOK(CharLiteral, "") 
TOK(StringConstant, "") 

TOK(Plus, "+") 
TOK(PlusPlus, "++") 
TOK(Minus, "-") 
TOK(MinusMinus, "--") 
TOK(Not, "!") 
TOK(Tilda, "~") 
TOK(Mul, "*") 
TOK(Div, "/") 
TOK(Mod, "%") 
TOK(LShift, "<<") 
TOK(RShift, ">>") 
TOK(LogAnd, "&&") 
TOK(LogOr, "||") 
TOK(BitAnd, "&") 
TOK(BitOr, "|") 
TOK(BitXor, "^") 
TOK(Less, "<") 
TOK(Greater, ">") 
TOK(LessEqual, "<=") 
TOK(GreaterEqual, ">=") 
TOK(Equal, "==") 
TOK(NotEqual, "!=") 
TOK(Assign, "=") 
TOK(Comma, ",") 
TOK(Dot, ".") 
TOK(Question, "?") 
TOK(Colon, ":") 
TOK(Semicolon, ";") 
TOK(OpenParen, "(") 
TOK(CloseParen, ")") 
TOK(BlockStart, "{") 
TOK(BlockEnd, "}") 
TOK(OpenBrace, "[") 
TOK(CloseBrace, "]") 

TOK(Invalid, "") 
TOK(EndOfFile, "EOF") 

#undef KEYWORD 
#undef TOK

Сам токен, который возвращается в результате лексического анализа имеет вид:

class Token {
  friend class Lexer; 

  const char *Ptr; ///< Положение токена во входном буфере
  size_t Length; ///< Длина токена в символах
  tok::TokenKind Kind; ///< Тип
  union { 
    Name *Id; ///< Значение, если это идентификатор или ключевое слово
    char *Literal; ///< Значение, если это константа (например целочисленная)
  }; 
  ...
};

Как видно из выше представленной класса, токен хранит минимальное количество информации:

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

  2. Длина токена и его тип;

  3. Значение токена (для оптимизации места используется union).

Сам же лексический анализатор имеет следующий вид:

class Lexer { 
  SourceMgr &SrcMgr; 
  DiagnosticsEngine &Diags; 

  StringRef BufferStart; 
  const char *CurPos; 

  unsigned CurBuffer = 0; 

  static NamesMap IdsMap; 

  llvm::SMLoc getLoc(const char *Pos) const { 
    return llvm::SMLoc::getFromPointer(Pos); 
  } 

public: 
  Lexer(SourceMgr &SrcMgr, DiagnosticsEngine &Diags) 
    : SrcMgr(SrcMgr), Diags(Diags) { 
    CurBuffer = SrcMgr.getMainFileID(); 
    BufferStart = SrcMgr.getMemoryBuffer(CurBuffer)->getBuffer(); 
    CurPos = BufferStart.begin(); 
    IdsMap.addKeywords(); 
  } 

  DiagnosticsEngine &getDiagnostics() const { 
    return Diags; 
  } 

  void next(Token &Result); 
};

Он имеет всего одну публичную значимую функцию next, которая считывает новый токен. Реализация самой функции представлена ниже:

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

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

  // Считываем символы, пока не найдем корректный токен
  while (Result.Kind == tok::Invalid) { 
    const char *tokenStart = p; 
// Макрос для чтения одинарного оператора
#define CHECK_ONE(CHR, TOK)  
      case CHR:  
        Result.Length = 1;  
        Result.Kind = TOK;  
        break 
// Макрос для чтения операторов вида ">" и ">=". Возвращает, T1 если 
// встретился только CH1 и T2, если следом идет CH2
#define CHECK_TWO(CH1, CH2, T1, T2)  
      case CH1:  
        if (*p == CH2) {  
          ++p;  
          Result.Length = 2;  
          Result.Kind = T1;  
        } else {  
          Result.Length = 1;  
          Result.Kind = T2;  
        }  
        break 
    // Переходим к следующему символу, но запоминаем его значение и смотрим 
    // что это за символ
    switch (char ch = *p++) { 
      case 0: 
        // Это конец файла, возвращаем его, но предварительно возвращаем
        // положение лексического анализатора на начало этого токена (что бы
        // можно его перечитать, если это необходимо)
        --p; 
        Result.Kind = tok::EndOfFile; 
        break; 

      case 'n': case 'r': case ' ': case 't': case 'v': case 'f': 
        // Считываем все пробельные символы в цикле, т. к. их может быть 
        // много
        while (charinfo::isWhitespace(*p)) { 
          ++p; 
        } 
        // Продолжаем искать токен
        continue; 

      // Анализ на операторы состоящих из одного символа
      CHECK_ONE('~', tok::Tilda); 
      CHECK_ONE('*', tok::Mul); 
      CHECK_ONE('%', tok::Mod); 
      CHECK_ONE('^', tok::BitXor); 
      CHECK_ONE(',', tok::Comma); 
      CHECK_ONE('?', tok::Question); 
      CHECK_ONE(':', tok::Colon); 
      CHECK_ONE(';', tok::Semicolon); 
      CHECK_ONE('(', tok::OpenParen); 
      CHECK_ONE(')', tok::CloseParen); 
      CHECK_ONE('{', tok::BlockStart); 
      CHECK_ONE('}', tok::BlockEnd); 
      // Анализ на операторы состоящих из одного символа или альтернативой из 
      // 2-х символов
      CHECK_TWO('-', '-', tok::MinusMinus, tok::Minus); 
      CHECK_TWO('+', '+', tok::PlusPlus, tok::Plus); 
      CHECK_TWO('!', '=', tok::NotEqual, tok::Not); 
      CHECK_TWO('=', '=', tok::Equal, tok::Assign); 
      CHECK_TWO('|', '|', tok::LogOr, tok::BitOr); 
      CHECK_TWO('&', '&', tok::LogAnd, tok::BitAnd); 

      case '/': 
        if (*p == '/') {
          // Одно строчный комментарий
          ++p; 
          // В цикле ищем конец строки или конец файла
          while (*p && (*p != 'r' && *p != 'n')) {
            ++p;
          }
          break; 
        } else if (*p == '*') {
          // Это много строчный комментарий
          unsigned Level = 1; 
          ++p; 

          while (*p && Level) { 
            // Считываем все символы пока не найдем конец файла или пока не 
            // выйдем из вложенного много строчного комментария
            if (*p == '/' && p[1] == '*') { 
              p += 2; 
              ++Level; 
            // Проверяем на конец считывания комментария
            } else if (*p == '*' && p[1] == '/' && Level) {
              // Уменьшаем уровень вложенности
              p += 2; 
              --Level; 
            } else {
              // Продолжаем искать конец комментария
              ++p; 
            } 
          } 
 
          if (Level) {
            // Комментарий не закрыт, сообщаем об ошибке
            Diags.report(getLoc(p), diag::ERR_UnterminatedBlockComment); 
          } 

          continue; 
        } else {
          // Это обычный оператор деления
          Result.Length = 1; 
          Result.Kind = tok::Div; 
          break; 
        } 

      case '<': 
        if (*p == '=') {
          // Это <=
          ++p; 
          Result.Length = 2; 
          Result.Kind = tok::LessEqual; 
          break; 
        } else if (*p == '<') {
           // Это <<
          ++p; 
          Result.Length = 2; 
          Result.Kind = tok::LShift; 
          break; 
        } else {
          // Это <
          Result.Length = 1; 
          Result.Kind = tok::Less; 
          break; 
        } 

      case '>': 
        if (*p == '=') {
           // Это >=
          ++p; 
          Result.Length = 2; 
          Result.Kind = tok::GreaterEqual; 
          break; 
        } else if (*p == '>') {
          // Это >> 
          ++p; 
          Result.Length = 2; 
          Result.Kind = tok::RShift; 
          break; 
        } else {
          // Это >
          Result.Length = 1; 
          Result.Kind = tok::Greater; 
          break; 
        } 

      case '1': case '2': case '3': case '4': case '5': case '6': case '7': 
      case '8': case '9': 
        // Считываем целую часть числа
        while (charinfo::isDigit(*p)) { 
          ++p; 
        } 

      case '0': 
        Result.Kind = tok::IntNumber; 
        // Проверяем на то, что вещественное число
        if (*p == '.') {
          const char *firstDigit = p++; 
          // Считываем все цифры
          while (charinfo::isDigit(*p)) { 
            ++p; 
          } 

          // Проверяем на наличие экспоненты у числа
          if (*p == 'e' || *p == 'E') { 
            ++p; 
            // Проверка на наличие знака в экспоненте
            if (*p == '+' || *p == '-') { 
              ++p; 
            } 

            // Должна быть хотя бы одна цифра после [eE][+-]
            firstDigit = p; 

            while (charinfo::isDigit(*p)) { 
              ++p; 
            } 

            // Проверяем, что в экспоненте есть хотя бы одна цифра
            if (p == firstDigit) { 
              Diags.report(getLoc(p),
                           diag::ERR_FloatingPointNoDigitsInExponent); 
            } 
          } 

          Result.Kind = tok::FloatNumber; 
        } 

        // Создаем токен на основе константы
        Result.Length = (int)(p - tokenStart); 
        Result.Literal = new char[Result.Length + 1]; 
        memcpy(Result.Literal, tokenStart, Result.Length); 
        Result.Literal[Result.Length] = 0; 
        break; 

      default: 
        // Проверяем, что это идентификатор
        if (charinfo::isIdentifierHead(ch)) { 
          // Считываем все символы идентификатора
          while (charinfo::isIdentifierBody(*p)) { 
            ++p; 
          }
          // Создаем токен для идентификатора или ключевого слова
          size_t length = (size_t)(p - tokenStart); 
          Name *name = IdsMap.getName(StringRef(tokenStart, length)); 

          Result.Id = name; 
          Result.Kind = (tok::TokenKind)name->Kind; 
          Result.Length = name->Length; 

          break; 
        } else {
           // Не определенный символ
          Diags.report(getLoc(p), diag::ERR_InvalidCharacter); 
          break; 
        } 
    } 

    Result.Ptr = tokenStart; 
  } 

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

Для упрощения реализации при возникновении ошибки, выводится сообщение об ошибки и работа программы завершается. Если бы необходимо выводить все найденные ошибки (как в большинстве серьезных компиляторах), то можно было бы ввести дополнительный тип токена Error, и возвращать его, сам ошибочный символ игнорировать, а на последующих стадиях обрабатывать что если вернулся Error, то происходило бы восстановление от ошибок. Аналогично и с самой функцией, при большем количестве и сложности лексем языка (например поддержка Unicode, различных escape последовательностей, и различных типов строк (как в С++ или D), ее можно было бы разбить на основной цикл, а разбор конкретных лексем вынести в отдельные функции (например scanIdentitifer, scanNumber, scanHexString, scanString и т.д).

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

Синтаксический анализатор (парсер) — часть компилятора, основной целью которой является анализ потока токенов на принадлежность грамматике конкретного языка.

Часто результатом работы парсера является AST, которое содержит всю необходимую информацию для дальнейших стадий компилятора.

Данная реализация парсера была написана с помощью метода рекурсивного спуска и метода разбора выражений с приоритетом операций. Про другие варианты построения парсеров, а так же вариант использования специальных программ для генерации парсеров (например bison для C++) можно прочитать в [1] или в интернете.

Для упрощения работы с потоком токенов при разборе грамматики, мы будем использовать следующий набор классов, который позволяет работать с токенами, как с итераторами, что позволяет писать код вида

if (CurPos == tok::Identifier) {
  ...
  ++CurPos;
}
if (CurPos + 1 == tok::Identifier) {
  ...
}

Интерфейс классов:

class TokenStream { 
  struct StreamNode { 
    StreamNode(StreamNode *next, StreamNode *prev) ;

    Token Tok;        ///<  Сам токен
    StreamNode *Next; ///< Следующий элемент в списке 
    StreamNode *Prev; ///< Предыдущий элемент в списке
  }; 

  class TokenStreamIterator { 
  public: 
    TokenStreamIterator &operator=(const TokenStreamIterator &other);

    bool empty() const ;
 
    llvm::SMLoc getLocation() const ;

    bool operator ==(tok::TokenKind tok) const;
    bool operator !=(tok::TokenKind tok) const;
    const Token &operator *() const;
    const Token *operator ->() const;
   TokenStreamIterator operator ++(int);
   TokenStreamIterator &operator ++() ;
    TokenStreamIterator operator —(int);
    TokenStreamIterator &operator --() ;
    TokenStreamIterator operator +(int count);
    TokenStreamIterator operator -(int count);

    friend class TokenStream; 

  private: 
    TokenStream *CurStream; ///< Родительский контейнер
    StreamNode *CurPos;     ///< Текущая позиция в контейнере

    TokenStreamIterator(TokenStream *source = nullptr,
                        StreamNode *curPos = nullptr) ;
  }; 
  /// Экземпляр лексического анализатора, с исходным кодом конкретного файла
  Lexer *Lex;
  StreamNode *Head; ///< Первый элемент в списке
  StreamNode *Tail; ///< Последний элемент в списке
  bool ScanDone;    ///< true — если считывание полностью завершено

  StreamNode *next(StreamNode *curPos); 

public: 
  typedef TokenStreamIterator iterator; 

  TokenStream(Lexer *lexer); 

  ~TokenStream(); 

  DiagnosticsEngine &getDiagnostics() const;

  TokenStreamIterator begin(); 
};

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

 void Parser::check(tok::TokenKind tok) { 
  if (CurPos != tok) { 
    getDiagnostics().report(CurPos.getLocation(), 
                            diag::ERR_Expected, 
                            tok::toString(tok), 
                            tok::toString(CurPos->getKind())); 
  } 

  ++CurPos; 
}

Для упрощения работы, как и с ошибками в лексическом анализаторе, будем просто выводить сообщение об ошибки и завершать работу приложения. Но возможны различные варианты восстановления от ошибок, которые зависят от конкретной конструкции и типа ошибки, например некоторые ошибки могут быть обработаны путем добавление необходимых элементов и продолжения анализа (например отсутствие операнда у бинарного или унарного оператора). Так же это может вариант панического восстановления, путем пропуска токенов и поиска ближайшего синхронизирующего токена (например ";" или "}"). Про все эти методы можно более подробно прочитать в [1] или в интернете.

В процессе своей работы парсер будет возвращать AST, со следующим списком базовых типов (все типы поддерживают RTTI, который используется в LLVM [6].

struct TypeAST { 
  enum TypeId { 
    TI_Void,     ///< void 
    TI_Bool,     ///< булево значение 
    TI_Int,      ///< int
    TI_Float,    ///< float 
    TI_Function  ///< функция 
  }; 
 
  TypeAST(int typeKind);
  
  ...

  int TypeKind; ///< тип в иерархии типов
  static llvm::StringSet<> TypesTable; ///< список используемых типов
};

Данный класс является базовым для иерархии типов в дереве (например базовые типы (int, float, bool, void), тип для функций. В последующих статьях серии данный список будет расширен и будут добавлены типы для строк, символов, классов, структур, указателей и массивов.

struct ExprAST { 
  enum ExprId { 
    EI_Int,         ///< целочисленные константы
    EI_Float,       ///< константы для чисел с плавающей точкой
    EI_Id,          ///< использование переменной 
    EI_Cast,        ///< преобразование типов
    EI_Unary,       ///< унарная операция
    EI_Binary,      ///< бинарная операция
    EI_Call,        ///< вызов функции
    EI_Cond         ///< тернарный оператор 
  }; 

  ExprAST(llvm::SMLoc loc, int exprKind, TypeAST *type = nullptr) ;
  virtual ~ExprAST();

  ...

  llvm::SMLoc Loc; ///< расположение выражения в исходном файле
  int ExprKind; ///< тип в иерархии выражений
};
typedef llvm::SmallVector<ExprAST*, 4> ExprList;

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

struct StmtAST { 
  enum StmtId { 
    SI_Expr, ///< выражение
    SI_Var, ///< объявление локальной переменной
    SI_For, ///< цикл for 
    SI_While, ///< цикл while 
    SI_If, ///< инструкция ветвления if 
    SI_Return, ///< инструкция возврата из функции return 
    SI_Continue, ///< инструкция перехода к следующей итерации цикла continue 
    SI_Break, ///< инструкция досрочного выхода из цикла break 
    SI_Block ///< блок инструкций
  }; 

  StmtAST(llvm::SMLoc loc, int stmtKind) ;
  virtual ~StmtAST();

  ...

  llvm::SMLoc Loc; ///< расположение выражения в исходном файле
  int StmtKind; ///< тип в иерархии инструкций
}; 

typedef llvm::SmallVector< StmtAST*, 4 > StmtList;

Данный класс является базовым для иерархии различных инструкций языка, такие как условные операторы if, циклы while и for, а так же операторы выхода из цикла break, continue, инструкция возврата из функции, объявление локальных переменных и выражений, а так же блок с набором инструкций.

struct SymbolAST { 
  enum SymbolId { 
    SI_Variable,    ///< переменная
    SI_Function,    ///< функция 
    SI_Module,      ///< модуль 
    SI_Parameter,   ///< параметр функции 
    SI_Block        ///< блочная декларация
  }; 

  SymbolAST(llvm::SMLoc loc, int symbolKind, Name *id);
  virtual ~SymbolAST();

  ...

  llvm::SMLoc Loc;  ///< расположение в исходном файле
  int SymbolKind;   ///< тип в иерархии объявлений
  Name *Id;         ///< имя объявлений
};

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

Иерархия для типов

На данный момент для типов у нас будет всего два типа BuiltinTypeAST, который отвечает за базовые типы, такие как int, float, bool и void.

struct BuiltinTypeAST : TypeAST { 
  static TypeAST *get(int type); 
private: 
  BuiltinTypeAST(int type) ;
};

и FuncTypeAST, который отвечает за прототип функции (тип возвращаемого ей значения и типы ее параметров)

struct ParameterAST { 
  ParameterAST(TypeAST* type, Name* id);

  TypeAST* Param; ///< тип параметра
  Name* Id; ///< имя 
}; 

typedef llvm::SmallVector< ParameterAST*, 4 > ParameterList; 

struct FuncTypeAST : TypeAST { 
  FuncTypeAST(TypeAST* returnType, const ParameterList& params);

  TypeAST* ReturnType; ///< тип возвращаемого значение или nullptr
  ParameterList Params; ///< список параметров функции
};

Иерархия выражений

Для констант целочисленных и с плавающей точкой будем использовать следующие классы:

struct IntExprAST : ExprAST { 
  IntExprAST(llvm::SMLoc loc, int value) ;

  int Val; ///< значение
}; 

struct FloatExprAST : ExprAST { 
  FloatExprAST(llvm::SMLoc loc, double value) ;

  double Val; ///< значение
};

Для использования переменных будем использовать следующий класс (на данный момент может ссылаться на параметры функции или переменные объявленные в теле функции, но в дальнейшем может ссылать и на члены и методы классов/структур:

struct IdExprAST : ExprAST { 
  IdExprAST(llvm::SMLoc loc, Name *name) ;

  Name* Val; ///< имя ссылаемой переменной
};

Для преобразования типов будем использовать следующий класс (т. к. явных преобразований в языке не будет, то этот класс будет в основном использоваться как вспомогательный другими выражениями, для приведения операндов к единому типу (например int к float или int/float к bool в условных выражениях)):

struct CastExprAST : ExprAST { 
  CastExprAST(llvm::SMLoc loc, ExprAST *expr, TypeAST *type) ;

  ExprAST* Val; ///< выражение, которое нужно преобразовать
};

Для выражений с одним операндом (такие как +,-, ++, -- и ~) будем использовать следующий класс:

struct UnaryExprAST : ExprAST { 
  UnaryExprAST(llvm::SMLoc loc, int op, ExprAST *value) ;

  int Op; ///< оператор
  ExprAST* Val; ///< операнд выражения
};

Для выражений с двумя аргументами будем использовать следующий класс:

struct BinaryExprAST : ExprAST { 
  BinaryExprAST(llvm::SMLoc loc, int op, ExprAST *lhs, ExprAST *rhs) ;

  int Op; ///< оператор
  ExprAST* LeftExpr; ///< левый оператор
  ExprAST* RightExpr; ///< правый оператор
};

Для тернарного оператора ? : будем использовать следующий класс:

struct CondExprAST : ExprAST { 
  CondExprAST(llvm::SMLoc loc, ExprAST *cond, ExprAST *ifExpr, 
    ExprAST* elseExpr) ;

  ExprAST* Cond; ///< условие
  ExprAST* IfExpr; ///< выражение, если условие истинно
  ExprAST* ElseExpr; ///< выражение, если условие ложно
};

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

struct CallExprAST : ExprAST { 
  CallExprAST(llvm::SMLoc loc, ExprAST *callee, const ExprList &args) ;

  ExprAST* Callee; ///< функция для вызова
  ExprList Args; ///< список аргументов функции
};

Иерархия для инструкций

Для инструкций, которые содержат выражения (например вызов функции или присвоение переменной):

struct ExprStmtAST : StmtAST { 
  ExprStmtAST(llvm::SMLoc loc, ExprAST *expr) ;

  ExprAST* Expr; ///< выражение, которое должно быть выполнено
};

Инструкция ветвления if:

struct IfStmtAST : StmtAST { 
  IfStmtAST(llvm::SMLoc loc, 
    ExprAST *cond, 
    StmtAST *thenBody, 
    StmtAST* elseBody) ;

  ExprAST* Cond; ///< условие для проверки
  /// инструкции, для выполнения в случае, если условие истинно
  StmtAST* ThenBody;
  /// инструкции, для выполнения в случае, если условие ложно
  StmtAST* ElseBody; 
};

Цикл с предусловием:

struct WhileStmtAST : StmtAST { 
  WhileStmtAST(llvm::SMLoc loc, ExprAST *cond, StmtAST *body) ;

  ExprAST* Cond; ///< условие для проверки
  StmtAST* Body; ///< инструкции тела цикла
};

Инструкция для досрочного выхода из цикла:

struct BreakStmtAST : StmtAST { 
  BreakStmtAST(llvm::SMLoc loc) ;
};

Инструкция для перехода к следующей итерации цикла:

struct ContinueStmtAST : StmtAST { 
  ContinueStmtAST(llvm::SMLoc loc) ;
};

Инструкция для возврата из функции:

struct ReturnStmtAST : StmtAST { 
  ReturnStmtAST(llvm::SMLoc loc, ExprAST *expr) ;

  ExprAST* Expr; ///< значение, которое нужно вернуть (или nullptr)
};

Блок с инструкциями (например тело функции или цикла):

struct BlockStmtAST : StmtAST { 
  BlockStmtAST(llvm::SMLoc loc, const StmtList &body) ;

  StmtList Body; ///< список инструкций для выполнения
};

Объявление локальной переменной:

struct DeclStmtAST : StmtAST { 
  DeclStmtAST(llvm::SMLoc loc, const SymbolList &decls) ;

  SymbolList Decls; ///< список объявлений
};

Цикл for. Данный цикл, как и его аналог из C++, имеет три блока (для объявлений переменных цикла или инициализации цикла, условие цикла и операции, которые должны быть выполнены после каждой итерации), которые являются не обязательными, а так же обязательное тело цикла:

struct ForStmtAST : StmtAST { 
  ForStmtAST(llvm::SMLoc loc, 
    ExprAST *initExpr, 
    const SymbolList &decls, 
    ExprAST* cond, 
    ExprAST* post, 
    StmtAST* body);

  ExprAST* InitExpr; ///< выражение для инициализации переменных цикла
  SymbolList InitDecls; ///< список переменных цикла с их инициализацией
  ExprAST* Cond; ///< условие цикла
  ExprAST* Post; ///< выражение для выполнения после каждой операции 
  StmtAST* Body; ///< тело цикла
};

Иерархия для объявлений

Объявление переменной:

struct VarDeclAST : SymbolAST {
  VarDeclAST(llvm::SMLoc loc, TypeAST *varType, Name *id,
    ExprAST* value);

  TypeAST* ThisType; ///< тип символа
  ExprAST* Val; ///< инициализатор (может быть nullptr, если его нет)
};

Базовый класс для объявлений, которые могут сами содержать другие объявления (например функции, классы, структуры):

struct ScopeSymbol : SymbolAST {
  ScopeSymbol(llvm::SMLoc loc, int symbolKind, Name *id);

  SymbolAST* find(Name* id, int flags = 0);

  typedef std::map< Name*, SymbolAST* > SymbolMap;
  SymbolMap Decls; ///< вложенные объявления
};

Параметр функции:

struct ParameterSymbolAST : SymbolAST {
  ParameterSymbolAST(ParameterAST* param);

  ParameterAST* Param; ///< значение параметра (тип и имя)
};

Объявление функции:

struct FuncDeclAST : ScopeSymbol {
  FuncDeclAST(llvm::SMLoc loc, TypeAST *funcType, Name *id,
    StmtAST* body, int tok = tok::Def);

  TypeAST* ThisType; ///< прототип функции
  TypeAST* ReturnType;
 ///< тип возвращаемого значения
  StmtAST* Body; ///< тело функции
  int Tok; ///< токен при помощи которого была объявлена функция
};

Объявление модуля:

struct ModuleDeclAST : ScopeSymbol {
  ModuleDeclAST(DiagnosticsEngine &D, const SymbolList& decls);

  static ModuleDeclAST* load(
    llvm::SourceMgr &SrcMgr,
    DiagnosticsEngine &Diags,
    llvm::StringRef fileName
  );

  SymbolList Members; ///< список объявлений в модуле
  DiagnosticsEngine &Diag; ///< модуль диагностики
};

Разбор выражений

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

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

  switch (CurPos->getKind()) { 
    case tok::FloatNumber: 
      // Это число с плавающей точкой. Строим ветку дерева и считываем 
      // следующий токен
      result = new FloatExprAST(CurPos.getLocation(),
                                strtod(CurPos->getLiteral().data(), nullptr)); 
      ++CurPos; 
      return result; 

    case tok::IntNumber: 
      // Это целочисленная константа. Строим ветку дерева и считываем 
      // следующий токен
      result = new IntExprAST(CurPos.getLocation(), 
                              atoi(CurPos->getLiteral().data())); 
      ++CurPos; 
      return result; 

    case tok::Identifier: 
      // Это обращение к переменной или параметру функции. Строим ветку дерева 
      // и считываем следующий токен
      result = new IdExprAST(CurPos.getLocation(), CurPos->getIdentifier()); 
      ++CurPos; 
      return result; 

    case tok::OpenParen: 
      // Это выражение заключенное в скобки, считываем "(" и переходим к 
      // следующему токену
      ++CurPos; 
      // Считываем выражение в скобках
      result = parseExpr(); 
      // Проверяем наличие ")"
      check(tok::CloseParen); 
      return result; 

    default: 
      // Сообщаем об ошибке
      getDiagnostics().report(CurPos.getLocation(),
                              diag::ERR_ExpectedExpression); 
      return nullptr; 
  } 
}

Следующий вид выражений, это постфиксные операции, такие как ++ и --, а так же вызов функции:

/// call-arguments 
///   ::= assign-expr 
///   ::= call-arguments ',' assign-expr 
/// postfix-expr 
///   ::= primary-expr 
///   ::= postfix-expr '++' 
///   ::= postfix-expr '--' 
///   ::= postfix-expr '(' call-arguments ? ')'
ExprAST *Parser::parsePostfixExpr() { 
   // Считываем выражение (константу, идентификатор или выражение в скобках)
  ExprAST *result = parsePrimaryExpr(); 
 
  // Пытаемся найти постфиксные операторы или вызов функции
  for (;;) { 
    llvm::SMLoc loc = CurPos.getLocation(); 

    switch (int op = CurPos->getKind()) { 
      case tok::PlusPlus: 
      case tok::MinusMinus: 
        // Это "++" или "--". Создаем ветвь дерева в виде выражения с двумя 
        // операндами, но в качестве второго оператора указываем nullptr (по
        // аналогии с постфиксными операторами в C++)
        result = new BinaryExprAST(loc, op, result, nullptr); 
        // Считываем "++" или "--"
        ++CurPos; 
        continue; 

      case tok::OpenParen: { 
        // Это вызов функции. Пропускаем "("
        ++CurPos; 

        ExprList args; 

        if (CurPos != tok::CloseParen) { 
          // Это не ")", значит у нас есть аргументы для вызова функции
          for (;;) { 
            // Считываем аргумент и добавляем его к списку аргументов
            ExprAST *arg = parseAssignExpr(); 
            args.push_back(arg); 

            if (CurPos != tok::Comma) { 
              // Если это не ",", то у нас больше нет аргументов для вызова 
              // функции
              break; 
            } 
           // Пропускаем ","
            ++CurPos; 
          } 
        } 
       // Проверяем наличие ")" и строим ветку дерева для вызова функции
        check(tok::CloseParen); 
        result = new CallExprAST(loc, result, args); 
        continue; 
      } 

      default: 
        // Больше нет никаких постфиксных операторов. Возвращаем 
        // результирующее выражение 
        return result; 
    } 
  } 
}

Следующий вид выражений, это выражения с одним операндом:

/// unary-expr 
///   ::= postfix-expr 
///   ::= '+' unary-expr 
///   ::= '-' unary-expr 
///   ::= '++' unary-expr 
///   ::= '--' unary-expr 
///   ::= '~' unary-expr 
///   ::= '!' unary-expr
ExprAST *Parser::parseUnaryExpr() { 
  ExprAST *result = nullptr; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (int op = CurPos->getKind()) { 
    case tok::Plus: 
    case tok::Minus: 
    case tok::PlusPlus: 
    case tok::MinusMinus: 
    case tok::Not: 
    case tok::Tilda: 
      // Пропускаем оператор и считываем следующий выражение с одним операндом
      ++CurPos; 
      result = parseUnaryExpr(); 
      // Строим ветку дерева для выражения с одним операндом на основе 
      // имеющейся информации
      return new UnaryExprAST(loc, op, result); 

    default: 
      // Нет никаких унарных операторов, считываем постфиксное выражение
      return parsePostfixExpr(); 
  } 
}

Следующими идут выражения с двумя аргументами. Тут уже все становится интересным. Есть два варианта реализации, для каждой группы операторов вводить отдельную функцию, которая делает разбор и анализ данного типа операций (что увеличивает глубину рекурсии и количество схожего кода, т. к. все эти операции очень похожи друг на друга), либо использовать вариант с разборам на основе приоритета операций и их ассоциативности. Мы будем использовать вариант с приоритетом операций. Для начала опишем список всех доступных нам приоритетов (они расположены в порядке возрастания приоритета операции, приоритет операций в нашем языке схож с тем, который есть в языке C++ и некоторых других):

enum OpPrecedenceLevel { 
  OPL_Unknown = 0,        ///< Не является оператором
  OPL_Comma = 1,          ///< , 
  OPL_Assignment = 2,     ///< =
  OPL_Conditional = 3,    ///< ? 
  OPL_LogicalOr = 4,      ///< || 
  OPL_LogicalAnd = 5,     ///< && 
  OPL_InclusiveOr = 6,    ///< | 
  OPL_ExclusiveOr = 7,    ///< ^ 
  OPL_And = 8,            ///< & 
  OPL_Equality = 9,       ///< ==, != 
  OPL_Relational = 10,    ///<  >=, <=, >, < 
  OPL_Shift = 11,         ///< <<, >> 
  OPL_Additive = 12,      ///< -, + 
  OPL_Multiplicative = 13 ///< *, /, % 
};

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

OpPrecedenceLevel getBinOpPrecedence(tok::TokenKind op) { 
  switch (op) { 
    case tok::Greater: 
    case tok::Less: 
    case tok::GreaterEqual: 
    case tok::LessEqual: 
      return OPL_Relational; 

    case tok::LShift: 
    case tok::RShift: 
      return OPL_Shift; 

    case tok::Comma: 
      return OPL_Comma; 
 
    case tok::Assign: 
      return OPL_Assignment; 

    case tok::Question: 
      return OPL_Conditional; 

    case tok::LogOr: 
      return OPL_LogicalOr; 

    case tok::LogAnd: 
      return OPL_LogicalAnd; 

    case tok::BitOr: 
      return OPL_InclusiveOr; 

    case tok::BitXor: 
      return OPL_ExclusiveOr; 

    case tok::BitAnd: 
      return OPL_And; 

    case tok::Equal: 
    case tok::NotEqual: 
      return OPL_Equality; 

    case tok::Plus: 
    case tok::Minus: 
      return OPL_Additive; 

    case tok::Mul: 
    case tok::Div: 
    case tok::Mod: 
      return OPL_Multiplicative; 

    default: 
      return OPL_Unknown; 
  } 
}

Теперь рассмотрим реализацию самого разбора выражений с двумя операндами:

/// expr 
///   ::= assign-expr 
///   ::= expr ',' assign-expr 
/// assign-expr 
///   ::= cond-expr 
///   ::= cond-expr '=' assign-expr 
/// cond-expr 
///   ::= assoc-expr 
///   ::= assoc-expr '?' expr ':' cond-expr 
/// op 
///   ::= '||' | '&&' | '|' | '^' | '&' | '==' | '!=' | '>=' | '<=' | '>'
///   ::= '<' | '<<' | '>>' | '-' | '+' | '*' | '/' | '%' 
/// assoc-expr 
///   ::= unary-expr 
///   ::= assoc-expr op unary-expr
ExprAST *Parser::parseRHS(ExprAST *lhs, int maxPrec) { 
  OpPrecedenceLevel newPrec = getBinOpPrecedence(CurPos->getKind()); 

  for (;;) { 
    tok::TokenKind tok = CurPos->getKind(); 
    llvm::SMLoc loc = CurPos.getLocation(); 
    // Если у текущего оператора приоритет ниже того, максимального приоритета
    // для данного выражения, то мы возвращаем выражение ранее полученное в 
    // процессе разбора
    if (newPrec < maxPrec) { 
      return lhs; 
    } 
   // Пропускаем считанный оператор
    ++CurPos; 

    // Проверяем на то, что это ? : т. к. у нас для этого оператора есть 
    // специальная обработка 
    if (newPrec == OPL_Conditional) { 
      ExprAST *thenPart = nullptr; 
      
      if (CurPos == tok::Colon) { 
        // Если это ":", то возвращаем ошибку, т. к. у нас отсутствует 
        // выражение для варианта, когда условие истинно
        getDiagnostics().report(CurPos.getLocation(), 
                                diag::ERR_ExpectedExpressionAfterQuestion); 
      } else { 
        // Считываем выражение для варианта, когда условие истинно
        thenPart = parseExpr(); 
      } 
     // Проверяем наличие ":" после выражения
      check(tok::Colon); 
     // Считываем выражение после ":" и создаем дерево для оператора
      ExprAST *elsePart = parseAssignExpr(); 
      lhs = new CondExprAST(loc, lhs, thenPart, elsePart); 
     // Получаем приоритет следующего токена и переходим к следующей итерации
      newPrec = getBinOpPrecedence(CurPos->getKind()); 
      continue; 
    } 
    // Разбор выражения для правого операнда
    ExprAST *rhs = parseUnaryExpr(); 
    // Получение приоритета следующего токена и проверка на то, что это 
    // оператор имеет правую ассоциативность
    OpPrecedenceLevel thisPrec = newPrec; 
    newPrec = getBinOpPrecedence(CurPos->getKind()); 
    bool isRightAssoc = (thisPrec == OPL_Assignment); 
    // Проверяем, что приоритет текущего оператора меньше приоритета нового 
    // оператора, а так же если их приоритеты совпадают, то оператор должен
    // иметь правую ассоциативность
    if (thisPrec < newPrec || (thisPrec == newPrec && isRightAssoc)) { 
      if (isRightAssoc) { 
        // Для операторов с правой ассоциативностью перед создания дерева для 
        // текущего выражения, мы должны сперва рекурсивно вызвать и построить
        // дерево для правой части выражения с таким же приоритетом
        rhs = parseRHS(rhs, thisPrec); 
      } else { 
        // Для операторов с левой ассоциативностью мы должны сначала построить
        // дерево для правой части выражения, но с более высоким приоритетом
        rhs = parseRHS(rhs, (OpPrecedenceLevel)(thisPrec + 1)); 
      } 
      // Получаем приоритет текущего токена, для последующего разбора
      newPrec = getBinOpPrecedence(CurPos->getKind()); 
    } 
    // Создание дерева для текущего выражения
    lhs = new BinaryExprAST(loc, tok, lhs, rhs); 
  } 
}

И в заключении для выражений у нас остались 2 функции, одна для выражений, в которых не может встречаться "," (например для обработки аргументов для вызова функции и некоторых других мест) и другая для случаев, где они допустимы:

ExprAST *Parser::parseAssignExpr() { 
  ExprAST *lhs = parseUnaryExpr(); 
  return parseRHS(lhs, OPL_Assignment); 
} 

ExprAST *Parser::parseExpr() { 
  ExprAST *lhs = parseUnaryExpr(); 
  return parseRHS(lhs, OPL_Comma); 
}

Для парсинга типа переменной, параметра функции или типа возвращаемого значения будет использоваться слудующий метод:

/// type ::= 'int' | 'float' | 'void'
TypeAST *Parser::parseType() { 
  TypeAST *type = nullptr; 
  bool isVoid = false; 
  llvm::SMLoc loc = CurPos.getLocation(); 

  switch (CurPos->getKind()) { 
    case tok::Int: 
      ++CurPos; 
      type = BuiltinTypeAST::get(TypeAST::TI_Int); 
      break; 

    case tok::Float: 
      ++CurPos; 
      type = BuiltinTypeAST::get(TypeAST::TI_Float); 
      break; 

    case tok::Void: 
      ++CurPos; 
      type = BuiltinTypeAST::get(TypeAST::TI_Void); 
      isVoid = true; 
      break; 

    default: 
      getDiagnostics().report(CurPos.getLocation(), diag::ERR_InvalidType); 
      return nullptr; 
  } 

  if (type == BuiltinTypeAST::get(TypeAST::TI_Void)) { 
    // Запрещаем использовать "void" в качестве типа, без дополнительных 
    // модификаторов
    getDiagnostics().report(loc, diag::ERR_VoidAsNonPointer); 
    return nullptr; 
  } 

  return type; 
}

Для разбора прототипа функции мы будем использовать следующую функцию (она будет применяться в нескольких местах):

/// 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; 
  } else { 
    check(tok::Identifier); 
  } 
  // Проверяем наличие "("
  check(tok::OpenParen); 

  //  Проверяем, что у прототипа есть параметры
  if (CurPos != tok::CloseParen) { 
    // Производим анализ всех параметров функции
    for (;;) { 
      Name *paramName = nullptr; 

      if (CurPos == tok::Identifier) { 
        // Параметр всегда должен начинаться с имени параметра. Сохраняем 
        // его и переходим к следующему токену
        paramName = CurPos->getIdentifier(); 
        ++CurPos; 

        // Особая обработка для "_" - анонимный параметр
        if (strcmp(paramName->Id, "_") == 0) { 
          paramName = nullptr; 
        } 
      } else { 
        // Сообщаем об ошибке
        check(tok::Identifier); 
      } 
      // После имени параметра всегда должно быть ":"
      check(tok::Colon); 
      // Получаем тип для параметра функции
      TypeAST *type = parseType(); 
      // Добавляем новый параметр для прототипа на основе полученной ранее 
      // информации
      params.push_back(new ParameterAST(type, paramName)); 

      if (CurPos != tok::Comma) { 
        // Если это не "," то заканчиваем обработку параметров 
        break; 
      } 
      // Считываем "," и переходим к следующему токену 
      ++CurPos; 
    } 
  } 
  // Проверяем на наличие ")"
  check(tok::CloseParen); 
  // Проверяем на наличие ":" и считываем тип возвращаемого значения
  // Примечание: мы не допускаем ":" "void"
  if (CurPos == tok::Colon) { 
    ++CurPos; 
    returnType = parseType(); 
  } 
  // Строим элемент дерева для прототипа функции
  returnType = new FuncTypeAST(returnType, params); 
  return new FuncDeclAST(loc, returnType, name, nullptr, Tok); 
}

Для разбора объявления функции будет использована следующая функция:

/// func-decl ::= 'fn' func-proto block-stmt
SymbolList Parser::parseFuncDecl() { 
  // Чтение прототипа функции
  SymbolList result; 
  FuncDeclAST *decl = (FuncDeclAST *)parseFuncProto(); 
 
  if (CurPos != tok::BlockStart) { 
    // Отсутствие "{" является ошибкой
    getDiagnostics().report(CurPos.getLocation(), diag::ERR_ExpectedFuncBody); 
  } else { 
    // Считываем тело функции
    StmtAST *body = parseStmt(); 
    // Добавляем тело к прототипу функции
    decl->Body = body; 
    // Добавляем созданное объявление функции к результирующим объявлениям
    result.push_back(decl); 
  } 

  return result; 
}

Для разбора объявлений используется следующая функция (пока она может понимать только функции, но позже мы добавим классы и структуры):

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

    switch (int Tok = CurPos->getKind()) { 
      case tok::Def: 
        // Объявление функции. Считываем объявление функции и добавляем в 
        // список объявлений
        tmp = parseFuncDecl(); 
        result.push_back(tmp.pop_back_val()); 
        continue; 

      case tok::EndOfFile: 
        break; 

      default: 
        break; 
    } 

    break; 
  } 

  return result; 
}

Разбор модуля со всеми верхнеуровневыми объявлениями:

/// module-decl ::= decls
ModuleDeclAST *Parser::parseModule() { 
  // Вызываем функцию разбора объявлений
  SymbolList decls = parseDecls(); 
  // Любой модуль должен заканчиваться символом конца файла (значит в нем нет 
  // не разобранных конструкций
  if (CurPos != tok::EndOfFile) { 
    getDiagnostics().report(CurPos.getLocation(),
                            diag::ERR_ExpectedEndOfFile); 
    return nullptr; 
  } 
  // Конструирование дерева для модуля
  return new ModuleDeclAST(getDiagnostics(), decls); 
}

Разбор объявлений для локальных переменных и блока инициализации в цикле "for":

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

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

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

  return result; 
}

Вспомогательная функция, которая считывает инструкцию и если это не блочный элемент (набор инструкций между "{" и "}"), то создает новый элемент дерева в виде блочного элемента:

StmtAST *Parser::parseStmtAsBlock() { 
  // Чтение инструкции
  llvm::SMLoc loc = CurPos.getLocation(); 
  StmtAST *result = parseStmt(); 

  if (isa<BlockStmtAST>(result)) { 
    // Это уже блочный элемент, возвращаем его
    return result; 
  } 

  // Создаем новый блочный элемент с одной инструкцией
  StmtList body; 
  body.push_back(result); 
  return new BlockStmtAST(loc, body); 
}

Разбор инструкций языка:

/// 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::Var: 
      // Объявление локальных переменных
      ++CurPos; 
      return new DeclStmtAST(loc, parseDecl(true)); 

    // Для упрощения анализа мы знаем с каких токенов может начинаться
    // арифметические выражение, поэтому мы можем обработать их здесь
    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: { 
      // Чтение выражение
      ExprAST *expr = parseExpr();
      // Инструкция с выражением должна заканчиваться ";" 
      check(tok::Semicolon); 
      // Создаем ветвь дерева для инструкции с арифметическим выражением
      return new ExprStmtAST(loc, expr); 
    } 

    case tok::If: { 
      // Это инструкция ветвления "if"
      check(tok::If); 
      // Считываем выражение — условие
      ExprAST *expr = parseExpr(); 

      if (CurPos != tok::BlockStart) {
        // Ветки ветвления должны начинаться с "{", т. е. должны быть блочным 
        // элементом
        check(tok::BlockStart); 
      } 
      // Считываем ветку если условие истинно
      StmtAST *thenPart = parseStmtAsBlock(); 
      StmtAST *elsePart = nullptr; 

      if (CurPos == tok::Else) { 
        // Если у нас есть "else", то пропускаем его и считываем тело ветки
        ++CurPos; 

        if (CurPos != tok::BlockStart) { 
          // Ветки ветвления должны начинаться с "{", т. е. должны быть 
          // блочным элементом
          check(tok::BlockStart); 
        } 
        // Считываем ветку если условие ложно
        elsePart = parseStmtAsBlock(); 
      } 
      // Создаем ветку дерева для инструкции ветвления "if"
      return new IfStmtAST(loc, expr, thenPart, elsePart); 
    } 

    case tok::While: { 
      // Это цикл "while"
      check(tok::While); 
      // Считываем выражение — условие цикла
      ExprAST *expr = parseExpr(); 

      if (CurPos != tok::BlockStart) { 
        // Тело цикла должно быть блочным элементом
        check(tok::BlockStart); 
      } 
      // Считываем тело цикла и создаем ветку дерева для инструкции "while"
      result = parseStmtAsBlock(); 
      return new WhileStmtAST(loc, expr, result); 
    } 

    case tok::For: { 
      // Это цикл "for"
      check(tok::For); 

      ExprAST *initExpr = nullptr, *condExpr = nullptr, *postExpr = nullptr; 
      SymbolList decls; 

      if (CurPos != tok::Semicolon) { 
        // У цикла есть блок инициализации цикла
        if (CurPos == tok::Var) { 
           // Это объявление переменных цикла
          ++CurPos; 
          decls = parseDecl(true); 
        } else { 
          // Это обычное выражение
          initExpr = parseExpr(); 
          check(tok::Semicolon); 
        } 
      } else { 
        // Блок инициализации всегда должен заканчиваться ";"
        check(tok::Semicolon); 
      } 

      if (CurPos != tok::Semicolon) { 
        // У нас есть условие цикла, считываем его
        condExpr = parseExpr(); 
      } 
      // После условия цикла всегда должна быть ";"
      check(tok::Semicolon); 

      if (CurPos != tok::BlockStart) { 
        // У нас есть выражение, которое должно быть выполнено после каждой 
        // итерации
        postExpr = parseExpr(); 
      } 

      if (CurPos != tok::BlockStart) { 
        // Тело цикла всегда должно быть блочным элементом
        check(tok::CloseParen); 
      } 
      // Чтение тела цикла и конструирование ветви дерева для инструкции 
      // "for"
      result = parseStmtAsBlock(); 
      return new ForStmtAST(loc, initExpr, decls, condExpr, postExpr,
                            result); 
    } 

    case tok::Break: 
      // Считываем "break" ";" и создаем ветку дерева для инструкции 
      // досрочного выхода из цикла "break"
      check(tok::Break); 
      check(tok::Semicolon); 
      return new BreakStmtAST(loc); 

    case tok::Continue: 
      // Считываем "continue" ";" и создаем ветку дерева для инструкции
      // перехода к следующей итерации цикла "continue"
      check(tok::Continue); 
      check(tok::Semicolon); 
      return new ContinueStmtAST(loc); 

    case tok::Return: { 
      // Это инструкция возврата из функции
      check(tok::Return); 

      if (CurPos == tok::Semicolon) { 
        // Если это ";", то у нас нет выражение, возможно это выход из 
        // функции с типом возвращаемого значения "void". Считываем ";" и 
        // строим ветвь дерева для "return"
        ++CurPos; 
        return new ReturnStmtAST(loc, nullptr); 
      } 
      // Считываем выражение для возврата
      ExprAST *expr = parseExpr(); 
      // После выражения всегда должен быть ";". Считываем и строим ветвь 
      // дерева для "return"
      check(tok::Semicolon); 
      return new ReturnStmtAST(loc, expr); 
    } 

    case tok::BlockStart: { 
       // Это блочный элемент
      StmtList stmts; 
      // Считываем "{"
      ++CurPos; 
      // И считываем все инструкции, пока мы не встретим "}" или конец файла
      while (CurPos != tok::BlockEnd && CurPos != tok::EndOfFile) { 
        result = parseStmt(); 
        stmts.push_back(result); 
      } 
      // Проверяем на наличие "}" и создаем ветвь дерева для блочного 
      // элемента
      check(tok::BlockEnd); 
      return new BlockStmtAST(loc, stmts); 
    } 

    case tok::Semicolon: 
      // Это пустое выражение, просто ";". Строим дерево для пустого 
      // выражения
      ++CurPos; 
      return new ExprStmtAST(loc, nullptr); 

    default: 
      // Все остальные случаи являются ошибкой
      getDiagnostics().report(CurPos.getLocation(), 
                              diag::ERR_InvalidStatement); 
      return nullptr; 
  } 
}

Для упрощения объявления прототипов функций для внутреннего использования (для подключения функций из языка C++) будем использовать следующую функцию:

SymbolAST *parseFuncProto(llvm::StringRef Proto) { 
  llvm::SourceMgr SrcMgr; 
  DiagnosticsEngine Diags(SrcMgr); 
  // Создаем буфер для лексического анализа и инициализируем его переданной 
  // строкой
  std::unique_ptr<llvm::MemoryBuffer> Buff = 
    llvm::MemoryBuffer::getMemBuffer(Proto); 
  // Добавляем файл для чтения
  SrcMgr.AddNewSourceBuffer(std::move(Buff), llvm::SMLoc()); 

  Lexer Lex(SrcMgr, Diags); 
  Parser P(&Lex); 
  // Парсим прототип функции
  return P.parseFuncProto(); 
}

Для разбора файла используется следующая функция:

ModuleDeclAST* ModuleDeclAST::load(SourceMgr &SrcMgr,
                                   DiagnosticsEngine &Diags,
                                   StringRef fileName) {
  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
    FileOrErr = llvm::MemoryBuffer::getFile(fileName);

  if (std::error_code BufferError = FileOrErr.getError()) {
    llvm::WithColor::error(llvm::errs(), "simple")
      << "Error reading " << fileName << ": "
      << BufferError.message() << "n";
  }

  // Добавляем файл для чтения
  SrcMgr.AddNewSourceBuffer(std::move(*FileOrErr),
                            llvm::SMLoc());

  Lexer Lex(SrcMgr, Diags);
  Parser P(&Lex);
  
  // Парсим содержимое модуля
  return P.parseModule();
}

Заключение

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

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

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

  1. Compilers: Principles, Techniques, and Tools by Alfred V. Aho (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author)

  2. Let's Build a Compiler, by Jack Crenshaw

  3. LLVM Techniques, Tips, and Best Practices Clang and Middle-End Libraries By Min-Yih Hsu

  4. Kaleidoscope: Compiling to Object Code

  5. https://llvm.godbolt.org/

  6. How to set up LLVM-style RTTI for your class hierarchy

Автор: Илья Моисеенко

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js