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

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

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

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

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

• проанализировать некоторую статистику программы (например, количество операторов присваивания),
• восстановить текст программы (причем, не обязательно на том же языке)
• отформатировать текст программы (создать так называемый 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) { }
}

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

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

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

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

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

Класс автовизитора с автоматическим обходом компонент

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

Определим в этом случае так называемый Автовизитор, который будет обходить и потомков, при этом не совершая никаких действий.

class AutoVisitor: Visitor
{
    public override void VisitBinOpNode(BinOpNode binop) 
    {
        binop.Left.Visit(this);
        binop.Right.Visit(this);
    }
    public override void VisitAssignNode(AssignNode a) 
    {
        // для каких-то визиторов порядок может быть обратный - вначале обойти выражение, потом - идентификатор
        a.Id.Visit(this);
        a.Expr.Visit(this);
    }
    public override void VisitCycleNode(CycleNode c) 
    {
        c.Expr.Visit(this);
        c.Stat.Visit(this);
    }
    public override void VisitBlockNode(BlockNode bl) 
    {
        foreach (var st in bl.StList)
            st.Visit(this);
    }
    public override void VisitWriteNode(WriteNode w) 
    {
        w.Expr.Visit(this);
    }
    public override void VisitVarDefNode(VarDefNode w) 
    {
        foreach (var v in w.vars)
            v.Visit(this);
    }
}

Пример простого визитора

Рассмотрим простой визитор подсчета количества операторов присваивания во всей программе:

class AssignCountVisitor : AutoVisitor
{
    public int Count = 0;
    public override void VisitAssignNode(AssignNode a)
    {
        Count += 1;
    }
}

Как видим, его код максимально прост: переопределен метод посещения узла AssignNode, в котором увеличивается счетчик количества присваиваний. Счетчик количества присваиваний является полем самого класса AssignCountVisitor и не захламляет внешний код.

Вызов данного визитора в основной программе:

var avis = new AssignCountVisitor();
parser.root.Visit(avis);
Console.WriteLine("Количество присваиваний = {0}", avis.Count);

Несмотря на внешнюю простоту, визитор имеет достаточно сложный алгоритм работы. Проследим выполнение метода parser.root.Visit(avis):

• parser.root.Visit(avis) вызывает код

avis.VisitBlockNode(this);

где this = parser.root. Таким образом, срабатыват

avis.VisitBlockNode(parser.root);

который вызывает метод базового класса AutoVisit.VisitBlockNode со следующим содержимым:

foreach (var st in bl.StList)
   st.Visit(this);

Посещение каждого st осуществляется виртуальным методом Visit, который для каждого типа узла свой. В частности, если st - узел присваивания, то в нем вызывается

v.VisitAssignNode(st);

который и вызывает определенный нами код:

public override void VisitAssignNode(AssignNode a)
{
  Count += 1;
}

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

Если программа содержит циклы, то они обходятся с помощью AutoVisit.VisitCycleNode, который автоматически обходит своё тело, где также могут встретиться присваивания.

Наконец, заметим, что при обходе самого присваивания мы не обходим узлы-потомки (идентификатор и выражение), тем самым выбрасывая целое поддерево выражения из процесса обхода.

К сожалению, узлы WriteNode и VarDefNode обходят своих потомков, заведомо не содержащих операторов присваиваний. Поэтому переопределим в AssignCountVisitor обход этих узлов, сделав его пустым:

public override void VisitWriteNode(WriteNode w) 
{
}
public override void VisitVarDefNode(VarDefNode w)
{ 
}

Единственное место, где мы неэффективно обходим целое поддерево - это оператор

write(expr)

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

Чтобы запретить этот ненужный обход поддерева, переопределим