Добро пожаловать в учебник «Создание языка программирования с LLVM». Этот учебник знакомит вас с созданием простейшего языка программирования, и при этом показывает, каким оно может быть легким и интересным, а также даёт вам начальные знания, которые вы затем сможете применить на других языках программирования. Код в этом учебнике также может быть использован в качестве стартовой площадки для ваших творений с помощью LLVM.
Целью данного учебника является постепенное представление нашего языка, описание его пошагового создания. Это позволит нам охватить достаточно широкий спектр вопросов проектирования языков и использования LLVM, попутно показывая и объясняя код без огромного количества ненужных деталей.
Полезно отметить заранее, что этот учебник действительно обучает некоторым техникам компиляции и специфике LLVM, но не обучает современным принципам разработки программного обеспечения. На практике это означает, что мы будем использовать максимально упрощённые и сокращённые решения, чтобы упростить изложение. Так, например, код работы с памятью повсюду использует глобальные переменные, не используя прекрасные шаблоны проектирования, такие как Visitor и другие — это не лучший способ, но зато это очень просто и понятно. Если вы разбираетесь в коде и используете его в качестве основы для будущих проектов, то исправление таких недостатков не будет для вас проблемой.
Я попытался скомпоновать этот учебник таким образом, чтобы вы легко могли пропустить части, с которыми уже знакомы или которые вам не интересны. Структура учебника такова:
И ещё кое-что: мы ждём от вас, что вы будете расширять язык и играть с ним по своему усмотрению. Возьмите код и начинайте неистово программировать, сойдите с ума, компиляторы не должны вас пугать — ведь это так весело — играть с языками!
Для простоты в Kaleidoscope есть только один тип данных — 64-битное число с плавающей точкой (как «double» в языке C). Таким образом, все значения — это действительные числа двойной точности и язык не требует объявления типов. Это делает язык очень красивым и упрощает синтаксис. Например, следующий простой пример вычисляет числа Фибоначчи:
Мы также позволили Kaleidoscope вызывать стандартные библиотечные функции (LLVM JIT делает это вполне тривиальным). Это значит, что вы можете использовать ключевое слово «extern» для объявления функции перед её использованием (это также полезно для взаимно рекурсивных функций). Например:
Более интересный пример приведён в Главе 6, где мы напишем на Kaleidoscope небольшое приложение, которое отображает множество Мандельброта в разных степенях приближения.
А теперь погрузимся в реализацию этого языка!
Каждый токен, возвращаемый нашими лексическим анализатором будет либо одним из значений перечисления Token или это будет «неизвестное» вроде символа "+", которое возвращается в качестве значения ASCII. Если текущий токен является идентификатором, то глобальная переменная IdentifierStr содержит имя идентификатора. Если текущий токен является числовым литералом (например, 1.0), NumVal содержит его значение. Обратите внимание, что мы используем глобальные переменные для простоты, но это далеко не лучший выбор для реального применения :).
Фактически, наш лексический анализатор реализован одной функцией с именем gettok. Функция Gettok при вызове возвращает следующий токен из стандартного потока ввода. Её определение начинается так:
gettok вызывает C-функцию getchar(), чтобы читать символы по одному из стандартного ввода. Она распознает их и сохраняет последний прочитанный символ в LastChar, но не обрабатывает. Первое, что она должна делать — это игнорировать пробелы между лексемами. Это достигается в вышеприведённом цикле.
Следующее действие gettok — это распознание идентификаторов и специальных ключевых слов, таких как «def». Kaleidoscope делает это с помощью этого простого цикла:
Обратите внимание, что этот код собирает глобальную переменную «IdentifierStr», пока анализирует идентификатор. Кроме того ключевые слова языка проверяются в этом же цикле. Для численных значений всё аналогично:
Это довольно простой код для обработки входных данных. При чтении числового значения, мы используем C-функцию strtod для преобразования его в числовое значение, которые мы сохраняем в NumVal. Отметим, что здесь не происходит достаточной проверки ошибок: значение «1.23.45.67» будет считано и обработано так, как если бы вы ввели в «1.23». Вы легко можете дополнить код проверкой на подобные ошибки :). Теперь разберёмся с комментариями:
Определив комментарий, мы пропускаем символы до конца строки, а затем возвращаем следующий токен. Затем, если ввод не совпадает с одним из указанных выше случаев, то это либо оператор вроде "+", либо конец файла. Они обрабатываются этим кодом:
При этом, мы имеем полноценный лексический анализатор для языка Kaleidoscope (полный листинг кода лексического анализатора доступен в следующей главе из учебника). Дальше мы разработаем простой синтаксический анализатор, который используем для построения Abstract Syntax Tree. Затем мы сможем использовать лексический и синтаксический анализатор вместе.
UPD.
Полезные ссылки, которые пригодятся в изучении:
Целью данного учебника является постепенное представление нашего языка, описание его пошагового создания. Это позволит нам охватить достаточно широкий спектр вопросов проектирования языков и использования 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»), и кучу других советов и трюков.
И ещё кое-что: мы ждём от вас, что вы будете расширять язык и играть с ним по своему усмотрению. Возьмите код и начинайте неистово программировать, сойдите с ума, компиляторы не должны вас пугать — ведь это так весело — играть с языками!
Язык 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.
Полезные ссылки, которые пригодятся в изучении:
