Написание простого DSL компилятора на Delphi (2. Абстрактное синтаксическое дерево)

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

Эта статья представляет собой описание абстрактного синтаксического дерева, используемого для представления "Языка". Если вы только начинаете читать эту серию, то я бы рекомендовал вам начать с этого поста.

Пожалуйста, имейте в виду, что эта статья описывают начальную реализацию AST. Если вы хотите просматривать код во время чтения статьи, убедитесь, что вы переключились на ветку dsl_v1.

Абстрактное синтаксическое дерево является, проще говоря, символическим представлением программы в виде дерева.

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

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

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

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

Структура компилятора

Достаточно очевидно, что AST является центральной частью всего проекта и поэтому я решил рассказать о нём перед токинизатором и парсером.

В моём случае (и позвольте мне напомнить вам снова, что всё последующее описание применяется к ветке dsl_v1), AST программы начинается с очень простого интерфейса ISimpleDSLAST. (я буду показывать все типы в сокращённой форме без геттеров и сеттеров).

Программа в "Языке" это не более чем коллекция функций и интерфейс отражает это.

Каждая функция имеет имя, список параметров и тело.

Тело функции не более чем коллекция операторов.

Оператором является либо оператор if, либо оператор return. Других вариантов нет.

IASTStatement это просто родительский интерфейс для всех интерфейсов операторов и никогда не создаётся сам по себе.

Оператор return имеет только одну часть — выражение, которое вычисляется и затем возвращается в виде результат функции.

Оператор if более сложный. Он имеет условие (которое тоже является выражением) и следующие за then и else блоки. (и, как мы уже знаем, блок это просто коллекция операторов)

Выражение может содержать слагаемое или бинарную операцию с двумя слагаемыми. На данный момент поддерживаются только три операции: сложение, вычитание и сравнение. В Языке нет унарных операторов, так вы не можете написать такой оператор return -3, а должны использовать такую форму return 0-3.

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

IASTTerm, также как IASTStatement, является родительским интерфейсом

Константа — просто числовое значение, вычислимое парсером.

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

И последняя часть AST — вызов функции содержит индекс вызываемой нами функции и список параметров которые мы передаём в функцию. Параметры являются выражением.

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

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

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

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