Визиторы по синтаксическому дереву
Код проекта
Комплект для практического занятия скачиваем отсюда.
Общие комментарии
Синтаксическое дерево построено - что дальше?
По синтаксическому дереву можно:
- проанализировать некоторую статистику программы (например, количество операторов присваивания),
- восстановить текст программы (причем, не обязательно на том же языке)
- отформатировать текст программы (создать так называемый 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);Основные задания (4 балла)
- Написать визитор, определяющий среднее количество операторов во теле цикла программы
- Написать визитор, определяющий наиболее часто используемую переменную.
- Написать визитор, определяющий стоимость вычисления каждого выражения. Стоимость операций умножения и деления положить равной 3, а стоимость сложения и вычитания - равной 1.
- Написать визитор, меняющий имя переменной с одного на другое
- Написать визитор, определяющий
Дополнительные задания
Нет
