294
Глава 5. Паттерны поведения
LiteralExpression есть переменная экземпляра components для хранения списка объектов (скорее всего, символов), представляющих литеральную строку, которая должна соответствовать входной строке.
Операция match:
реализует интерпретатор регулярных выражений. Эта операция реализована в каждом из классов, входящих в абстрактное синтак- сическое дерево. Ее аргументом является переменная inputState
, описыва- ющая текущее состояние процесса сопоставления, то есть уже прочитанную часть входной строки.
Текущее состояние характеризуется множеством входных потоков, представ- ляющим множество тех входных строк, которое регулярное выражение могло бы к настоящему моменту принять. (Это примерно то же, что регистрация всех состояний, в которых побывал бы эквивалентный конечный автомат, распознавший входной поток до данного места.)
Текущее состояние наиболее важно для операции repeat
. Например, регу- лярному выражению 'a' repeat интерпретатор сопоставил бы строки "a"
,
"aa"
,
"aaa"
и т. д. А регулярному выражению 'a’ repeat & ‘bc’
строки "abc"
,
"aabc"
,
"aaabc"
и т. д. Но для регулярного выражения 'a' repeat & 'abc' сопоставление входной строки "aabc"
с подвыражением "'a' repeat"
дало бы два потока, один из которых соответствует одному входному символу, а другой — двум. Из них лишь поток, принявший один символ, может быть сопоставлен с остатком строки "abc"
Теперь рассмотрим определения match:
для каждого класса, описывающе- го регулярное выражение.
SequenceExpression производит сопоставление с каждым подвыражением в определенной последовательности. Обычно потоки ввода не включаются в его состояние inputState match: inputState
^ expression2 match: (expression1 match: inputState).
AlternationExpression возвращает результат, объединяющий состояния всех альтернатив. Определение match:
для этого случая выглядит так:
Паттерн Interpreter (интерпретатор)
295match: inputState
| finalState |
finalState := alternative1 match: inputState.
finalState addAll: (alternative2 match: inputState).
^ finalState
Операция match
: для
RepetitionExpression пытается найти максимальное количество состояний, допускающих сопоставление:
match: inputState
| aState finalState |
aState := inputState.
finalState := inputState copy.
[aState isEmpty]
whileFalse:
[aState := repetition match: aState.
finalState addAll: aState].
^ finalState
На выходе этой операции мы обычно получаем больше состояний, чем на входе, поскольку
RepetitionExpression
может быть сопоставлено с одним, двумя или более вхождениями повторяющегося выражения во входную строку. В выходном состоянии представлены все возможные варианты, а ре- шение о том, какое из состояний правильно, принимается последующими элементами регулярного выражения.
Наконец, операция match:
для
LiteralExpression сравнивает свои компо- ненты с каждым возможным входным потоком и оставляет только те из них, для которых попытка завершилась удачно:
match: inputState
| finalState tStream | finalState := Set new. inputState do:
[:stream | tStream := stream copy.
(tStream nextAvailable: components size
) = components ifTrue: [finalState add: tStream]
].
^ finalState
Сообщение nextAvailable:
выполняет смещение вперед по входному потоку.
Это единственная операция match:
, которая сдвигается по потоку. Обратите внимание: возвращаемое состояние содержит его копию, поэтому можно быть
296
Глава 5. Паттерны поведения уверенным, что сопоставление с литералом никогда не изменяет входной по- ток. Это существенно, поскольку все альтернативы в
AlternationExpression должны «видеть» идентичные копии входного потока.
Итак, классы, составляющие абстрактное синтаксическое дерево, опреде- лены; теперь опишем процесс его построения. Вместо того чтобы создавать парсер регулярных выражений, мы определим некоторые операции в классах
RegularExpression
, так что вычисление выражения языка Smalltalk приведет к созданию абстрактного синтаксического дерева для соответствующего ре- гулярного выражения. Тем самым мы будем использовать встроенный ком- пилятор Smalltalk, как если бы это был парсер для регулярных выражений.
Для построения дерева нам понадобятся операции "|"
,
"repeat"
и "&"
над регулярными выражениями. Определим эти операции в классе
RegularExpression
:
& aNode
^ SequenceExpression new expression1: self expression2: aNode asRExp repeat
^ RepetitionExpression new repetition: self
| aNode
^ AlternationExpression new alternative1: self alternative2: aNode asRExp asRExp
^ self
Операция asRExp преобразует литералы в
RegularExpression
. Следующие операции определены в классе
String
:
& aNode
^ SequenceExpression new expression1: self asRExp expression2: aNode asRExp repeat
^ RepetitionExpression new repetition: self
| aNode
^ AlternationExpression new alternative1: self asRExp alternative2: aNode asRExp asRExp
^ LiteralExpression new components: self
Если бы эти операции были определены выше в иерархии классов
(
SequenceableCollection в Smalltalk-80,
IndexedCollection в Smalltalk/V),
Паттерн Interpreter (интерпретатор)
297то они появились бы и в таких классах, как
Array и
OrderedCollection
. Это позволило бы сопоставлять регулярные выражения с последовательностями объектов любого вида.
Второй пример — это система для
манипулирования и вычисления булевых выражений, реализованная на C++. Терминальными символами в этом языке являются булевы переменные, то есть константы true и false
. Не- терминальные символы представляют выражения, содержащие операторы and
, or и not
. Определение грамматики выглядит так
1
:
BooleanExp ::= VariableExp | Constant | OrExp | AndExp | NotExp |
'(' BooleanExp ')'
AndExp ::= BooleanExp 'and' BooleanExp
OrExp ::= BooleanExp 'or' BooleanExp
NotExp ::= 'not' BooleanExp
Constant ::= 'true' | 'false'
VariableExp ::= 'A' | 'B' | ... | ‘X’ | ‘Y’ | ‘Z’
Определим две операции над булевыми выражениями. Первая —
Evaluate
— вычисляет выражение в контексте, где каждой переменной присваивается истинное или ложное значение. Вторая —
Replace
— порождает новое булево выражение, заменяя выражением некоторую переменную. Эта операция демонстрирует, что паттерн интерпретатор можно использовать не только для вычисления выражений; в данном случае он манипулирует самим вы- ражением.
Здесь подробно описываются только классы
BooleanExp,
VariableExp и
AndExp
. Классы
OrExp и
NotExp аналогичны классу
AndExp
. Класс
Constant представляет булевы константы.
В классе
BooleanExp определен интерфейс всех классов, которые описывают булевы выражения:
class BooleanExp {
public:
BooleanExp(); virtual BooleanExp();
virtual bool Evaluate(Context&) = 0;
virtual BooleanExp* Replace(const char*, BooleanExp&) = 0;
virtual BooleanExp* Copy() const = 0;
};
1
Для простоты мы игнорируем приоритеты операторов и предполагаем, что этой про- блемой должен заниматься объект, строящий дерево разбора.
298
Глава 5. Паттерны поведения
Класс
Context определяет соответствие между переменными и булевыми значениями, которые в C++ представляются константами true и false
Возьмем следующий интерфейс:
class Context {
public:
bool Lookup(const char*) const;
void Assign(VariableExp*, bool);
};
Класс
VariableExp представляет именованную переменную:
class VariableExp : public BooleanExp {
public:
VariableExp(const char*);
virtual VariableExp();
virtual bool Evaluate(Context&);
virtual BooleanExp* Replace(const char*, BooleanExp&);
virtual BooleanExp* Copy() const;
private:
char* _name;
};
Конструктор класса получает в аргументе имя переменной:
VariableExp::VariableExp (const char* name) {
_name = strdup(name);
}
Вычисление переменной возвращает ее значение в текущем контексте:
bool VariableExp::Evaluate (Context& aContext) {
return aContext.Lookup(_name);
}
Копирование переменной возвращает новый объект класса
VariableExp
:
BooleanExp* VariableExp::Copy () const {
return new VariableExp(_name);
}
Чтобы заменить переменную выражением, мы сначала проверяем, что имя переменной совпадает с именем, переданным в аргументе:
BooleanExp* VariableExp::Replace ( const char* name, BooleanExp& exp ) {
if (strcmp(name, _name) == 0) {
return exp.Copy();
Паттерн Interpreter (интерпретатор)
299
} else {
return new VariableExp(_name);
}
}
Класс
AndExp представляет выражение, получающееся в результате приме- нения операции логического И к двум булевым выражениям:
class AndExp : public BooleanExp {
public:
AndExp(BooleanExp*, BooleanExp*);
virtual AndExp();
virtual bool Evaluate(Context&);
virtual BooleanExp* Replace(const char*, BooleanExp&);
virtual BooleanExp* Copy() const;
private:
BooleanExp* _operand1;
BooleanExp* _operand2;
};
AndExp::AndExp (BooleanExp* op1, BooleanExp* op2) {
_operand1 = op1;
_operand2 = op2;
}
При решении
AndExp вычисляются его операнды и возвращается результат применения к ним операции логического И:
bool AndExp::Evaluate (Context& aContext) {
return _operand1->Evaluate(aContext) &&
_operand2->Evaluate(aContext);
}
В классе
AndExp операции
Copy и
Replace реализуются с помощью рекурсив- ных обращений к операндам:
BooleanExp* AndExp::Copy () const {
return new AndExp(_operand1->Copy(), _operand2->Copy());
}
BooleanExp* AndExp::Replace (const char* name, BooleanExp& exp) {
return new AndExp(
_operand1->Replace(name, exp),
_operand2->Replace(name, exp)
);
}
300
Глава 5. Паттерны поведения
Определим теперь булево выражение
(true and x) or (y and (not x))
и вычислим его для некоторых конкретных значений булевых перемен- ных x
и y
:
BooleanExp* expression;
Context context;
VariableExp* x = new VariableExp("X");
VariableExp* y = new VariableExp("Y");
expression = new OrExp( new AndExp(new Constant(true), x),
new AndExp(y, new NotExp(x))
);
context.Assign(x, false);
context.Assign(y, true);
bool result = expression->Evaluate(context);
С такими значениями x
и y
выражение равно true
. Чтобы вычислить его при других значениях переменных, достаточно просто изменить контекст.
Наконец, можно заменить переменную y
новым выражением и повторить вычисление:
VariableExp* z = new VariableExp("Z");
NotExp not_z(z);
BooleanExp* replacement = expression->Replace("Y", not_z);
context.Assign(z, true);
result = replacement->Evaluate(context);
Этот пример иллюстрирует важную особенность паттерна интерпретатор: многие разновидности операций могут «интерпретировать» последова- тельности. Из трех операций, определенных в классе
BooleanExp
,
Evaluate наиболее близка к нашему интуитивному представлению о том, что интер- претатор должен интерпретировать программу или выражение и возвращать простой результат.
Но и операцию
Replace можно считать интерпретатором. Его контекстом является имя заменяемой переменной и подставляемое вместо него выраже- ние, а результатом служит новое выражение. Даже операция
Copy может рас- сматриваться как интерпретатор с пустым контекстом. Трактовка операций
Replace и
Copy как интерпретаторов может показаться странной, поскольку
Паттерн Interpreter (интерпретатор)
301это всего лишь базовые операции над деревом. Примеры в описании пат- терна посетитель (379) демонстрируют, что все три операции разрешается вынести в отдельный объект-посетитель «интерпретатор», тогда аналогия станет более очевидной.
Паттерн интерпретатор — нечто большее, чем распределение некоторой опе- рации по иерархии классов, составленной с помощью паттерна компоновщик
(196). Мы рассматриваем операцию
Evaluate как интерпретатор, поскольку иерархию классов
BooleanExp мыслим себе как представление некоторого языка. Если бы у нас была аналогичная
иерархия для представления агре- гатов автомобиля, то вряд ли мы стали бы рассматривать такие операции, как
Weight
(вес) и
Copy
(копирование), как интерпретаторы, несмотря на то что они распределены по всей иерархии классов, — просто мы не восприни- маем части автомобиля как язык. Тут все дело в точке зрения: опубликуй мы грамматику автомобильных частей, то операции над ними можно было трактовать как способы интерпретации соответствующего языка.
Известные применения
Паттерн интерпретатор широко используется в компиляторах, реализованных с помощью объектно-ориентированных языков, например в компиляторах
Smalltalk. В языке SPECTalk этот паттерн применяется для интерпретации форматов входных файлов [Sza92]. В библиотеке QOCA он применяется для вычисления ограничений [HHMV92].
Если рассматривать данный паттерн в самом общем виде (то есть как операцию, распределенную по иерархии классов, основанной на паттерне компоновщик), то почти любое применение компоновщика содержит и интер- претатор. Но паттерн интерпретатор лучше применять в тех случаях, когда иерархию классов можно рассматривать как описание языка.
Родственные паттерны
Компоновщик (196): абстрактное синтаксическое дерево — пример приме- нения паттерна компоновщик.
Приспособленец (231) показывает варианты разделения терминальных сим- волов в абстрактном синтаксическом дереве.
Итератор (302): интерпретатор может пользоваться итератором для обхода структуры.
Посетитель (379) может использоваться для инкапсуляции в одном классе поведения каждого узла абстрактного синтаксического дерева.
302 Глава 5. Паттерны поведения
ПАТТЕРН ITERATOR (ИТЕРАТОР)
Название и классификация паттерна
Итератор — паттерн поведения объектов.
Назначение
Предоставляет способ последовательного обращения ко всем элементам составного объекта без раскрытия его внутреннего представления.
Другие названия
Cursor
(курсор).
Мотивация
Составной объект, скажем, список, должен предоставлять способ доступа к своим элементам, не раскрывая их внутреннюю структуру. Более того, иногда требуется обходить список по-разному в зависимости от решаемой задачи. Но вряд ли вы захотите засорять интерфейс класса
List операциями для различных вариантов обхода, даже если все их можно предусмотреть заранее. Кроме того,
иногда бывает нужно, чтобы в один и тот же момент действовало несколько активных обходов списка.
Все это позволяет сделать паттерн итератор. Основная его идея в том, чтобы за обращения к элементам и способ обхода отвечал не сам список, а отдель- ный объект-итератор. В классе
Iterator определен интерфейс для доступа к элементам списка. Объект этого класса отслеживает текущий элемент, то есть он располагает информацией, какие элементы уже посещались.
Например, для класса
List мог бы существовать класс
ListIterator
; отно- шения между этими классами могли бы выглядеть так:
Count()
Append(Element)
Remove(Element)
ListFirst()
Next()
IsDone()
CurrentItem()
index list
ListIteratorПрежде чем создавать экземпляр класса
ListIterator
, необходимо иметь список для обхода. С объектом
ListIterator вы можете последовательно
Паттерн Iterator (итератор)
303
посетить все элементы списка. Операция
CurrentItem возвращает текущий элемент списка,
First инициализирует текущий элемент первым элементом списка,
Next делает текущим следующий элемент, а
IsDone проверяет, не вышел ли обход за последний элемент, если вышел — то обход завершается.
Отделение механизма обхода от объекта
List позволяет определять ите- раторы, реализующие различные стратегии обхода, не перечисляя их в ин- терфейсе класса
List
. Например, итератор
FilteringListIterator мог бы предоставлять доступ только к тем элементам, которые удовлетворяют критериям фильтрации.
Следует заметить, что между итератором и списком существует тесная связь.
Клиент должен знать, что он обходит именно список, а не какую-то другую агрегированную структуру. По этой причине клиент привязан к конкретному способу агрегирования. Было бы лучше, если бы класс агрегата можно было изменять без изменения кода клиента. Для этого можно обобщить концеп- цию итератора и рассмотреть полиморфную итерацию.
Допустим, у вас есть еще класс
SkipList
, реализующий cписок с пропусками
(skiplist) [Pug90] — вероятностную структуру данных, которая по своим характеристикам напоминает сбалансированное дерево. Требуется иметь возможность писать код, способный работать с объектами как класса
List
, так и класса
SkipList
Определим класс
AbstractList
, в котором объявлен общий интерфейс для манипулирования списками. Еще нам понадобится абстрактный класс
Iterator
, определяющий общий интерфейс итерации. Затем мы смогли бы определить конкретные подклассы класса
Iterator для различных ре- ализаций списка. В результате механизм итерации перестает зависеть от конкретных агрегированных классов.
Client
List
SkipList
SkipListIterator
ListIterator
CreateIterator()
Count()
Append(Item)
Remove(Item)
...
AbstractList
First()
Next()
IsDone()
CurrentItem()
Iterator
304 Глава 5. Паттерны поведения
Остается понять, как создается итератор. Поскольку мы хотим написать код, не зависящий от конкретных подклассов
List
, то нельзя просто создать экземпляр конкретного класса. Вместо этого ответственность за создание подходящих объектов-списков будет возложена на сами объекты-списки; вот почему потребуется операция
CreateIterator
, посредством которой клиенты смогут запрашивать объект-итератор.
CreateIterator
— это пример использования паттерна фабричный метод
(135). В данном случае он служит для того, чтобы клиент мог запросить у объекта-списка подходящий итератор. Применение фабричного метода при- водит к появлению двух иерархий классов — одной для списков, другой для итераторов. Фабричный метод
CreateIterator связывает эти две иерархии.
Применимость
Основные условия для применения паттерна итератор:
обращение к содержимому агрегированных объектов без раскрытия их внутреннего представления;
поддержка нескольких активных обходов одного и того же агрегирован- ного объекта;
предоставление единообразного интерфейса для обхода различных агре- гированных структур (то есть для поддержки полиморфной итерации).
Структура
Скачать 6.37 Mb.