Я нахожусь в процессе создания своего собственного языка программирования, который я делаю для целей обучения. Я уже написал лексер и парсер рекурсивного спуска для подмножества моего языка (в настоящее время я поддерживаю математические выражения, такие как + - * /
и круглые скобки). Парсер возвращает мне абстрактное синтаксическое дерево, в котором я вызываю Evaluate
метод для получения результата выражения. Все отлично работает Вот примерно моя текущая ситуация (примеры кода на C #, хотя это в значительной степени не зависит от языка):
public abstract class Node
{
public abstract Double Evaluate();
}
public class OperationNode : Node
{
public Node Left { get; set; }
private String Operator { get; set; }
private Node Right { get; set; }
public Double Evaluate()
{
if (Operator == "+")
return Left.Evaluate() + Right.Evaluate();
//Same logic for the other operators
}
}
public class NumberNode : Node
{
public Double Value { get; set; }
public Double Evaluate()
{
return Value;
}
}
Однако я хотел бы отделить алгоритм от узлов дерева, потому что я хочу применить принцип Open / Closed, чтобы мне не пришлось заново открывать каждый класс узлов, когда я хочу реализовать генерацию кода, например. Я читал, что Шаблон посетителя хорош для этого. Я хорошо понимаю, как работает шаблон, и что использование двойной диспетчеризации - это путь. Но из-за рекурсивной природы дерева я не уверен, как мне к нему подойти. Вот как будет выглядеть мой посетитель:
public class AstEvaluationVisitor
{
public void VisitOperation(OperationNode node)
{
// Here is where I operate on the operation node.
// How do I implement this method?
// OperationNode has two child nodes, which may have other children
// How do I work the Visitor Pattern around a recursive structure?
// Should I access children nodes here and call their Accept method so they get visited?
// Or should their Accept method be called from their parent's Accept?
}
// Other Visit implementation by Node type
}
Так что это моя проблема. Я хочу немедленно заняться этим, пока мой язык не поддерживает большую функциональность, чтобы избежать более серьезной проблемы в дальнейшем.
Я не опубликовал это в StackOverflow, потому что я не хочу, чтобы вы предоставили реализацию. Я только хочу, чтобы вы поделились идеями и концепциями, которые я, возможно, пропустил, и как я должен подходить к этому.
источник
Ответы:
Реализация посетителя должна решить, посещать ли дочерние узлы и в каком порядке. Вот и весь смысл шаблона посетителя.
Чтобы адаптировать посетителя к большему количеству ситуаций, полезно (и довольно часто) использовать такие обобщения, как это (это Java):
И
accept
метод будет выглядеть так:Это позволяет передавать дополнительные параметры посетителю и извлекать из него результат. Таким образом, оценка выражения может быть реализована так:
Параметр
accept
method не используется в приведенном выше примере, но поверьте мне: он очень полезен. Например, это может быть экземпляр Logger, чтобы сообщить об ошибках.источник
Я реализовал шаблон посетителя на рекурсивном дереве раньше.
Моя конкретная рекурсивная структура данных была предельно простой - всего три типа узлов: общий узел, внутренний узел с дочерними элементами и конечный узел с данными. Это намного проще, чем я предполагаю, что ваш AST будет, но, возможно, идеи могут масштабироваться.
В моем случае я сознательно не позволил узлу Accept узла с детьми вызвать Accept для его потомков или вызвать visitor.Visit (child) изнутри Accept. Правильная реализация посетителя-члена «Посетить» отвечает за делегирование Приемок дочерним узлам посещаемого узла. Я выбрал этот способ, потому что хотел, чтобы разные реализации Visitor могли определять порядок посещения независимо от представления дерева.
Второе преимущество заключается в том, что внутри узлов моего дерева почти нет артефактов шаблона «Посетитель» - каждый «Принять» просто вызывает «Посетить» посетителя с правильным конкретным типом. Это облегчает поиск и понимание логики посещения, это все внутри реализации посетителя.
Для ясности я добавил псевдокод C ++ - ish. Сначала узлы:
И посетитель:
источник
allow different Visitor implementations to be able to decide the order of visitation
. Очень хорошая идея.Вы работаете с шаблоном посетителей вокруг рекурсивной структуры так же, как вы делаете что-либо еще с вашей рекурсивной структурой: рекурсивно посещая узлы в вашей структуре.
источник