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

Текущая версия на 10:15, 4 декабря 2015

Код проекта

Комплект для практического занятия скачиваем отсюда.

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

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

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

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

Визитор для создания Pretty Printerа

Данный визитор генерирует во внутренней переменной Text текст отформатированной программы.

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

Код визитора PrettyPrintVisitor

class PrettyPrintVisitor: Visitor
{
    public string Text = "";
    private int Indent = 0;

    private string IndentStr()
    {
        return new string(' ', Indent);
    }
    private void IndentPlus()
    {
        Indent += 2;
    }
    private void IndentMinus()
    {
        Indent -= 2;
    }
    public override void VisitIdNode(IdNode id) 
    {
        Text += id.Name;
    }
    public override void VisitIntNumNode(IntNumNode num) 
    {
        Text += num.Num.ToString();
    }
    public override void VisitBinOpNode(BinOpNode binop) 
    {
        Text += "(";
        binop.Left.Visit(this);
        Text += " " + binop.Op + " ";
        binop.Right.Visit(this);
        Text += ")";
    }
    public override void VisitAssignNode(AssignNode a) 
    {
        Text += IndentStr();
        a.Id.Visit(this);
        Text += " := ";
        a.Expr.Visit(this);
    }
    public override void VisitCycleNode(CycleNode c) 
    {
        Text += IndentStr() + "cycle ";
        c.Expr.Visit(this);
        Text += Environment.NewLine;
        c.Stat.Visit(this);
    }
    public override void VisitBlockNode(BlockNode bl) 
    {
        Text += IndentStr() + "begin" + Environment.NewLine;
        IndentPlus();

        var Count = bl.StList.Count;

        if (Count>0)
            bl.StList[0].Visit(this);
        for (var i = 1; i < Count; i++)
        {
            Text += ';';
            if (!(bl.StList[i] is EmptyNode))
                Text += Environment.NewLine;
            bl.StList[i].Visit(this);
        }
        IndentMinus();
        Text += Environment.NewLine + IndentStr() + "end";
    }
    public override void VisitWriteNode(WriteNode w) 
    {
        Text += IndentStr() + "write(";
        w.Expr.Visit(this);
        Text += ")";
    }
    public override void VisitVarDefNode(VarDefNode w) 
    {
        Text += IndentStr() + "var " + w.vars[0].Name;
        for (int i = 1; i < w.vars.Count; i++)
            Text += ',' + w.vars[i].Name;
    }
}

Комментарии к визитору PrettyPrintVisitor

Для данного визитора все методы необходимо переопределять.
Вызов методов Visit для подузлов перемежается с накоплением информации в переменной Text в достаточно нетривиальном порядке.
Не все узлы, имеющие подузлы, вызывают Visit для подузлов. Например, VisitVarDefNode вместо этого осуществляет непосредственный доступ к переменным, являющимся идентификаторами.

Участок основной программы, вызывающий визитор PrettyPrintVisitor

var pp = new PrettyPrintVisitor();
parser.root.Visit(pp);
Console.WriteLine(pp.Text);

Основные задания (8 баллов)

Написать визитор, определяющий среднее количество операторов в теле каждого цикла программы (1 балл)
Написать визитор, определяющий наиболее часто используемую переменную. (1 балл)
Написать визитор, определяющий стоимость вычисления каждого выражения. Стоимость операций умножения и деления положить равной 3, а стоимость сложения и вычитания - равной 1. (1 балл)
Написать визитор, меняющий имя переменной с одного на другое (1 балл)
Написать визитор, определяющий максимальную вложенность циклов (1 балл)
Реализовать оператор if ... then ... else (полная и неполная формы). Для него реализовать синтаксический узел, метод Visit... в визиторе, вывод в PrettyPrintVisitor. Написать визитор, определяющий максимальную вложенность циклов и конструкций if ... then ... else. Например, в cycle 3 if 1 then cycle 4 a := 1 максимальная вложенность конструкций составляет 3. (3 балла)

Дополнительные задания

Нет