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

Текущая версия на 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 балла)

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

Нет