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

Автор оригинала: Chris Lattner, Erick Tryzelaar
  • Перевод
Добро пожаловать в учебник «Создание языка программирования с LLVM». Этот учебник знакомит вас с созданием простейшего языка программирования, и при этом показывает, каким оно может быть легким и интересным, а также даёт вам начальные знания, которые вы затем сможете применить на других языках программирования. Код в этом учебнике также может быть использован в качестве стартовой площадки для ваших творений с помощью LLVM.

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

Полезно отметить заранее, что этот учебник действительно обучает некоторым техникам компиляции и специфике LLVM, но не обучает современным принципам разработки программного обеспечения. На практике это означает, что мы будем использовать максимально упрощённые и сокращённые решения, чтобы упростить изложение. Так, например, код работы с памятью повсюду использует глобальные переменные, не используя прекрасные шаблоны проектирования, такие как Visitor и другие — это не лучший способ, но зато это очень просто и понятно. Если вы разбираетесь в коде и используете его в качестве основы для будущих проектов, то исправление таких недостатков не будет для вас проблемой.

Я попытался скомпоновать этот учебник таким образом, чтобы вы легко могли пропустить части, с которыми уже знакомы или которые вам не интересны. Структура учебника такова:
  • Глава №1: Введение в язык Kaleidoscope и определение его лексического анализатора — Покажет, в каком направлении мы двигаемся и базовую функциональность, которую нам предстоит разработать. Для того, чтобы этот учебник был понятнее, а примеры ближе к реальности, мы решили осуществлять все только на чистом C++ без использования парсер-генераторов. LLVM, конечно же, прекрасно работает с такими инструментами, так что вы запросто можете использовать один из них.
  • Глава №2: Реализация парсера и AST — С готовым лексическим анализатором мы уже можем поговорить о методах парсинга и основах построения AST. Это руководство описывает анализ рекурсивным спуском и разбор приоритета операторов. Ничто в Главах 1 или 2 не относится к LLVM, код даже не связывается с LLVM в этих главах. :)
  • Глава №3: Кодогенерация LLVM IR — С готовым AST мы можем показать, как легко на самом деле генерировать LLVM IR.
  • Глава №4: Добавление JIT и поддержка оптимизатора — Так как многие люди заинтересованы в использовании LLVM как JIT, мы погрузиться в него и покажем вам 3 шага для добавления поддержки JIT. LLVM также полезен и во многих других отношениях, но это один из самых простых и «сексуальных» способов продемонстрировать свою силу. :)
  • Глава №5: Расширение языка: Поток управления — Теперь, когда у нас есть работающий язык программирования, мы сможем расширить его управляющими конструкциями (if/then/else и цикл «for»). Это дает нам возможность говорить о простом построении SSA и управлении потоком выполнения.
  • Глава №6: Расширение языка: Определяемые пользователем операторы — это простая, но интересная глава, рассказывающая о расширении языка, которое позволит пользователю определять свои собственные унарные и бинарные операторы (с назначаемым приоритетом!). Это позволит нам построить значительный кусок «языка программирования» как библиотеку подпрограмм.
  • Глава №7: Расширение языка: Изменяемые переменные — Эта глава рассказывает о добавлении пользовательских локальных переменных с помощью оператора присваивания. Самое интересное здесь — то, как легко и тривиально это строится в SSA-форме: и нет, LLVM НЕ требует использования SSA-формы в вашем фронт-энде!
  • Глава №8: Заключение и другие вкусности LLVM — Эта глава завершает серию, рассказывая о возможных способах расширения языка, а также включает в себя кучу ссылок на различные темы, такие как поддержка сборки мусора (Garbage Collection), исключения, отладка, поддержка «спагетти-стека» («spaghetti stacks»), и кучу других советов и трюков.
К завершению учебника, мы написали чуть менее 700 строк кода без учёта комментариев и пустых строк. С помощью этого небольшого количества кода, мы создали очень даже неплохой компилятор для нетривиального языка программирования, включающий рукописный лексический анализатор, парсер, AST, а также поддержку кодогенерации с JIT. В то время как у других систем есть учебники в стиле «Hello, World», ширина этого учебника является отличным свидетельством мощи LLVM. Если вы заинтересованы в построении языков и компиляторов, вы обязательно должны прочесть этот учебник.

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

Язык Kaleidoscope

Этот учебник проиллюстрирует игрушечный язык программирования, который мы назвали "Kaleidoscope" (название происходит от трёх греческих слов: «красивый», «вид» и «смотрю, наблюдаю»). Kaleidoscope является процедурным языком, что позволяет определять функции, использовать условия, математику и т.д. В ходе изучения мы расширим Kaleidoscope для поддержки конструкций if/then/else, циклов, пользовательских операторов, JIT-компиляции с простым консольным интерфейсом и т.д.

Для простоты в Kaleidoscope есть только один тип данных — 64-битное число с плавающей точкой (как «double» в языке C). Таким образом, все значения — это действительные числа двойной точности и язык не требует объявления типов. Это делает язык очень красивым и упрощает синтаксис. Например, следующий простой пример вычисляет числа Фибоначчи:

# Расчет x-го числа Фиббоначчи
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

# Это выражение расчитывает 40-е число.
fib(40)

Мы также позволили Kaleidoscope вызывать стандартные библиотечные функции (LLVM JIT делает это вполне тривиальным). Это значит, что вы можете использовать ключевое слово «extern» для объявления функции перед её использованием (это также полезно для взаимно рекурсивных функций). Например:

extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

atan2(sin(.4), cos(42))

Более интересный пример приведён в Главе 6, где мы напишем на Kaleidoscope небольшое приложение, которое отображает множество Мандельброта в разных степенях приближения.

А теперь погрузимся в реализацию этого языка!

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

Когда дело доходит до реализации языка программирования, первое, что необходимо, так это способность обрабатывать текстовый файл и распознавать в нём код. Традиционный способ сделать это состоит в использовании "лексического анализатора" (или «сканера»), для разбития входного потока на «токены». Каждый токен возвращаемый лексическим анализатором включает единицу кода и потенциально некоторые метаданные (например, числовое значение). Во-первых, мы определим возможности:


// Лексический анализатор возвращает токены [0-255], если это неизвестны, 
// иначе одну из известных единиц кода
enum Token {
  tok_eof = -1,

  // команды (ключевые слова)
  tok_def = -2, tok_extern = -3,

  // операнды (идентификаторы, числа)
  tok_identifier = -4, tok_number = -5,
};

static std::string IdentifierStr;  // Заполняется, если tok_identifier (если токен - идентификатор)
static double NumVal;              // Заполняется, если tok_number (если токен - число)

Каждый токен, возвращаемый нашими лексическим анализатором будет либо одним из значений перечисления Token или это будет «неизвестное» вроде символа "+", которое возвращается в качестве значения ASCII. Если текущий токен является идентификатором, то глобальная переменная IdentifierStr содержит имя идентификатора. Если текущий токен является числовым литералом (например, 1.0), NumVal содержит его значение. Обратите внимание, что мы используем глобальные переменные для простоты, но это далеко не лучший выбор для реального применения :).

Фактически, наш лексический анализатор реализован одной функцией с именем gettok. Функция Gettok при вызове возвращает следующий токен из стандартного потока ввода. Её определение начинается так:


/// gettok - Возвращает следующий токен из стандартного потока ввода.
static int gettok() {
  static int LastChar = ' ';

  // Пропускаем пробелы.
  while (isspace(LastChar))
    LastChar = getchar();

gettok вызывает C-функцию getchar(), чтобы читать символы по одному из стандартного ввода. Она распознает их и сохраняет последний прочитанный символ в LastChar, но не обрабатывает. Первое, что она должна делать — это игнорировать пробелы между лексемами. Это достигается в вышеприведённом цикле.

Следующее действие gettok — это распознание идентификаторов и специальных ключевых слов, таких как «def». Kaleidoscope делает это с помощью этого простого цикла:


  if (isalpha(LastChar)) { // идентификатор: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = getchar())))
      IdentifierStr += LastChar;

    if (IdentifierStr == "def") return tok_def;
    if (IdentifierStr == "extern") return tok_extern;
    return tok_identifier;
  }

Обратите внимание, что этот код собирает глобальную переменную «IdentifierStr», пока анализирует идентификатор. Кроме того ключевые слова языка проверяются в этом же цикле. Для численных значений всё аналогично:


  if (isdigit(LastChar) || LastChar == '.') {   // Число: [0-9.]+
    std::string NumStr;
    do {
      NumStr += LastChar;
      LastChar = getchar();
    } while (isdigit(LastChar) || LastChar == '.');

    NumVal = strtod(NumStr.c_str(), 0);
    return tok_number;
  }

Это довольно простой код для обработки входных данных. При чтении числового значения, мы используем C-функцию strtod для преобразования его в числовое значение, которые мы сохраняем в NumVal. Отметим, что здесь не происходит достаточной проверки ошибок: значение «1.23.45.67» будет считано и обработано так, как если бы вы ввели в «1.23». Вы легко можете дополнить код проверкой на подобные ошибки :). Теперь разберёмся с комментариями:


  if (LastChar == '#') {
    // Комментарий до конца строки.
    do LastChar = getchar();
    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
    
    if (LastChar != EOF)
      return gettok();
  }

Определив комментарий, мы пропускаем символы до конца строки, а затем возвращаем следующий токен. Затем, если ввод не совпадает с одним из указанных выше случаев, то это либо оператор вроде "+", либо конец файла. Они обрабатываются этим кодом:


  // Проверка конца файла.
  if (LastChar == EOF)
    return tok_eof;
  
  // В противном случае просто возвращаем символ как значение ASCII
  int ThisChar = LastChar;
  LastChar = getchar();
  return ThisChar;
}

При этом, мы имеем полноценный лексический анализатор для языка Kaleidoscope (полный листинг кода лексического анализатора доступен в следующей главе из учебника). Дальше мы разработаем простой синтаксический анализатор, который используем для построения Abstract Syntax Tree. Затем мы сможем использовать лексический и синтаксический анализатор вместе.

UPD.
Полезные ссылки, которые пригодятся в изучении:
Поделиться публикацией

Комментарии 27

    +3
    Очень интересно и познавательно. Жду продолжения.
      0
      Кстати, возник вопрос:
      Если в языке только один тип данных double, то как будут храниться, например, строки? В виде массива, в каждой ячейке которого будет ASCII код? Не слишком ли «жирно» по памяти выходит?
        +1
        Это же ИГРУШЕЧНЫЙ язык, показывающий возможности LLVM.
          0
          А можно рассчитывать, что в дальнейшем язык будет модифицирован для работы с несколькими типами? Или он создается только для демонстрации?
            0
            Я думаю, что достаточно добавить булев тип, строки и массивы и можно будет нормально программировать.
              +1
              В Java и C# булев тип, с точки зрения виртуальной машины, является типобезопасным синонимом3 int32(0). А в Erlang нет строк, зато есть массивы int'ов, которые можно вывести в качестве строки. Это, конечно, не очень удобно, но работает.

              А вот массивы было бы неплохо добавить, да :)
                0
                главное что автор показал как сделать простой язык, все эти нововведения не сложно самому добавить.
                0
                В оригинале насколько я помню до этого дело не дошло.
                  0
                  Он создан только для демонстрации… Он обучает работать с LLVM и не предназначен для реального программирования. Но добавить в него ещё типы данных после прочтения всего учебника не составит никакого труда.
              0
              Спасибо! Вы реализуете мою мечту. Всегда хотел сделать свой язык, но никак руки не доходили. Может чему-то у Вас научусь.
                +1
                Это мечта любого программиста )
                  0
                  Просто если каждый программист начнет делать язык, который будет для него идеальным и программировать только на нем — мир рухнет)))
                    +1
                    То-то сейчас полно быстро развивающихся языков. Видимо, мир в руинах! :)
                      0
                      Да не в том смысле. Просто если бы был сделан реально классный язык, на котором можно сделать буквально всё, удобный, красивый и т.д. — то да, всё замечательно. А если каждый будет делать то, что будет удобно в использовании только ему…

                      Имхо, основная проблема в том, что каждый язык, как правило «заточен» под что то одно, и у каждого есть свои плюсы, свои минусы. То есть если мы хотим быстро сделать достаточно гибкий web-сервис — мы сядем за Python, потеряв, в частности, в производительности. Если мы хотим сделать анализ большого объёма данных за короткое время — мы сядем за сложный и трудный для понимания Perl. Нет ничего одинаково подходящего и для одной, и для другой задачи.

                      С одной стороны, это хорошо, что для нужной задачи у нас есть нужный инструмент. Но с другой, когда нам в одном проекте нужно соединить и то, и другое, возникают сложности. Плюс опять же, нет программистов-универсалов, всё-таки каждый более спец в своей области.
                        0
                          0
                          упс, не та ветка…
                            0
                            комментарий — не воробей)
                        0
                        Можно написать себе свой собственный язык под существующую виртуальную машину, типа .NET, JVM, Parrot и т.д. и писать на нем, используя совместимость на уровне байткода. Хотя рано или поздно большинству авторов таких языков надоедает их развивать.
                      +4
                      Не поверите — моя тоже. Писал два года виртуальную машину на C++, потом она все же заработала, но пропал интерес. Взялся писать на .NET — за два месяца написал работающий .NET-совместимый язык. Можете посмотреть примеры и исходные коды — вот страничка на кодеплексе. Если возникнет желание посодействовать в дизайне и реализации версии 2.0 — милости прошу :)
                        +1
                        Можно попробовать flex/bison, относительно просто можно создать лексический и синтаксический анализатор своего языка.
                        +1
                        Может быть в блог «Компиляторы»?
                          0
                          Действительно, перенёс, спасибо, этот блог более уместен.
                          +1
                          Любой желающий естественно сможет выяснить, что же это за аббревиатура такая LLVM, но неужели раз это учебник нельщя было в первом же абзаце расшифровать? А так ждём-с, спасибо!
                            0
                            Low Level Virtual Machine. Сразу всё стало понятно, правда? Все мучительные вопросы получили ответы.
                              +1
                              Добавил в конце несколько ссылок для изучения
                              +6
                              Хочу поделиться опытом.

                              На протяжении около десяти лет работал в проекте где было реализовано 4 языка (язык для написания веб страниц, ибо Perl был какой-то мутный, макропроцессор, ибо стандартный макропроцессор C какой-то недостаточно крутой, язык описания архитектуры процессоров и т.п.). Оглядываясь назад, понятно, что языки делались потому что было много «сильных» программистом и потому что с появлением средств типа ANTLR создание парсера языка стало ну совсем плевым делом. Ну а написать свой язык это всегда круто и интересно:)

                              В результате вывод такой, что первая версия делается за несколько дней (или ночей). И казалось бы вот он язык! Но. Один за другим начинают возникать вопросы. Какие нужны встроенные функции? Поддержка арифметики? Типы данных? Структуры? Массивы? Динамические массивы? Документация языка такая, что им может пользоваться кто-то кроме автора (а это могут быть десятки и сотни страниц)? Примеры? Обращение к внешним библиотекам (ну вызов функций, вызов COM). Все эти аспекты зависят от назначения языка, но можете быть уверены, что создавая язык вы вешаете на шею обузу, которую придется нести долгое время. В частности, будте готовы десятки раз отвечать на вопрос «а нахрена вы завели свой язык когда есть PPP». И ваш ответ «мой такой же но удобнее и лучше» вряд ли проканает:)

                              Каждый уважающий себя программист должен сделать язык. Это лучший опыт для того, чтобы научиться программировать на других языках, поскольку становится понятна «кухня», объединяющая различные языки. Но нужно быть готовым отказатся от своего в пользу общего.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое