Визиторы по синтаксическому дереву

К основной странице курса

Общие комментарии

Синтаксическое дерево построено - что дальше?

По синтаксическому дереву можно:

• проанализировать некоторую статистику программы (например, количество операторов присваивания),
• восстановить текст программы (причем, не обязательно на том же языке)
• отформатировать текст программы (создать так называемый Pretty Printer)
• сгенерировать код программы на некотором целевом языке
• выполнить интерпретацию программы

Для каждого такого действия придется совершать обход всех узлов дерева в некотором порядке и совершать действие над каждым узлом в зависимости от типа узла.

При этом, в результате выполнения такого действия будут, как правило, накапливаться некоторые внешние данные (количество операторов присваивания или список команд целевого кода)

Одно из решений - реализовать каждое действие в виде виртуального метода и переопределить этот метод в каждом типе узлов дерева. Например, реализовать в каждом синтаксическом узле метод Print для вывода текста программы, метод Generate для генерации участка кода, метод Interpret - для выполнения команды интерпретатора и т.д.

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

Именно для решения подобных проблем и используется паттерн Визитор.

Паттерн Визитор

Описание паттерна Посетитель в курсе Паттерны проектирования

Для реализации паттерна Визитор в нашем проекте имеется файл Visitor.cs, содержащий абстрактный класс

public abstract class Visitor
{
    public virtual void VisitIdNode(IdNode id) { }
    public virtual void VisitIntNumNode(IntNumNode num) { }
    public virtual void VisitBinOpNode(BinOpNode binop) { }
    public virtual void VisitAssignNode(AssignNode a) { }
    public virtual void VisitCycleNode(CycleNode c) { }
    public virtual void VisitBlockNode(BlockNode bl) { }
    public virtual void VisitWriteNode(WriteNode w) { }
    public virtual void VisitVarDefNode(VarDefNode w) { }
    public virtual void VisitEmptyNode(EmptyNode w) { }
}

с методами для обхода каждого типа узла.

Кроме этого, в базовом классе для всех узлов определим абстрактный метод Accept, которому передадим текущий визитор в качестве параметра.

public abstract class Node     
{
    public abstract void Accept(Visitor v);
}

и в каждом узле синтаксического дерева, который требуется обходить, переопределим метод Accept, вызывая из него соответствующий метод Visit. Например, для AssignNode он будет выглядеть так:

public override void Accept(Visitor v)
{
   v.VisitAssignNode(this);
}