About Teletype
Join
P
@pascalabcnet
July 10, 2023

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

Этот текст - продолжение публикации https://teletype.in/@pascalabcnet/InterpretASTTree.

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

Итак, мы построили синтаксическое дерево. Его корнем является узел всей программы, остальные вершины являются операторами, выражениями и листовые вершины являются терминалами: целыми и вещественными константами, идентификаторами.

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

По синтаксическому дереву можно восстановить текст программы - причем, можно это сделать на другом языке: например, программа будет на языке C, а восстановим мы ее на языке Паскаль.

По синтаксическому дереву можно сделать ряд семантических проверок: верно ли описаны переменные, правильно ли типизированы выражения и проч. Семантическими проверками мы займемся в одной из следующих статей.

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

Для решения этой важнейшей задачи нам поможет так называемый паттерн проектирования Визитор (Посетитель).

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

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

Рассмотрим интерфейс визитора по нашему синтаксическому дереву:

type
  IVisitor<T> = interface
    function VisitNode(bin: Node): T;
    function VisitExprNode(bin: ExprNode): T;
    function VisitStatementNode(bin: StatementNode): T;
    function VisitBinOp(bin: BinOpNode): T;
    function VisitStatementList(stl: StatementListNode): T;
    function VisitExprList(exlist: ExprListNode): T;
    function VisitInt(n: IntNode): T;
    function VisitDouble(d: DoubleNode): T;
    function VisitId(id: IdNode): T;
    function VisitAssign(ass: AssignNode): T;
    function VisitAssignPlus(ass: AssignPlusNode): T;
    function VisitIf(ifn: IfNode): T;
    function VisitWhile(whn: WhileNode): T;
    function VisitProcCall(p: ProcCallNode): T;
    function VisitFuncCall(f: FuncCallNode): T;
  end;

Он состоит из заголовков функций - каждая отвечает за свой тип узла и возвращает некоторое значение типа T. В классах, реализующих этот интерфейс, мы будем возвращать конкретные типы T. Например, в визиторе PrettyPrinter T=string и мы будем в каждой функции строковое представление части кода, связанной с этим узлом.

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

Для того чтобы паттерн Визитор автоматически вызывал эти методы для каждого типа узла, мы должны встроить в каждый узел синтаксического дерева специальный метод Visit:

 type
  Node = class
    pos: Position;    
  public
    function Visit<T>(v: IVisitor<T>): T; virtual := v.VisitNode(Self);
  end;
  ExprNode = class(Node)
  public
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitExprNode(Self);
  end;
  StatementNode = class(Node)
  public
    function Visit<T>(v: IVisitor<T>): T; override 
      := v.VisitStatementNode(Self);
  end;
  BinOpNode = class(ExprNode)
  public
    Left,Right: ExprNode;
    Op: OpType;
    constructor (Left,Right: ExprNode; Op: OpType; pos: Position) := 
      (Self.Left,Self.Right,Self.Op,Self.pos) := (Left,Right,Op,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitBinOp(Self);
  end;
  StatementListNode = class(StatementNode)
  public
    lst: List<StatementNode> := new List<StatementNode>;
    procedure Add(st: StatementNode) := lst.Add(st);    
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitStatementList(Self);
  end;
  ExprListNode = class(Node)
  public
    lst: List<ExprNode> := new List<ExprNode>;
    procedure Add(ex: ExprNode) := lst.Add(ex);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitExprList(Self);
  end;
  IntNode = class(ExprNode)
  public
    Value: integer;
    constructor(Value: integer; pos: Position) 
    := (Self.Value,Self.pos) := (Value,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitInt(Self);
  end;
  DoubleNode = class(ExprNode)
  public
    Value: real;
    constructor(Value: real; pos: Position) := (Self.Value,Self.pos) := (Value,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitDouble(Self);
  end;
  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) := (Self.Name,Self.pos) := (name,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitId(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitAssign(Self); 
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitAssignPlus(Self); 
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitIf(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitWhile(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitProcCall(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitFuncCall(Self);
  end;

В каждом методе Visit мы передаем единственным параметром интерфейс описанного нами визитора и в теле метода вызываем соответствующий данному синтаксическому узлу метод визитора. Например, в теле метода Visit класса BinOpNode мы вызываем метод v.VisitBinOp(Self), передавая ему в качестве параметра Self - ссылку на текущий узел синтаксического дерева.

Что мы таким образом приобретаем?

Предположим, мы написали определенный визитор MyVisitor, реализующий интерфейс IVisitor<T> и создали объект этого визитора в переменной v. Тогда вызов метода Visit например для узла BinOpNode вызовет, как мы уже отметили, метод v.VisitBinOp(Self) для нашего класса MyVisitor, тем самым, выполнится конкретное действие, которое мы предусмотрели для узла BinOpNode в классе MyVisitor.

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

Приведем полный код модуля ASTNodes с интерфейсом визитора:

unit ASTNodes;
uses Common;

type OpType = (opPlus, opMinus, opMultiply, opDivide, 
  opEqual, opLess, opLessEqual, opGreater, opGreaterEqual, opNotEqual, 
  opAnd, opOr, opNot, opBad);

var OpToStr := Dict(
    (opPlus,#39;+'),(opMinus,#39;-'),(opMultiply,#39;*'),(opDivide,#39;/'),
    (opEqual,#39;=='),(opLess,#39;<'),(opLessEqual,#39;<='),(opGreater,#39;>'),(opGreaterEqual,#39;>='),(opNotEqual,#39;!='),
    (opAnd,#39;&&'),(opOr,#39;||'),(opNot,#39;!')
  );

type 
  Node = class;
  ExprNode = class;
  StatementNode = class;
  BinOpNode = class;
  StatementListNode = class;
  ExprListNode = class;
  IntNode = class;
  DoubleNode = class;
  IdNode = class;
  AssignNode = class;
  AssignPlusNode = class;
  IfNode = class;
  WhileNode = class;
  ProcCallNode = class;
  FuncCallNode = class;
  IVisitor<T> = interface
    function VisitNode(bin: Node): T;
    function VisitExprNode(bin: ExprNode): T;
    function VisitStatementNode(bin: StatementNode): T;
    function VisitBinOp(bin: BinOpNode): T;
    function VisitStatementList(stl: StatementListNode): T;
    function VisitExprList(exlist: ExprListNode): T;
    function VisitInt(n: IntNode): T;
    function VisitDouble(d: DoubleNode): T;
    function VisitId(id: IdNode): T;
    function VisitAssign(ass: AssignNode): T;
    function VisitAssignPlus(ass: AssignPlusNode): T;
    function VisitIf(ifn: IfNode): T;
    function VisitWhile(whn: WhileNode): T;
    function VisitProcCall(p: ProcCallNode): T;
    function VisitFuncCall(f: FuncCallNode): T;
  end;
  IVisitorP = interface
    procedure VisitNode(bin: Node);
    procedure VisitExprNode(bin: ExprNode);
    procedure VisitStatementNode(bin: StatementNode);
    procedure VisitBinOp(bin: BinOpNode);
    procedure VisitStatementList(stl: StatementListNode);
    procedure VisitExprList(exlist: ExprListNode);
    procedure VisitInt(n: IntNode);
    procedure VisitDouble(d: DoubleNode);
    procedure VisitId(id: IdNode);
    procedure VisitAssign(ass: AssignNode);
    procedure VisitAssignPlus(ass: AssignPlusNode);
    procedure VisitIf(ifn: IfNode);
    procedure VisitWhile(whn: WhileNode);
    procedure VisitProcCall(p: ProcCallNode);
    procedure VisitFuncCall(f: FuncCallNode);
  end;
  
  Node = class
    pos: Position;    
  public
    function Visit<T>(v: IVisitor<T>): T; virtual := v.VisitNode(Self);
  end;
  ExprNode = class(Node)
  public
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitExprNode(Self);
  end;
  StatementNode = class(Node)
  public
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitStatementNode(Self);
  end;
  BinOpNode = class(ExprNode)
  public
    Left,Right: ExprNode;
    Op: OpType;
    constructor (Left,Right: ExprNode; Op: OpType; pos: Position) := 
      (Self.Left,Self.Right,Self.Op,Self.pos) := (Left,Right,Op,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitBinOp(Self);
  end;
  StatementListNode = class(StatementNode)
  public
    lst: List<StatementNode> := new List<StatementNode>;
    procedure Add(st: StatementNode) := lst.Add(st);    
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitStatementList(Self);
  end;
  ExprListNode = class(Node)
  public
    lst: List<ExprNode> := new List<ExprNode>;
    procedure Add(ex: ExprNode) := lst.Add(ex);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitExprList(Self);
  end;
  IntNode = class(ExprNode)
  public
    Value: integer;
    constructor(Value: integer; pos: Position) := (Self.Value,Self.pos) := (Value,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitInt(Self);
  end;
  DoubleNode = class(ExprNode)
  public
    Value: real;
    constructor(Value: real; pos: Position) := (Self.Value,Self.pos) := (Value,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitDouble(Self);
  end;
  IdNode = class(ExprNode)
  public
    Name: string;
    constructor(name: string; pos: Position) := (Self.Name,Self.pos) := (name,pos);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitId(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitAssign(Self); 
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitAssignPlus(Self); 
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitIf(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitWhile(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitProcCall(Self);
  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);
    function Visit<T>(v: IVisitor<T>): T; override := v.VisitFuncCall(Self);
  end;
end.

Напишем простой прикладной визитор простой печати текста программы по синтаксическому дереву. Унаследуем его от IVisitor<string>. Это значит, что каждый его метод будет возвращать строку - часть текста программы, соответствующая данному узлу. Поместим этот визитор в модуль SimplePrint:

unit SimplePrint;
uses ASTNodes;
type 
  SimplePrintVisitor = class(IVisitor<string>)
  public  
    function VisitNode(n: Node): string := n.Visit(Self);
    function VisitExprNode(ex: ExprNode): string := ex.Visit(Self);
    function VisitStatementNode(st: StatementNode): string := st.Visit(Self);
    function VisitBinOp(bin: BinOpNode): string := bin.Left.Visit(Self) + OpToStr[bin.Op] + bin.Right.Visit(Self);
    function VisitStatementList(stl: StatementListNode): string := 
      stl.lst.Select(x -> x.Visit(Self)).JoinToString(NewLine);
    function VisitExprList(exlist: ExprListNode): string := exlist.lst.Select(x -> x.Visit(Self)).JoinToString(',');
    function VisitInt(n: IntNode): string := n.Value.ToString;
    function VisitDouble(d: DoubleNode): string := d.Value.ToString;
    function VisitId(id: IdNode): string := id.Name;
    function VisitAssign(ass: AssignNode): string := ass.Ident.Name + ' := ' + ass.Expr.Visit(Self);
    function VisitAssignPlus(ass: AssignPlusNode): string := ass.Ident.Name + ' += ' + ass.Expr.Visit(Self);
    function VisitIf(ifn: IfNode): string 
      := 'if ' + ifn.Condition.Visit(Self) + ' then '+ ifn.ThenStat.Visit(Self) 
        + (ifn.ElseStat = nil ? '' : ifn.ElseStat.Visit(Self));
    function VisitWhile(whn: WhileNode): string
      := 'while '+ whn.Condition.Visit(Self) + ' do '+ NewLine + whn.Stat.Visit(Self);
    function VisitProcCall(p: ProcCallNode): string := p.Name.Name + '(' + p.Pars.Visit(Self) + ')';
    function VisitFuncCall(f: FuncCallNode): string := f.Name.Name + '(' + f.Pars.Visit(Self) + ')';
  end;
end.

Воспользуемся им в основной программе:

uses LexUnit,ParseUnit,SemanticCheck,Common,SimplePrint;
begin
  var text := 'i = 1; sum = 0.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;
    var semcheck := new SemanticCheckVisitor;
    progr.VisitP(semcheck);
    progr.Visit(new SimplePrintVisitor).Println;
  except
    on e: LexerException do
      OutputError('Лексическая ошибка:',e,lex.Lines);
    on e: SyntaxException do
      OutputError('Синтаксическая ошибка:',e,lex.Lines);
    on e: SemanticException do
      OutputError('Семантическая ошибка:',e,lex.Lines);
  end;  
end.

Результат:

i := 1
sum := 0
while i<100000000 do 
sum += 1/i
i += 1
print(sum)

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

@pascalabcnet
July 10, 2023, 08:46
2 reactions
0 views