Написание простого DSL компилятора на Delphi (Intermezzo)

Перевод поста Writing a Simple DSL Compiler with Delphi (Intermezzo).

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

Результатом всего этого является программа introduction.dpr, автономная программа которая содержит полностью язык (очень тривиальный) вместе с полной документацией, написанная в стиле Грамотного программирования. Упрощено — вы можете читать её сверху вниз как историю.

В качестве intermezzo и для упрощения моего объяснения компилятора, я опишу эту программу здесь полностью, отформатировав её как пост в блог.

introduction.dpr

Эта программа является мягким введением в тему "compiler-compiler" (программ которые генерируют компиляторы или их части). Она написана в стиле Грамотного программирования и предназначена для чтения от начала до конца.

Наша задача: мы хотим вычислять выражения в форме

Все числа целые и позитивные, только один оператор — сложение, переполнение игнорируется.

Формально, мы можем описать нашу программу следующей грамматикой

Пробельные символы игнорируются парсером и следовательно не являются частью грамматики.

Мы начнём с очень простого AST который будет хранить разобранную версию программы

На верху нашего дерева находится 'term' (слагаемое). Слагаемое может быть либо константой либо сложением.

Константа, как и можно ожидать, содержит целочисленное значение.

Здесь мы непоследовательны — язык позволяет только позитивные числа, но AST более общее и допускает негативные числа. Мы будем просто игнорировать это.

Сложение — бинарная операция над двумя слагаемыми (левым и правым).

Объект TAddition является владельцем своих дочерних объектов.

Следующая функция строит AST из массива чисел. Владелец отвечает за уничтожение полученного AST.

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

Вызов CreateAST([1, 2, 3]) создаст следующее AST с тремя узлами:

Давайте сделаем из этого тест.

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

И теперь реальный тест.

Мы напишем просто парсер который создаст AST из выражения в форме number1 + number2 + ... numberN.

Наш "язык" имеет только два токена: 'number' (число) и 'addition' (сложение). Пробельные символы не важны будут игнорироваться токинезатором (лексическим анализатором). Все не распознанные символы будут возвращать токен 'unknown'.

Больше информации про токены:

  • tkNumber — "\d+"
  • tkAddition — "+"
  • "\s+" — пропускаются
  • tkUnknown — принимает всё остальное: "[^\d+\s]"

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

  • Входная строка.
  • Текущая позиция.

Класс TStringStream обеспечивает оба эти пункта так что мы будем использовать его.

Единственная функция токинезатора возвращает следующий токен и его значение как параметры с модификатором var и возвращает True если пара токен\значение была возвращена и False если достигнут конец потока.

Эта реализация очень проста, но одновременно крайне неоптимизирована.

Необходимо несколько тестов для токинезатора..

ExpectFail(state) вызывает GetToken и ожидает что он вернёт False.

Expect(State, token, value) вызывает GetNextToken и ожидает что он вернёт True и те же токен/значение которые переданы в параметрах.

Парсер принимает любую допустимую строку и преобразует её в AST.

Если программа корректна, он создаст AST для этой программы, вернёт его в параметре ast и результат функции будет True.

Если программа не корректна, параметр ast будет nil и результат функции False.

Пустой ввод не допускается.

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

(Доказательство опущено в качестве упражнения для читателя)

Код проверит синтаксис и извлечёт из строки все числа в TArray.

В конце он передаст этот массив в функцию CreateAST для создания AST.

Нам нужно больше тестов...

Для интерпретации этого AST мы будем использовать простую рекурсию.

Несколько sanity tests всегда приветствуются...

Для компиляции этого AST, мы должны:

  • Изменить каждый узел с типом 'constant' в анонимную функцию которая возвращает значение этого узла.
  • Изменить каждый узел с типом 'summation' в анонимную функцию которая возвращает значение двух параметров.
    • Первый - анонимная функция которая вычисляет значение левого слагаемого и
    • второй - анонимная функция которая вычисляет значение правого слагаемого
  • Механизм связывания переменных заботится о получении правильных входных данных

Важная точка здесь в том что не MakeConstant не MakeAddition не делает никаких вычислений. Они просто настраивают анонимный метод и возвращают ссылку на него, что более или менее соответствует созданию объекта и возврату его интерфейса, но с добавление затрат на связывание переменных (variable capturing).

Кстати, так как наш "язык" только вычисляет целочисленные выражения что всегда на выходе даёт целое число, то "функция которая возвращает число" или TFunc точно подходит под наши требования.

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

Этот код работает корректно потому что захватывает значение const1.Value, а не ссылку (указатель) на него. Откуда я это знаю? Потому что функция TestCompileAST явным образом проверяет это поведение.

Вызывая CompileAST(CreateAST[1,2,3]) будет сгенерирована следующая анонимная функция:

(*): я знаю что результатом этого будет уточка памяти так как AST не уничтожается.

Трудно проверить что сгенерированная анонимная функция в корректной форме, но мы можем запустить её на некотором числе тестов и надеятся что всё ОК 😉

Давайте удостоверимся что ast.Value был связан по значению а не по ссылке.

Изменение AST сейчас не должно влиять на скомпилированный код.

Если все тесты проходят, мы запустим цикл Чтение-Выполнение-Вывод (Read-Eval-Print Loop) так что пользователь сможет проверить наш компилятор.

Запустим все модульные тесты для проверки корректности программы.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *