Way23

Написание простого DSL компилятора на Delphi (6. Дамп AST)

Перевод поста Writing a Simple DSL Compiler with Delphi (6. AST Dumper)open in new window.

Эта статья представляет описание инструмента для тестирования моего игрушечного языка программирования. Если вы только начинаете читать эту серию, то я бы рекомендовал вам начать с этого постаopen in new window.

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

Теперь, когда мы имеем работающий токинезаторopen in new window и парсерopen in new window генерирующие на выходе ASTopen in new window, мы можем начать работать над компилятором. Тем не менее, было бы отлично проверить корректность выходных данных парсера. Или по другому — нам нужны модульные тесты.

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

Чтобы сделать это, мы напишем генератор кода который вместо машинного кода генерирует исходную программу. Мы можем сделать просто поместив новую фабрику codegen в гибкий каркас компилятораopen in new window.

sl := TStringList.Create;
try
  compiler := CreateSimpleDSLCompiler;
  compiler.CodegenFactory := 
    function: ISimpleDSLCodegen 
    begin 
      Result := CreateSimpleDSLCodegenDump(sl); 
    end;
  compiler.Compile(CMultiProcCode);
  Writeln(sl.Text);
finally FreeAndNil(sl); end;
1
2
3
4
5
6
7
8
9
10
11

codegen будет сохранять результирующую программу в список строк sl, который мы можем передать в анонимную процедуру (CodegenFactory) из-за полезного захвата переменнойopen in new window.

Наш генератор кода — TSimpleDSLCodegenDump должен реализовывать интерфейс ISimpleDSLCodegen содержащий одну функцию — Generate. Эта функция берет AST и возвращает что-то запускаемое — ISimpleDSLProgram. Поскольку наш код не знает как создавать запускаемую программу, он будет возвращать nil в этом параметре.

type
  ISimpleDSLCodegen = interface ['{C359C174-E324-4709-86EF-EE61AFE3B1FD}']
    function Generate(const ast: ISimpleDSLAST; var runnable: ISimpleDSLProgram): boolean;
  end;
1
2
3
4

Полезные данные будут сохранены в список строк (TStringList) который передан в конструктор.

constructor TSimpleDSLCodegenDump.Create(dump: TStringList);
begin
  inherited Create;
  FDump := dump;
end;
1
2
3
4
5

Основная функция генерации кода сохраняет ссылку на AST в поле так что мы имеем доступ к нему из всех методов и затем восстаёт исходный код функция за функцией вызовами DumpFunction.

function TSimpleDSLCodegenDump.Generate(const ast: ISimpleDSLAST;
  var runnable: ISimpleDSLProgram): boolean;
var
  i: integer;
begin
  FErrors := false;
  FAST := ast;
  for i := 0 to ast.Functions.Count - 1 do begin
    if i > 0 then begin
      WritelnText;
      WritelnText;
    end;
    DumpFunction(ast.Functions[i]);
  end;
  FDump.Text := FText;
  Result := not FErrors;
end;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Код программы собирается в поле FText: string. Два вспомогательных метода WritelnText используются для добавления данных в это поле.

procedure TSimpleDSLCodegenDump.WritelnText(const s: string);
begin
  WriteText(s);
  WriteText(#13#10);
end;

procedure TSimpleDSLCodegenDump.WriteText(const s: string);
begin
  FText := FText + s;
end;
1
2
3
4
5
6
7
8
9
10

Я покажу только две части этого "генератора кода" так как он довольно скучен. Как первый пример, эта функция записывает исходный код одной функции.

procedure TSimpleDSLCodegenDump.DumpFunction(const func: TASTFunction);
begin
  FCurrentFunc := func;
  WriteText(Format('%s(%s) ', [func.Name, ''.Join(',', func.ParamNames.ToArray)]));
  DumpBlock('', func.Body);
  FCurrentFunc := nil;
end;
1
2
3
4
5
6
7

Ссылка на текущую функцию сохраняется снаружи так как она нужна нам в методе который записывает название переменной (не показан здесь). Затем мы записываем название функции, с последующим списком параметров. Хелпер Join для строк соединяет параметры в одну строку с разделителем в виде запятой. В конце мы вызываем DumpBlock для записи тела функции.

Во втором примере, метод DumpExpression, записывает выражение. Он вызывает DumpTerm для записи первого слагаемого, записывает оператор (если он есть) и записывает второе слагаемое.

procedure TSimpleDSLCodegenDump.DumpExpression(const expr: TASTExpression);
begin
  DumpTerm(expr.Term1);
  case expr.BinaryOp of
    opNone:        Exit;
    opAdd:         WriteText(' + ');
    opSubtract:    WriteText(' - ');
    opCompareLess: WriteText(' < ');
    else begin
      WritelnText('*** Unexpected operator');
      FErrors := true;
    end;
  end;
  DumpTerm(expr.Term2);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

'fib(i) {                          '#13#10 +
'  if i < 3 {                      '#13#10 +
'    return 1                      '#13#10 +
'  } else {                        '#13#10 +
'    return fib(i-2) + fib(i-1)    '#13#10 +
'  }                               '#13#10 +
'}                                 '
1
2
3
4
5
6
7

...мы увидим что результат довольно близок к оригиналу

fib(i) {
  if i < 3  {
    return 1
  }  else  {
    return fib(i - 2) + fib(i - 1)
  }
}
1
2
3
4
5
6
7

Разделители немного отличаются, но это не имеет значения так как мой игрушечный язык игнорирует пробельные символы. Это даёт нам уверенность что AST действительно правильно сгенерированно (как минимум в некоторых случаях). Чтобы быть более уверенными в правильной работе парсера мы могли бы написать больше тестов... или мы можем просто поиграть с компилятором, написать больше программ и проверить что они работают корректно. Однако, чтобы это сделать нам нужен сам компилятор.

Последниее изменение: 24.08.2023, 06:42:55