Пишем интерпретатор на PascalABC.NET. Интерпретатор по синтаксическому дереву

Этот текст - продолжение публикации https://teletype.in/@pascalabcnet/Parse3, в которой описывалось, как построить абстрактное синтаксическое дерево.

Перейдем к тому, ради чего мы публикуем серию этих статей - к написанию собственно интерпретатора. Исходные коды интерпретатора - здесь.

Для простоты интегрируем методы Eval() и Execute() прямо в узлы синтаксического дерева. Метод Eval() будет содержаться во всех узлах, производных от ExprNode, вычислять выражения и возвращать для простоты вещественное. Метод Execute() будет содержаться во всех узлах, производных от StatementNode, и будет выполнять (интерпретировать) конкретные операторы.

type 
  Node = class
    pos: Position;    
  end;
  ExprNode = class(Node)
  public
    function Eval: real; virtual := 0;
  end;
  StatementNode = class(Node)
  public
    procedure Execute; virtual := begin end;
  end;

Рассмотрим вычисление бинарной операции в узле BinOpNode:

  BinOpNode = class(ExprNode)
  public
    Left,Right: ExprNode;
    Op: char;
    constructor (Left,Right: ExprNode; Op: char; pos: Position) := 
      (Self.Left,Self.Right,Self.Op,Self.pos) := (Left,Right,Op,pos);
    function Eval: real; override;
    begin
      var l := Left.Eval;
      var r := Right.Eval;
      case Op of
        '+' : Result := l + r;
        '*' : Result := l * r;
        '/' : Result := l / r;
        '<' : Result := l < r ? 1 : 0;
      end;
    end;
  end;

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

Хорошо видно, что мы реализовали не все возможные операции - их несложно пополнить в операторе case. Основная проблема здесь - операции, имеющие для своего обозначения более одного символа - например, <=. В нашем случае приходится кодировать каждую такую операцию отдельным символом. В будущем для всех типов операций сделаем перечислимый тип.

Далее рассмотрим вычисление более простых выражений: целых и вещественных констант:

type
  IntNode = class(ExprNode)
  public
    Value: integer;
    constructor(Value: integer; pos: Position) := (Self.Value,Self.pos) 
      := (Value,pos);
    function Eval: real; override := Value;
  end;
  DoubleNode = class(ExprNode)
  public
    Value: real;
    constructor(Value: real; pos: Position) := (Self.Value,Self.pos) 
      := (Value,pos);
    function Eval: real; override := Value;
  end;

Здесь всё просто: в качестве значения константы возвращается запомненное значение Value при создании узла.

Далее рассмотрим выполнение блока, моделируемого узлом синтаксического дерева StatementListNode. Здесь мы переопределяем метод Execute:

  StatementListNode = class(StatementNode)
  public
    lst: List<StatementNode> := new List<StatementNode>;
    procedure Add(st: StatementNode) := lst.Add(st);    
    procedure Execute; override;
    begin 
      foreach var st in lst do
        st.Execute;
    end;
  end;

Суть проста - чтобы выполнить блок операторов, необходимо последовательно выполнить каждый оператор.

Следующим по сложности является реализация выполнения оператора цикла while:

type
  WhileNode = class(StatementNode)
  public
    Condition: ExprNode;
    Stat: StatementNode;
    constructor(Condition: ExprNode; Stat: StatementNode; pos: Position) 
      := (Self.Condition,Self.Stat,Self.pos) := (Condition,Stat,pos);
    procedure Execute; override;
    begin 
      while Condition.Eval > 0 do
        Stat.Execute;
    end;
  end;

В методе Execute всякий раз вычисляется условие, хранящееся в узле Condition, и пока оно истинно, выполняется тело цикла Stat.Execute.

Аналогично несложно реализуется выполнение условного оператора:

  IfNode = class(StatementNode)
  public
    Condition: ExprNode;
    ThenStat,ElseStat: StatementNode;
    constructor(Condition: ExprNode; ThenStat,ElseStat: StatementNode; pos: Position) 
      := (Self.Condition,Self.ThenStat,Self.ElseStat,Self.pos) 
        := (Condition,ThenStat,ElseStat,pos);
    procedure Execute; override;
    begin 
      if Condition.Eval > 0 then
        ThenStat.Execute
      else if ElseStat <> nil then
        ElseStat.Execute 
    end;
  end;

Здесь важной является проверка узла ElseStat на непустоту: ветвь else выполняется только если соответствующий ему узел ElseStat непуст.

Наиболее интересным является реализация выполнения оператора присваивания. Для сохранения значений переменных во время выполнения создадим словарь, который ставит в соответствие имени переменной ее значение во время выполнения:

var VarValues := new Dictionary<string,real>;

В более сложных языках, где в разных пространствах имен будут переменные с одинаковыми именами, такая структура будет сложнее.

Теперь вернемся к методу выполнения в узле AssignNode:

  AssignNode = class(StatementNode)
  public
    Ident: IdNode;
    Expr: ExprNode;
    constructor(Ident: IdNode; Expr: ExprNode; pos: Position) 
      := (Self.Ident,Self.Expr,Self.pos) := (Ident,Expr,pos);
    procedure Execute; override;
    begin 
      VarValues[Ident.Name] := Expr.Eval;
    end;
  end;

Нетрудно видеть, что для выполнения оператора присваивания мы просто меняем значение VarValues[Ident.Name] в словаре VarValues. При первом присваивании переменной словарь пополняется данной переменной, при последующих присваиваниях значение этой переменной в нем изменяется.

Обратим внимание, что поскольку у нас всего один тип - вещественный, то вообще невозможно сказать, какой наш язык: статически или динамически типизированный.

Аналогично реализуется выполнение оператора +=:

  AssignPlusNode = class(StatementNode)
  public
    Ident: IdNode;
    Expr: ExprNode;
    constructor(Ident: IdNode; Expr: ExprNode; pos: Position) 
      := (Self.Ident,Self.Expr,Self.pos) := (Ident,Expr,pos);
    procedure Execute; override;
    begin 
      VarValues[Ident.Name] += Expr.Eval;
    end;
  end;

Если переменная встречается в выражении (в правой части присваивания, в условиях операторов if и while, то для вычисления ее значения надо просто найти ее значение в словаре VarValues:

  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) 
      := (Self.Name,Self.pos) := (name,pos);
    function Eval: real; override;
    begin
      Result := VarValues[Name];
    end;
  end;

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

Наконец, нам осталось реализовать выполнение в еще одном узле: ProcCallNode. Поскольку у нас нет пользовательских процедур, то все стандартные процедуры мы можем просто перечислить при выполнении. В нашем языке есть всего одна стандартная процедура print, которая печатает вещественное значение единственного аргумента:

  ProcCallNode = class(StatementNode)
  public
    Name: IdNode;
    Pars: ExprListNode;
    constructor(Name: IdNode; Pars: ExprListNode; pos: Position) 
      := (Self.Name,Self.Pars,Self.pos) := (Name,Pars,pos);
    procedure Execute; override;
    begin
      if Name.Name = 'print' then
        Println(Pars.lst[0].Eval)
    end;
  end;

Заметим, что мы не проверяем количество параметров у print. а также имя процедуры - процедура с другим именем просто не выполнится - никакой ошибки не произойдет. Процедуру же print мы не сможем вызвать без параметров, поскольку в грамматике у процедур предусмотрен хотя бы один параметр.

Приведем полный текст модуля ASTNodes с методами Eval и Execute в соответствующих узлах:

unit ASTNodes;

uses Common;

var VarValues := new Dictionary<string,real>;
type 
  Node = class
    pos: Position;    
  end;
  ExprNode = class(Node)
  public
    function Eval: real; virtual := 0;
  end;
  StatementNode = class(Node)
  public
    procedure Execute; virtual := begin end;
  end;
  BinOpNode = class(ExprNode)
  public
    Left,Right: ExprNode;
    Op: char;
    constructor (Left,Right: ExprNode; Op: char; pos: Position) := 
      (Self.Left,Self.Right,Self.Op,Self.pos) := (Left,Right,Op,pos);
    function Eval: real; override;
    begin
      var l := Left.Eval;
      var r := Right.Eval;
      case Op of
        '+' : Result := l + r;
        '*' : Result := l * r;
        '/' : Result := l / r;
        '<' : Result := l < r ? 1 : 0;
      end;
    end;
  end;
  StatementListNode = class(StatementNode)
  public
    lst: List<StatementNode> := new List<StatementNode>;
    procedure Add(st: StatementNode) := lst.Add(st);    
    procedure Execute; override;
    begin 
      foreach var st in lst do
        st.Execute;
    end;
  end;
  ExprListNode = class(Node)
  public
    lst: List<ExprNode> := new List<ExprNode>;
    procedure Add(ex: ExprNode) := lst.Add(ex);
  end;
  IntNode = class(ExprNode)
  public
    Value: integer;
    constructor(Value: integer; pos: Position) := (Self.Value,Self.pos) := (Value,pos);
    function Eval: real; override := Value;
  end;
  DoubleNode = class(ExprNode)
  public
    Value: real;
    constructor(Value: real; pos: Position) := (Self.Value,Self.pos) := (Value,pos);
    function Eval: real; override := Value;
  end;
  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) := (Self.Name,Self.pos) := (name,pos);
    function Eval: real; override;
    begin
      Result := VarValues[Name];
    end;
  end;
  AssignNode = class(StatementNode)
  public
    Ident: IdNode;
    Expr: ExprNode;
    constructor(Ident: IdNode; Expr: ExprNode; pos: Position) := (Self.Ident,Self.Expr,Self.pos) := (Ident,Expr,pos);
    procedure Execute; override;
    begin 
      VarValues[Ident.Name] := Expr.Eval;
    end;
  end;
  AssignPlusNode = class(StatementNode)
  public
    Ident: IdNode;
    Expr: ExprNode;
    constructor(Ident: IdNode; Expr: ExprNode; pos: Position) := (Self.Ident,Self.Expr,Self.pos) := (Ident,Expr,pos);
    procedure Execute; override;
    begin 
      VarValues[Ident.Name] += Expr.Eval;
    end;
  end;
  IfNode = class(StatementNode)
  public
    Condition: ExprNode;
    ThenStat,ElseStat: StatementNode;
    constructor(Condition: ExprNode; ThenStat,ElseStat: StatementNode; pos: Position) 
      := (Self.Condition,Self.ThenStat,Self.ElseStat,Self.pos) := (Condition,ThenStat,ElseStat,pos);
    procedure Execute; override;
    begin 
      if Condition.Eval > 0 then
        ThenStat.Execute
      else if ElseStat <> nil then
        ElseStat.Execute 
    end;
  end;
  WhileNode = class(StatementNode)
  public
    Condition: ExprNode;
    Stat: StatementNode;
    constructor(Condition: ExprNode; Stat: StatementNode; pos: Position) 
      := (Self.Condition,Self.Stat,Self.pos) := (Condition,Stat,pos);
    procedure Execute; override;
    begin 
      while Condition.Eval > 0 do
        Stat.Execute;
    end;
  end;
  ProcCallNode = class(StatementNode)
  public
    Name: IdNode;
    Pars: ExprListNode;
    constructor(Name: IdNode; Pars: ExprListNode; pos: Position) 
      := (Self.Name,Self.Pars,Self.pos) := (Name,Pars,pos);
    procedure Execute; override;
    begin
      if Name.Name.ToLower = 'print' then
        Println(Pars.lst[0].Eval)
    end;
  end;
  FuncCallNode = class(ExprNode)
  public
    Name: IdNode;
    Pars: ExprListNode;
    constructor(Name: IdNode; Pars: ExprListNode; pos: Position) 
      := (Self.Name,Self.Pars,Self.pos) := (Name,Pars,pos);
  end;
 
end.

Рассмотрим основную программу, которая запускает интерпретатор:

uses LexUnit,ParseUnit,Common;
begin
  var text := 'i = 1; sum = 0; while i<100000000 do {sum += 1/i; i += 1}; print(sum)';
  var lex := new Lexer(text);
  try
    var par := new Parser(lex);
    var progr := par.MainProgram;
    Println; 
    MillisecondsDelta;
    progr.Execute;
    Println(#10,MillisecondsDelta/1000+' с');
  except
    on e: LexerException do
      OutputError('Lexer error:',e,lex.Lines);
    on e: SyntaxException do
      OutputError('Parser error:',e,lex.Lines);
  end;  
end.

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

Время выполнения на компьютере с процессором Core I7 8700K с 16 Гб памяти составляет 15.3 сек. Количество строк нашей программы - около 660.

Составим аналогичную программу на языке Python:

import time
n = 100000000
c = True
start = time.time()
i = 1
sum = 0
while i<n:
    sum += 1/i
    i += 1
print(sum)
print(time.time() - start)

Время ее выполнения на компьютере с той же конфигурацией составляет 12.8 сек.

Вывод: мы написали интерпретатор на PascalABC.NET на 660 строк, по скоростью сравнимый со скоростью промышленного интерпретатора Python.