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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Новая страница: «===Общие комментарии=== ===Паттерн Визитор=== ===Пример простого визитора=== ===Визитор для со…»)
 
(→‎Основные задания (8 баллов))
 
(не показано 30 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
__NOTOC__
 +
[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]]
 +
 +
===Код проекта===
 +
Комплект для практического занятия [http://pascalabc.net/downloads/CompilerConstruction/SimpleLanguage2.zip скачиваем отсюда].
 +
 
===Общие комментарии===
 
===Общие комментарии===
 +
Синтаксическое дерево построено - что дальше?
 +
 +
По синтаксическому дереву можно:
 +
* проанализировать некоторую статистику программы (например, количество операторов присваивания),
 +
* восстановить текст программы (причем, не обязательно на том же языке)
 +
* отформатировать текст программы (создать так называемый Pretty Printer)
 +
* сгенерировать код программы на некотором целевом языке
 +
* выполнить интерпретацию программы
 +
 +
Для каждого такого действия придется совершать обход всех узлов дерева в некотором порядке и совершать действие над каждым узлом в зависимости от типа узла.
 +
 +
При этом, в результате выполнения такого действия будут, как правило, накапливаться некоторые внешние данные (количество операторов присваивания или список команд целевого кода)
 +
 +
Одно из решений - реализовать каждое действие в виде '''виртуального метода''' и переопределить этот метод в каждом типе узлов дерева. Например, реализовать в каждом синтаксическом узле
 +
метод Print для вывода текста программы, метод Generate для генерации участка кода, метод Interpret - для выполнения команды интерпретатора и т.д.
 +
 +
Очевидно, что такое решение захламляет интерфейс каждого узла, делая его тяжеловесным. К тому же, остается открытым вопрос - как хранить внешние данные для каждого такого действия.
 +
 +
Именно для решения подобных проблем и используется '''паттерн Визитор'''.
  
 
===Паттерн Визитор===
 
===Паттерн Визитор===
 +
==== Общие сведения о паттерне Визитор====
 +
[[Посетитель_(Visitor)|Описание паттерна Посетитель в курсе Паттерны проектирования]]
 +
 +
==== Базовый абстрактный класс визитора====
 +
Для реализации паттерна Визитор в нашем проекте имеется файл Visitor.cs, содержащий абстрактный класс
 +
<source lang="Csharp">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) { }
 +
}</source>
 +
с методами для обхода каждого типа узла.
 +
 +
Кроме этого, в базовом классе для всех узлов определим абстрактный метод Visit, которому передадим текущий визитор в качестве параметра.
 +
<source lang="Csharp">public abstract class Node   
 +
{
 +
    public abstract void Visit(Visitor v);
 +
}
 +
</source>
 +
 +
и в каждом узле синтаксического дерева, который требуется обходить, переопределим метод Visit, вызывая из него соответствующий метод Visit...Node. Например, для AssignNode он будет выглядеть так:
 +
 +
<source lang="Csharp">public override void Visit(Visitor v)
 +
{
 +
  v.VisitAssignNode(this);
 +
}</source>
 +
 +
==== Класс автовизитора с автоматическим обходом компонент====
 +
Для большинства целей при обходе узла дерева с потомками необходимо обойти также потомков. При этом порядок обхода потомков неважен.
 +
 +
Определим в этом случае так называемый Автовизитор, который будет обходить и потомков, при этом не совершая никаких действий.
 +
 +
<source lang="Csharp">
 +
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);
 +
    }
 +
}
 +
</source>
  
 
===Пример простого визитора===
 
===Пример простого визитора===
 +
Рассмотрим простой визитор подсчета количества операторов присваивания во всей программе:
 +
 +
<source lang="Csharp">class AssignCountVisitor : AutoVisitor
 +
{
 +
    public int Count = 0;
 +
    public override void VisitAssignNode(AssignNode a)
 +
    {
 +
        Count += 1;
 +
    }
 +
}
 +
</source>
 +
Как видим, его код максимально прост: переопределен метод посещения узла AssignNode, в котором увеличивается счетчик количества присваиваний.
 +
Счетчик количества присваиваний является полем самого класса AssignCountVisitor и не захламляет внешний код.
 +
 +
Вызов данного визитора в основной программе:
 +
 +
<source lang="Csharp">
 +
var avis = new AssignCountVisitor();
 +
parser.root.Visit(avis);
 +
Console.WriteLine("Количество присваиваний = {0}", avis.Count);
 +
</source>
 +
 +
Несмотря на внешнюю простоту, визитор имеет достаточно сложный алгоритм работы. Проследим выполнение метода parser.root.Visit(avis):
 +
* parser.root.Visit(avis) вызывает код
 +
avis.VisitBlockNode(this);
 +
где this = parser.root. Таким образом, срабатыват
 +
avis.VisitBlockNode(parser.root);
 +
который вызывает метод базового класса AutoVisit.VisitBlockNode со следующим содержимым:
 +
<source lang="Csharp">foreach (var st in bl.StList)
 +
  st.Visit(this);
 +
</source>
 +
Посещение каждого st осуществляется виртуальным методом Visit, который для каждого типа узла свой. В частности, если st - узел присваивания, то в нем вызывается
 +
v.VisitAssignNode(st);
 +
который и вызывает определенный нами код:
 +
<source lang="Csharp">public override void VisitAssignNode(AssignNode a)
 +
{
 +
  Count += 1;
 +
}</source>
 +
Вложенные узлы присваивания возникают в составных операторах, обход которых по-прежнему определен в AutoVisit.VisitBlockNode.
 +
 +
Если программа содержит циклы, то они обходятся с помощью AutoVisit.VisitCycleNode, который автоматически обходит своё тело, где также могут встретиться присваивания.
 +
 +
Наконец, заметим, что при обходе самого присваивания мы не обходим узлы-потомки (идентификатор и выражение), тем самым выбрасывая целое поддерево выражения из процесса обхода.
 +
 +
К сожалению, узлы WriteNode и VarDefNode обходят своих потомков, заведомо не содержащих операторов присваиваний. Поэтому переопределим в AssignCountVisitor обход этих узлов, сделав его пустым:
 +
 +
<source lang="Csharp">public override void VisitWriteNode(WriteNode w)
 +
{
 +
}
 +
public override void VisitVarDefNode(VarDefNode w)
 +
{
 +
}
 +
</source>
  
 
===Визитор для создания Pretty Printerа===
 
===Визитор для создания Pretty Printerа===
 +
Данный визитор генерирует во внутренней переменной Text текст отформатированной программы.
 +
 +
Для отступов поддерживается переменная Indent, которая увеличивается на 2 всякий раз при входе в блок и уменьшается на 2 - перед выходом из блока.
 +
 +
====Код визитора PrettyPrintVisitor====
 +
<source lang="Csharp">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;
 +
    }
 +
}
 +
</source>
 +
====Комментарии к визитору PrettyPrintVisitor====
 +
*Для данного визитора все методы необходимо переопределять. 
 +
*Вызов методов Visit для подузлов перемежается с накоплением информации в переменной Text в достаточно нетривиальном порядке.
 +
*Не все узлы, имеющие подузлы, вызывают Visit для подузлов. Например, VisitVarDefNode вместо этого осуществляет непосредственный доступ к переменным, являющимся идентификаторами.
 +
 +
====Участок основной программы, вызывающий визитор PrettyPrintVisitor====
 +
<source lang="Csharp">var pp = new PrettyPrintVisitor();
 +
parser.root.Visit(pp);
 +
Console.WriteLine(pp.Text);
 +
</source>
 +
 +
===Основные задания (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 балла)
 +
 +
===Дополнительные задания===
 +
Нет

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

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

Нет

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Визиторы_по_синтаксическому_дереву&oldid=6149»