Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Паттерн Interpreter

символы представляют выражения, содержащие операторы and, or и not. При­ведем определение грамматики:

BooleanExp::= VariableExp I Constant I OrExp I AndExp I NotExp I

' (' BooleanExp ') '

AndExp::= BooleanExp 'and' BooleanExp OrExp:: = BooleanExp ' or ' BooleanExp NotExp::= 'not' BooleanExp Constant::= 'true' I 'false¹ VariableExp::= 'A' I 'B' I... |.'X' | 'Y¹ I 'Z'

Определим две операции над булевыми выражениями. Первая - Evaluate -вычисляет выражение в контексте, где каждой переменной присваивается истин­ное или ложное значение. Вторая - Replace - порождает новое булево выраже­ние, заменяя выражением некоторую переменную. Эта операция демонстрирует, что паттерн интерпретатор можно использовать не только для вычисления вы­ражений; в данном случае он манипулирует самим выражением.

Здесь мы подробно опишем только классы BooleanExp, VariableExp и AndExp. Классы OrExp и NotExp аналогичны классу AndExp. Класс Constant представляет булевы константы.

В классе BooleanExp определен интерфейс всех классов, которые описыва­ют булевы выражения:

class BooleanExp { public:

BooleanExp ();

virtual -BooleanExp ();

virtual bool Evaluate (Contextk) = 0;

virtual BooleanExp* Replace (const char*, BooleanExp&) = 0;

virtual BooleanExp* Copy () const = 0;

Класс 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(Contexts);

virtual BooleanExp* Replace(const char*, BooleanExp&);

virtual BooleanExp* Copy() const; private:

char* _name; I.

Конструктор класса принимает в качестве аргумента имя переменной:

VariableExp::VariableExp (const char* name) { _name = strdup(name);

Вычисление переменной возвращает ее значение в текущем контексте:

bool VariableExp::Evaluate (Contexts aContext) { return aContext.Lookup(_name);

Копирование переменной возвращает новый объект класса VariableExp:

BooleanExp* VariableExp::Copy () const { return new VariableExp(_name);

Чтобы заменить переменную выражением, мы сначала проверяем, что у пере­менной то же имя, что было передано ранее в качестве аргумента:

BooleanExp* VariableExp::Replace (const char* name, BooleanExp& exp

if (strcmptname, _name) == 0) {

return exp.Copy(); } else {

return new VariableExp(_name);

Класс AndExp представляет выражение, получающееся в результате примене­ния операции логического И к двум булевым выражениям:

class AndExp: public BooleanExp { public:

AndExp(BooleanExp*, BooleanExp*);

virtual -AndExp();•

virtual bool Evaluate(Contexts);

virtual BooleanExp* Replace(const char*, BooleanExpS);

virtual BooleanExp* CopyO const; private:

BooleanExp* _operandl;

BooleanExp* _operand2; i.

Паттерн Interpreter

AndExp::AndExp (BooleanExp* opl, BooleanExp* op2) { _operandl = opl; _operand2 = op2; }

При решении AndExp вычисляются его операнды и результат применения к ним операции логического И возвращается:

bool AndExp::Evaluate (Context"⁴ aContext) { return

_operandl->Evaluate (aContext) && _operand2->Evaluate (aContext);

}

В классе AndExp операции Copy и Replace реализованы с помощью рекур­сивных обращений к операндам:

BooleanExp* AndExp:: Copy () const { return

new AndExp (_operandl->Copy (), _operand2->Copy ());

BooleanExp* AndExp::Replace (const char* name, BooleanExpk ep) { return

new AndExp(

_operandl->Replace(name, exp), _operand2->Replace(name, exp)

Определим теперь булево выражение (true and x) or (у and (not x)) и вычислим его для некоторых конкретных значений булевых переменных х и у:

BooleanExp* expression; Context context;

VariableExp* x = new VariableExp("X"); VariableExp* у = new VariableExp("Y");

expression = new OrExpt

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);

С такими значениями х и у выражение равно true. Чтобы вычислить его при других значениях переменных, достаточно просто изменить контекст.

Паттерны поведения

И наконец, мы можем заменить переменную у новым выражением и повто­рить вычисление:

VariableExp* z = new VariableExpf"Z");

NotExp not_z(z);

BooleanExp* replacement = expression->Replace("Y", not_z);

context.Assign(z, true);

result = replacement->Evaluate(context);

На этом примере проиллюстрирована важная особенность паттерна интер­претатор: «интерпретация» предложения может означать самые разные действия. Из трех операций, определенных в классе BooleanExp, Evaluate наиболее близ­ка к нашему интуитивному представлению о том, что интерпретатор должен ин­терпретировать программу или выражение и возвращать простой результат.

Но и операцию Replace можно считать интерпретатором. Его контекстом яв­ляется имя заменяемой переменной и подставляемое вместо него выражение, а ре­зультатом служит новое выражение. Даже операцию Сору допустимо рассматри­вать как интерпретатор с пустым контекстом. Трактовка операций Replace и Сору как интерпретаторов может показаться странной, поскольку это всего лишь базо­вые операции над деревом. Примеры в описании паттерна посетитель демон­стрируют, что все три операции разрешается вынести в отдельный объект-посети­тель «интерпретатор», тогда аналогия станет более очевидной.

Паттерн интерпретатор - это нечто большее, чем распределение некоторой операции по иерархии классов, составленной с помощью паттерна компоновщик. Мы рассматриваем операцию Evaluate как интерпретатор, поскольку иерархию классов BooleanExp мыслим себе как представление некоторого языка. Если бы у нас была аналогичная иерархия для представления агрегатов автомобиля, то вряд ли мы стали бы считать такие операции, как Weight (вес) и Сору (копирование), интерпретаторами, несмотря на то что они распределены по всей иерархии клас­сов, - просто мы не воспринимаем агрегаты автомобиля как язык. Тут все дело в точке зрения: опубликуй мы грамматику агрегатов автомобиля, операции над ними можно было трактовать как способы интерпретации соответствующего языка.

Известные применения

Паттерн интерпретатор широко используется в компиляторах, реализован­ных с помощью объектно-ориентированных языков, например в компиляторах Smalltalk. В языке SPECTalk этот паттерн применяется для интерпретации фор­матов входных файлов [Sza92]. В библиотеке QOCA для разрешения ограниче­ний он применяется для вычисления ограничений [HHMV92].

Если рассматривать данный паттерн в самом общем виде (то есть как опера­цию, распределенную по иерархии классов, основанной на паттерне компонов­щик), то почти любое применение компоновщика содержит и интерпретатор. Но применять паттерн интерпретатор лучше в тех случаях, когда иерархию клас­сов можно представлять себе как описание языка.

Родственные паттерны

Компоновщик: абстрактное синтаксическое дерево - это пример применения паттерна компоновщик.