Пишем интерпретатор на PascalABC.NET. Синтаксический анализатор. Часть 2. Абстрактное синтаксическое дерево (AST)

Этот текст - продолжение публикации https://teletype.in/@pascalabcnet/Parse2, в которой описывался парсер простого языка программирования Simple.

Следующая статья - https://teletype.in/@pascalabcnet/InterpretASTTree

Чтобы код, приведенный по предыдущей ссылке, работал, нам необходим еще один модуль - ASTNodes. Это - модуль, содержащий узлы абстрактного синтаксического дерева программы AST, которое создается как результат парсинга.

Все узлы синтаксического дерева - наследники узла Node:

type 
  Node = class
  public  
    pos: Position;    
  end;

Этот класс по-существу хранит только позицию начала конструкции pos, тип которой Position описан в модуле Common:

type
  Position = auto class
    auto property Line: integer;
    auto property Col: integer;
  end;

Следующие два важных класса - это ExprNode - предок всех выражений и StatementNode - предок всех операторов. Они не имеют собственных полей и нужны лишь для того чтобы мы от них наследовали конкретные узлы. Такие классы, которые нужны только для создания потомков, а экземпляры самих классов не создаются, называются абстрактными. В PascalABC.NET для абстрактных классов имеется специальное ключевое слово abstract:

type 
  Node = abstract class
  public  
    pos: Position;    
  end;
  ExprNode = abstract class(Node)
  end;
  StatementNode = abstract class(Node)
  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);
  end;

Классы IntNode и DoubleNode являются узлами, представляющими целые и вещественные константы в коде программы. Они хранят помимо позиции значение этой константы:

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

Класс IdNode представляет идентификатор:

  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) := (Self.Name,Self.pos) 
      := (name,pos);
  end;

Далее приведем код всех узлов используемого нами синтаксического дерева. Каждый узел хранит позицию в коде т.к. наследуется от узла Node, свои подузлы - наследники Node (если они есть) и дополнительные поля, связанные с конкретным узлом:

type  
  StatementListNode = class(StatementNode)
  public
    lst: List<StatementNode> := new List<StatementNode>;
    procedure Add(st: StatementNode) := lst.Add(st);    
  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);
  end;
  DoubleNode = class(ExprNode)
  public
    Value: real;
    constructor(Value: real; pos: Position) := (Self.Value,Self.pos) 
      := (Value,pos);
  end;
  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) := (Self.Name,Self.pos) 
      := (name,pos);
  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);
  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);
  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);
  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);
  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);
  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;

Если мы разместим все узлы в модуле ASTNodes и подключим его в модуле ParseUnit, то следующий код будет строить абстрактное синтаксическое дерево:

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;
  except
    on e: LexerException do
      OutputError('Lexer error:',e,lex.Lines);
    on e: SyntaxException do
      OutputError('Parser error:',e,lex.Lines);
  end;  
end.

Всего наше приложение занимает около 650 строк. Оно пока ничего не делает кроме построения AST - дерева. Однако именно AST-дерево - отправная точка для дальнейших преобразований.

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