Перевод поста Writing a Simple DSL Compiler with Delphi (2. Abstract Syntax Tree).
Эта статья представляет собой описание абстрактного синтаксического дерева, используемого для представления "Языка". Если вы только начинаете читать эту серию, то я бы рекомендовал вам начать с этого поста.
Пожалуйста, имейте в виду, что эта статья описывают начальную реализацию AST. Если вы хотите просматривать код во время чтения статьи, убедитесь, что вы переключились на ветку dsl_v1.
Абстрактное синтаксическое дерево является, проще говоря, символическим представлением программы в виде дерева.
В то время как текстовое представление программы хорошо подходит для нас, людей, компьютерам тяжело с ним справляться. Поэтому специальная часть любого интерпретатора или компилятора, называемая парсер, читает входной поток и преобразует его в машиночитаемый формат — AST. Это дерево может использоваться для множества целей. Мы можем, например, скормить его интерпретатору который запустит программу для нас, или мы можем скормить его компилятору для генерации запускаемого модуля, или кросс-компилятору для генерации эквивалентной программы на другом языке программирования.
В действительности, этот процесс обычно еще более сложный. Парсер использует специальный входной модуль называемый токинизатор для чтения входного потока и компилятор обычно не создаёт исполняемый модуль напрямую, но производит несколько файлов, которые линкуются в конечную программу.
В случая моего игрушечного проекта компилятора, парсер использует отдельный токинизатор, а компилятор не создаёт запускаемый файл непорсредственно, а производит несколько файлов которые линкуются в конечную программу.
В случае моего игрушечного компилятора, парсер использует отдельный токинизатор, в то время как все вроцессы вывода (такие как компилятор) генерируют код, без дополнительных шагов (например, линковки).
Достаточно очевидно, что AST является центральной частью всего проекта и поэтому я решил рассказать о нём перед токинизатором и парсером.
В моём случае (и позвольте мне напомнить вам снова, что всё последующее описание применяется к ветке dsl_v1), AST программы начинается с очень простого интерфейса ISimpleDSLAST. (я буду показывать все типы в сокращённой форме без геттеров и сеттеров).
1 2 3 4 5 6 7 8 9 10 | 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; |
Программа в "Языке" это не более чем коллекция функций и интерфейс отражает это.
Каждая функция имеет имя, список параметров и тело.
1 2 3 4 5 6 7 | 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; |
Тело функции не более чем коллекция операторов.
1 2 3 4 5 | TStatementList = TList; IASTBlock = interface property Statements: TStatementList read GetStatements; end; |
Оператором является либо оператор if, либо оператор return. Других вариантов нет.
1 2 3 4 | TASTStatementType = (stIf, stReturn); IASTStatement = interface end; { IASTStatement } |
IASTStatement это просто родительский интерфейс для всех интерфейсов операторов и никогда не создаётся сам по себе.
Оператор return имеет только одну часть — выражение, которое вычисляется и затем возвращается в виде результат функции.
1 2 3 | IASTReturnStatement = interface(IASTStatement) property Expression: IASTExpression read GetExpression write SetExpression; end; |
Оператор if более сложный. Он имеет условие (которое тоже является выражением) и следующие за then и else блоки. (и, как мы уже знаем, блок это просто коллекция операторов)
1 2 3 4 5 | 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.
1 2 3 4 5 6 | 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; |
Слагаемое может быть константой, переменной или вызовом функции.
1 2 3 4 | TASTTermType = (termConstant, termVariable, termFunctionCall); IASTTerm = interface end; |
IASTTerm, также как IASTStatement, является родительским интерфейсом
Константа — просто числовое значение, вычислимое парсером.
1 2 3 | IASTTermConstant = interface(IASTTerm) property Value: integer read GetValue write SetValue; end; |
Переменные в действительности имеют неверное название. Язык не поддерживает переменные. В коде могут быть только ссылки на параметры функций. Так как вложенные функции не поддерживаются, то каждый параметр может быть представлен своим индексом в списке параметров (который, также вычисляется парсером).
1 2 3 | IASTTermVariable = interface(IASTTerm) property VariableIdx: integer read GetVariableIdx write SetVariableIdx; end; |
И последняя часть AST — вызов функции содержит индекс вызываемой нами функции и список параметров которые мы передаём в функцию. Параметры являются выражением.
1 2 3 4 5 | TExpressionList = TList; IASTTermFunctionCall = interface(IASTTerm) property FunctionIdx: integer read GetFunctionIdx write SetFunctionIdx; property Parameters: TExpressionList read GetParameters; end; |
В действительности, в модуле SimpleDSLCompiler.AST больше ничего нет кроме этого набора интерфейсов и очень тривиальных объектов реализующих их. Этой информации достаточно чтобы представлять семантику оригинальной программы (форматирование теряется во время парсинга) и дальше она может быть подана на вход компилятору.
