283
Пример кода
Приведенный ниже код на языке C++ дает представление о реализации классов
Command
, обсуждавшихся в разделе «Мотивация». Мы определим классы
OpenCommand
,
PasteCommand и
MacroCommand
. Начнем с абстрактного класса
Command
:
class Command { public: virtual
Command(); virtual void Execute() = 0; protected:
Command();
};
Команда
OpenCommand открывает документ, имя которому задает пользова- тель. Конструктору
OpenCommand передается объект
Application
. Функция
AskUser запрашивает у пользователя имя открываемого документа:
class OpenCommand : public Command { public:
OpenCommand(Application*); virtual void Execute(); protected:
virtual const char* AskUser();
private:
Application* _application;
char* _response;
};
OpenCommand::OpenCommand (Application* a) {
_application = a;
} void OpenCommand::Execute () {
const char* name = AskUser();
if (name != 0) {
Document* document = new Document(name);
_application->Add(document); document->Open();
}
}
Команде
PasteCommand должен передаваться объект
Document
, являющийся получателем. Он передается в параметре конструктора
PasteCommand
:
class PasteCommand : public Command { public:
PasteCommand(Document*);
284
Глава 5. Паттерны поведения virtual void Execute(); private:
Document* _document;
};
PasteCommand::PasteCommand (Document* doc)
{
_document = doc;
}
void PasteCommand::Execute ()
{
_document->Paste();
}
Для простых команд, не допускающих отмены и не требующих аргументов, можно воспользоваться шаблоном класса для параметризации получателя.
Определим для них шаблонный подкласс
SimpleCommand
, который пара- метризуется типом получателя
Receiver и хранит связь между объектом- получателем и действием, представленным указателем на функцию класса:
template
class SimpleCommand : public Command {
public: typedef void (Receiver::* Action)();
SimpleCommand(Receiver* r, Action a) :
_receiver(r), _action(a) { } virtual void Execute(); private:
Action _action;
Receiver* _receiver;
};
Конструктор сохраняет информацию о получателе и действии в соответ- ствующих переменных экземпляра. Операция
Execute просто выполняет действие по отношению к получателю:
template
void SimpleCommand<Receiver>::Execute ()
{
(_receiver->*_action)();
}
Чтобы создать команду, которая вызывает операцию
Action для экземпляра класса
MyClass
, клиент пишет следующий код:
MyClass* receiver = new MyClass;
// ...
Command* aCommand =
Паттерн Command (команда)
285
new SimpleCommand(receiver, &MyClass::Action);
// ...
aCommand->Execute();
Имейте в виду, что такое решение годится только для простых команд. Для более сложных команд, которые отслеживают не только получателей, но и аргументы, и, возможно, состояние, необходимое для отмены операции, приходится порождать подклассы от класса
Command
Класс
MacroCommand управляет выполнением последовательности подкоманд и предоставляет операции для добавления и удаления подкоманд. Задавать получателя не требуется, так как в каждой подкоманде уже определен свой получатель:
class MacroCommand : public Command {
public:
MacroCommand();
virtual MacroCommand();
virtual void Add(Command*);
virtual void Remove(Command*);
virtual void Execute();
private:
List* _cmds;
};
Основой класса
MacroCommand является его функция
Execute
. Она обходит все подкоманды и для каждой вызывает ее операцию
Execute
:
void MacroCommand::Execute () {
ListIterator i(_cmds);
for (i.First(); !i.IsDone(); i.Next()) {
Command* c = i.CurrentItem(); c->Execute();
}
}
Обратите внимание: если бы в классе
MacroCommand была реализована опе- рация отмены
Unexecute
, то при ее выполнении подкоманды должны были бы отменяться в порядке, обратном порядку их применения в реализации
Execute
Наконец, в классе
MacroCommand должны быть операции для добавления и удаления подкоманд:
void MacroCommand::Add (Command* c) {
_cmds->Append(c);
}
286 Глава 5. Паттерны поведения void MacroCommand::Remove (Command* c) {
_cmds->Remove(c);
}
Известные применения
Вероятно, впервые паттерн команда появился в работе Генри Либермана
(Henry Lieberman) [Lie85]. В системе MacApp [App89] команды широко применяются для реализации допускающих отмену операций. В ET++
[WGM88], InterViews [LCI+92] и Unidraw [VL90] также имеются классы, описываемые паттерном команда. Так, в библиотеке InterViews определен абстрактный класс
Action
, который определяет функциональность команд.
Также определяется шаблон
ActionCallback
, параметризованный методом действия, который автоматически создает экземпляры подклассов команд.
В библиотеке классов THINK [Sym93b] также используются команды для поддержки отмены операций. В THINK команды называются
задачами (Tasks). Объекты
Task передаются по цепочке обязанностей (263), пока не будут кем-то обработаны.
Объекты команд в каркасе Unidraw уникальны в том отношении, что могут вести себя подобно сообщениям. В Unidraw команду можно послать другому объекту для интерпретации, результат которой зависит от объекта-полу- чателя. Более того, сам получатель может делегировать интерпретацию следующему объекту, обычно своему родителю. Это напоминает паттерн цепочка обязанностей. Таким образом, в Unidraw получатель вычисляется, а не хранится. Механизм интерпретации в Unidraw использует информацию о типе, доступную во время выполнения.
Джеймс Коплиен описывает, как в языке C++ реализуются
функторы — объекты, ведущие себя, как функции [Cop92]. Перегрузка оператора вызова operator()
делает его использование более прозрачным. Смысл паттерна команда в другом — он устанавливает и поддерживает
связь между полу- чателем и функцией (то есть действием), а не просто функцию.
Родственные паттерны
Паттерн компоновщик (196) можно использовать для реализации макро- команд.
Паттерн хранитель (330)
может сохранять состояние, необходимое команде для отмены ее действия.
Команда, которую нужно копировать перед помещением в список истории, ведет себя, как прототип (146).
Паттерн Interpreter (интерпретатор)
287
ПАТТЕРН INTERPRETER (ИНТЕРПРЕТАТОР)
Название и классификация паттерна
Интерпретатор — паттерн поведения классов.
Назначение
Для заданного языка определяет представление его грамматики, а также интерпретатор предложений этого языка.
Мотивация
Если некоторая задача встречается достаточно часто, то имеет смысл пред- ставить ее конкретные проявления в виде предложений на простом языке.
После этого можно создать интерпретатор, который решает задачу, анали- зируя предложения этого языка.
Например, поиск строк по образцу — весьма распространенная задача. Регу- лярные выражения — это стандартный язык для задания образцов поиска.
Вместо того чтобы программировать специализированные алгоритмы для сопоставления строк с каждым образцом, алгоритм поиска может интерпре- тировать регулярное выражение, описывающее множество подходящих строк.
Паттерн интерпретатор определяет грамматику простого языка, представляет предложения на этом языке и интерпретирует их. Для приведенного при- мера паттерн описывает определение грамматики и интерпретации языка регулярных выражений.
Допустим, они описываются следующей грамматикой:
expression ::= literal | alternation | sequence | repetition |
'(' expression ')'
alternation ::= expression '|' expression sequence ::= expression '&' expression repetition ::= expression '*'
literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*
где expression
— начальный символ, а literal
— терминальный символ, определяющий простые слова.
Паттерн интерпретатор использует класс для представления каждого правила грамматики. Символы в правой части правила — это переменные экзем- пляров таких классов. Для представления приведенной выше грамматики требуется пять классов: абстрактный класс
RegularExpression и четыре его
288
Глава 5. Паттерны поведения подкласса
LiteralExpression
,
AlternationExpression
,
SequenceExpression и
RepetitionExpression
. В последних трех подклассах определены пере- менные для хранения подвыражений.
RegularExpression
Interpret()
Interpret()
RepetitionExpression
Interpret()
Повторение
Альтернатива1
Альтернатива2
Выражение1
Выражение2
AlternationExpression
Interpret()
SequenceExpression
Interpret()
literal
LiteralExpression
Каждое регулярное выражение, описываемое этой грамматикой, представля- ется в виде абстрактного синтаксического дерева, в узлах которого находятся экземпляры этих классов. Например, дерево
aSequenceExpression
Выражение1
Выражение2
anAlternationExpression
Альтернатива1
Альтернатива2
aLiteralExpression
'raining'
aLiteralExpression
'dogs'
aLiteralExpression
'cats'
aRepetitionExpression
Повторить
Паттерн Interpreter (интерпретатор)
289представляет выражение raining & (dogs | cats) *
Чтобы создать интерпретатор регулярных выражений, можно определить в каждом подклассе
RegularExpression операцию
Interpret
,
получающую в аргументе контекст, в котором должно интерпретироваться выражение.
Контекст состоит из входной строки и информации о текущем состоянии по- иска совпадения. В каждом подклассе
RegularExpression операция
Interpret ищет совпадение следующей части входной строки с учетом текущего кон- текста. Например:
LiteralExpression проверяет, соответствует ли входная строка литера- лу, который хранится в объекте подкласса;
AlternationExpression проверяет, соответствует ли строка одной из альтернатив;
RepetitionExpression проверяет, имеются ли в входной строке повторя- ющиеся соответствия выражения;
и так далее.
Применимость
Используйте паттерн интерпретатор в ситуациях, когда имеется интерпрети- руемый язык, конструкции которого можно представить в виде абстрактных синтаксических деревьев. Этот паттерн лучше всего работает в следующих случаях:
грамматика проста. Для сложных грамматик иерархия классов стано- вится слишком громоздкой и неуправляемой. В таких случаях лучше применять парсеры-генераторы, поскольку они могут интерпретиро- вать выражения без построения абстрактных синтаксических деревьев, что экономит память (а возможно, и время);
эффективность не является главным критерием. Наиболее эффектив- ные интерпретаторы обычно
не работают непосредственно с деревья- ми, а сначала транслируют их в другую форму. Так, регулярное выра- жение часто преобразуется в конечный автомат. Но даже в этом случае сам
транслятор можно реализовать с помощью паттерна интерпре- татор.
290 Глава 5. Паттерны поведения
Структура
NonterminalExpressionInterpret(
Context)
ClientContextAbstractExpressionInterpret(Context)TerminalExpressionInterpret(Context)
Участники
AbstractExpression (
RegularExpression
) — абстрактное выражение:
• объявляет абстрактную операцию
Interpret
, общую для всех узлов в абстрактном синтаксическом дереве;
TerminalExpression (
LiteralExpression
) — терминальное выражение:
• реализует операцию
Interpret для
терминальных символов грамма- тики;
• необходим отдельный экземпляр для каждого терминального символа в предложении;
NonterminalExpression (
AlternationExpression
,
RepetitionExpression
,
SequenceExpressions
) — нетерминальное выражение:
• по одному такому классу требуется для каждого грамматического правила R :: = R
1
R
2
...R
n;
• хранит переменные экземпляра типа
AbstractExpression для каждого символа от R
1
до R
n;
• реализует операцию
Interpret для нетерминальных символов грам- матики. Эта операция рекурсивно вызывает себя же для переменных, представляющих R
1
, ... R
n;
Context — контекст:
• содержит информацию, глобальную по отношению к интерпрета- тору;
Паттерн Interpreter (интерпретатор)
291
Client — клиент:
• строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее отдельное предложение на языке с дан- ной грамматикой. Дерево собирается из экземпляров классов
NonterminalExpression и
TerminalExpression
;
• вызывает операцию
Interpret
Отношения
клиент строит (или получает в готовом виде) конструкцию в виде аб- страктного синтаксического дерева, в узлах которого находятся объек- ты классов
NonterminalExpression и
TerminalExpression
. Затем клиент инициализирует контекст и вызывает операцию
Interpret
;
в каждом узле вида
NonterminalExpression через операции
Interpret определяется операция
Interpret для каждого подвыражения. Для класса
TerminalExpression операция
Interpret определяет базу рекур- сии;
операции
Interpret в каждом узле используют контекст для сохране- ния и доступа к состоянию интерпретатора.
Результаты
Основные достоинства и недостатки паттерна интерпретатор:
простота изменения и расширения грамматики. Поскольку для пред- ставления грамматических правил в паттерне используются классы, то для изменения или расширения грамматики можно применять наследо- вание. Существующие
выражения можно модифицировать постепенно, а новые определять как вариации старых;
простая реализация грамматики. Реализации классов, описывающих узлы абстрактного синтаксического дерева, похожи. Такие классы легко программируются, а зачастую они могут автоматически генерироваться генератором компиляторов или парсером-генератором;
сложность сопровождения сложных грамматик. В паттерне интерпре- татор определяется по меньшей мере один класс для каждого правила грамматики (для правил, определенных с помощью формы Бэкуса —
Наура — BNF, может понадобиться и более одного класса). Поэтому сопровождение грамматики с большим числом правил иногда оказы- вается трудной задачей. Для ее решения могут быть применены другие паттерны (см. раздел «Реализация»). Но если грамматика очень сложна,
292 Глава 5. Паттерны поведения лучше прибегнуть к другим методам, например воспользоваться генера- тором компиляторов или парсером-генератором;
добавление новых способов интерпретации выражений. Паттерн интер- претатор позволяет легко изменить способ вычисления выражений. На- пример, реализовать красивую печать выражения вместо проверки вхо- дящих в него типов можно, просто определив новую операцию в классах выражений. Если вам приходится часто создавать новые способы ин- терпретации выражений, подумайте о применении паттерна посети- тель (379). Это поможет избежать изменения классов, описывающих грамматику.
Реализация
У реализаций паттернов интерпретатор и компоновщик (196) много общего.
Следующие аспекты относятся только к интерпретатору:
создание абстрактного синтаксического дерева.
Паттерн интерпретатор не поясняет, как создавать дерево, то есть разбор выражения не вхо- дит в его задачу. Абстрактное дерево разбора можно строить таблично- управляемым или написанным вручную парсером (обычно методом ре- курсивного спуска), а также самим клиентом;
определение операции Interpret. Определять операцию
Interpret в клас- сах выражений необязательно. Если создавать новые интерпретаторы приходится часто, то лучше воспользоваться паттерном посетитель и по- местить операцию
Interpret в отдельный объект-посетитель. Напри- мер, для грамматики языка программирования будет нужно определить много операций над абстрактными синтаксическими деревьями: про- верку типов, оптимизацию, генерацию кода и т. д. Лучше, конечно, ис- пользовать посетителя и не определять эти операции в каждом классе грамматики;
разделение терминальных символов с помощью паттерна «приспособле-нец». Для грамматик, предложения которых содержат много вхождений одного и того же терминального символа, может оказаться полезным разделение этого символа. Хорошим примером служат грамматики компьютерных программ, поскольку в них каждая переменная встре- чается в коде многократно. В примере из раздела «Мотивация» терми- нальный символ
dog (для моделирования которого используется класс
LiteralExpression
) может встречаться многократно.
В терминальных узлах обычно не хранится информация о положении в абстрактном синтаксическом дереве. Необходимый для интерпретации
Паттерн Interpreter (интерпретатор)
293контекст предоставляют им родительские узлы. Налицо различие между разделяемым (внутренним) и передаваемым (внешним) состояниями, так что вполне применим паттерн приспособленец (231).
Например, каждый экземпляр класса
LiteralExpression для
dog полу- чает контекст, состоящий из уже просмотренной части строки. И каждый такой экземпляр делает в своей операции
Interpret одно и то же — про- веряет, содержит ли остаток входной строки слово
dog, — независимо от того, в каком месте дерева этот экземпляр встречается.
Пример кода
Ниже приведены два примера. Первый — законченная программа на Smalltalk для проверки того, существует ли в заданной последовательности совпаде- ние регулярного выражения. Второй — программа на C++ для вычисления булевых выражений.
Программа сопоставления с регулярным выражением проверяет, является ли строка корректным предложением языка, определяемого этим выражением.
Регулярное выражение определено следующей грамматикой:
expression ::= literal | alternation | sequence | repetition |
'(' expression ')'
alternation ::= expression '|' expression sequence ::= expression '&' expression repetition ::= expression 'repeat'
literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*
Между этой грамматикой и той, что приведена в разделе «Мотивация», есть небольшие отличия. Мы слегка
изменили синтаксис регулярных выраже- ний, поскольку в Smalltalk символ
*
не может быть постфиксной операцией, поэтому вместо него употребляется слово repeat
. Например, регулярное выражение
(('dog ‘ | ‘cat ‘) repeat & ‘weather’) соответствует входной строке 'dog dog cat weather’
Для реализации программы сопоставления мы определим пять классов, упомянутых на с. 379. В классе
SequenceExpression есть переменные экземпляра expression1
и expression2
для хранения ссылок на потомков в дереве. Класс
AlternationExpression хранит альтернативы в переменных экземпляра alternative1
и alternative2
, а класс
RepetitionExpression
— повторяемое выражение в переменной экземпляра repetition
. В классе
Скачать 6.37 Mb.