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

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

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

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

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

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

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

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

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

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

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

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

IASTFunctions = interface
  function  Add(const func: IASTFunction): integer;
  function  Count: integer;
  function  IndexOf(const name: string): integer;
  property Items[idxFunction: integer]: IASTFunction read GetItems; default;
end; { IASTFunctions }

ISimpleDSLAST = interface
   property Functions: IASTFunctions read GetFunctions;
end;

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

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

TParameterList = TList<string>;

IASTFunction = interface ['{FA4F603A-FE89-40D4-8F96-5607E4EBE511}']
   property Name: string read GetName write SetName;
   property ParamNames: TParameterList read GetParamNames;
   property Body: IASTBlock read GetBody write SetBody;
end;

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

TStatementList = TList;

IASTBlock = interface
   property Statements: TStatementList read GetStatements;
end;

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

TASTStatementType = (stIf, stReturn);

IASTStatement = interface
end; { IASTStatement }

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

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

IASTReturnStatement = interface(IASTStatement)
   property Expression: IASTExpression read GetExpression write SetExpression;
end;

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

IASTIfStatement = interface(IASTStatement)
   property Condition: IASTExpression read GetCondition write SetCondition;
   property ThenBlock: IASTBlock read GetThenBlock write SetThenBlock;
   property ElseBlock: IASTBlock read GetElseBlock write SetElseBlock;
end;

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

TBinaryOperation = (opNone, opAdd, opSubtract, opCompareLess);
IASTExpression = interface
   property Term1: IASTTerm read GetTerm1 write SetTerm1;
   property Term2: IASTTerm read GetTerm2 write SetTerm2;
   property BinaryOp: TBinaryOperation read GetBinaryOp write SetBinaryOp;
end;

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

TASTTermType = (termConstant, termVariable, termFunctionCall);

IASTTerm = interface
end;

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

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

IASTTermConstant = interface(IASTTerm)
   property Value: integer read GetValue write SetValue;
end;

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

IASTTermVariable = interface(IASTTerm)
   property VariableIdx: integer read GetVariableIdx write SetVariableIdx;
end;

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

TExpressionList = TList;
IASTTermFunctionCall = interface(IASTTerm)
   property FunctionIdx: integer read GetFunctionIdx write SetFunctionIdx;
   property Parameters: TExpressionList read GetParameters;
end;

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

Последниее изменение: