|
© 2026
Александр Легалов
Содержание
Состояние (State)
Паттерн Состояние, по мнению авторов, позволяет объекту изменять свое поведение в зависимости от внутреннего состояния. Извне создается впечатление, что изменился класс объекта.
Графическое представление ОО структуры Состояния приведено на рисунке. Эта структура практически совпадает со структурой образца Стратегия. Основное отличие заключается в динамике, определяюющей подмену альтернатив. Если переключение между альтернативами в Стратегии (выбор алгоритма) обычно определяется клиентом, то переключение между состояними происходит из самих состояний, что определяет особенности функционирования конечных автоматов. Хотя эта разница в подмене вряд ли является существенной. Ничто не мешает менять состояния, исходя из внешних факторов или переходить в Стратегии от одного алгоритма к другому, минуя их централизованную замену. Да и говорить только о конечных автоматах не всегда имеет смысл, хотя в наибольшей степени концепция состояний и переходов воплощена именно в них.
Структура паттерна Состояние
Несмотря на то, что наиболее удобное, на мой взгляд, использование этого образца проявляется тогда, когда состояния являются достаточно громоздкими, содержат внутренние данные и имеют объемные вычисления, в качестве примера буду использовать простой распознаватель вложенности круглых скобок. Во-первых, он мною уже описан и реализован как совокупность иерархически порождаемых конечных автоматов. То есть, содержит состояния и переходы. Во-вторых имеются альтернативные реализации с применением более утилитарных технических приемов, которые можно сравнить с рассматриваемыми решениями, использующими динамический полиморфизм.
Для построения распознавателей существуют разнообразные подходы, опирающиеся как на "ручное" создание, так и на использование генераторов компиляторов. Выбор обычно субъективен и никогда для меня не являлся предметом дискуссий. Я использую "самопальную" версию на основе иерархически порождаемых конечных автоматов, описанных с использованием диаграмм Вирта. Поэтому в рамках примера использую когда-то построенный и реализованный такой автомат, состояния которого определяются жирными точками, а переходы задаются символами и нетерминалами.
Иерархически порождаемый конечный автомат, описанный диаграммами Вирта
Реализовать подобные автоматы можно различными путями. Например, используя switch-технологию программирования, предлагаемую А.А. Шалыто. В этом случае каждое состояние кодируется переменной, внутри цикла меняется в операторах присваивания, а автомат задается охватывающей их функцией. Однако в таких ситуациях я следую более прямым и путем, используя в качестве состояний метки. Переходы автомата в требуемые состояния непосредственно проверяют соответствие входного символа или вложенного правила, после чего, в случае истины, осуществляется переход с использованием ненавистного многоими оператора goto. В результате представленные на рисунке выше S и Z-автоматы будут выглядеть следующим образом.
// Функция, реализующая распознавание нетерминала S.
_Bool S() {
//_0: // Начало диаграммы
if(str[i] == '(') {
i++;
goto _1;
}
return 0; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
_1: // Точка 1 диаграммы
if(str[i] == ')') {
i++;
goto _3;
}
if(S()) {
goto _2;
}
erFlag++;
printf(
"Position %d, Error 1: I want closed bracket or next opened bracket!\n", i);
return 0;
_2: // Точка 2 диаграммы
if(str[i] == ')') {
i++;
goto _3;
}
erFlag++;
printf("Position %d, Error 2: I want closed bracket!\n", i);
return 0;
_3: // Точка 3 диаграммы
if(str[i] == '(') {
i++;
goto _1;
}
goto _end;
_end: // Точка end диаграммы
return 1;
}
// Функция, реализующая распознавание нетерминала Z.
_Bool Z() {
//_0: // Начало диаграммы
if(S()) goto _1;
return 0; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
_1: // Точка 1 диаграммы
// За последней скобкой должен быть "конец строки"
if(str[i] == '\n') {
goto _end; // Все прошло нормально
}
erFlag++;
printf("Position %d, Error 3: I want end of line!\n", i);
return 0;
_end:
return 1;
}
Несмотря на использование внешних переменных и прочего грязного кода я не хочу менять то, что повторно используется дальше во всех вариантах распознавателей этого элементарного примера. Эти функции выглядят следующим образом.
char str[256]; // Строка с входной цепочкой, имитирующая входную ленту
// string str; // Строка с входной цепочкой, имитирующая входную ленту
int i; // Текущее положение входной головки
int erFlag; // Флаг, фиксирующий наличие ошибок в середине правила
// Функция, реализующая чтение символов в буфер из входного потока.
// Используется для ввода с клавиатуры распознаваемой строки.
// Ввод осуществляется до нажатия на клавишу Enter.
// Символ '\n' является концевым маркером входной строки.
void GetOneLine(FILE *is, char* str) {
str[0] = '\0';
// ssize_t n = 256;
// ssize_t len = getline(&str, &n, is);
fgets(str, 256, stdin);
}
// Главная функция используется для тестирования до тех пор,
// пока не будет прочитана пустая строка
int main () {
char strCursor[256];
str[0] = '\0';
// Цикл распознавания различных входных цепочек
// do {
// while(str[0] != '\n') {
while(1) {
// Чтение очередной входной цепочки в буфер
printf("Input bracket\'s expression!: ");
// Формируем очередную строку скобок для распознавания.
GetOneLine(stdin, str);
if(str[0] == '\n') {
break;
}
// Здесь начинается разбор принятой строки.
if(Parser()) {
printf("+++++ OK! +++++\n");
} else {
printf("----- Fatal error (look upper error message)! -----\n");
}
// Вывод разобранной строки и значения позиции входой головки.
printf("Line: %s", str);
// strCursor = " Pos: " + string(i, '-');
// strCursor +='^';
// cout << strCursor << " i = " << i << "\n\n";
printf(" Pos: ");
for(int j = 0; j < i; ++j) {
printf("%c", '-');
}
printf("^ i = %d\n\n", i);
}
// } while(str[0] != '\n');
printf("Goodbye!\n");
return 0;
}
После этого безобразия пришло время насладиться динамически полиморфными примерами.
Объектно-ориентированная реализация Состояния
Не отходя от канонов, представленных у Гаммы и компании, сформируем абстрактный класс, определяющий метод, запускающий анализ состояния.
//------------------------------------------------------------------------------
// Класс, описывающий абстрактное состояние автомата
class State {
public:
// Переопределяемый метод проверки входных символов
virtual bool CalcState(State**) = 0;
};
Каждое из конкретных состояний любого автомата определяется конкретным классом и обеспечивает реализацию методов, осуществляющих переходы между состояниями. Для упрощения схемы зависимостей между объектами - состояниями и обработчиками состоями будем использовать простую схему из глобальных состояний - объектов. В более сложных ситуациях, когда конкретные состояния содержат свои внутренние данные, рекурсивные схемы могут привести к конфликтам. Поэтому потребуется более комплексное разрешение конфликтов. Однако в нашем случае одного набора состяний достаточно, так как нет тех данных, которые могут конфликтовать в рекурсивных вложенных вызовах. Это позволяет непосредственно менять объекты - состояния в обработчиках.
//==============================================================================
// Состояния, используемые в S-автомате
//==============================================================================
// Прототип функции автомата, реализующего распознавание нетерминала S.
bool S();
//------------------------------------------------------------------------------
//_0: // Начало S-диаграммы
class S0: public State {
// Проверка символа для первого состояния
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
// _1: // Точка 1 S-диаграммы
class S1: public State {
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
// _2: // Точка 2 S-диаграммы
class S2: public State {
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
// _3: // Точка 3 S-диаграммы
class S3: public State {
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
// Ложное состояние
class Sfalse: public State {
bool CalcState(State** state) override {
cout << "Sfalse: " << str[i] << "\n";
return false;
}
};
//------------------------------------------------------------------------------
// Истинное состояние
class Strue: public State {
bool CalcState(State** state) override {
return true;
}
};
//------------------------------------------------------------------------------
// Объекты, определяющие состояния S автомата
S0 s0;
S1 s1;
S2 s2;
S3 s3;
Sfalse sFalse;
Strue sTrue;
//------------------------------------------------------------------------------
// После этого можно описать реализации состояний для каждого класса
//------------------------------------------------------------------------------
// Проверка символа для первого состояния
bool S0::CalcState(State** state) {
if(str[i] == '(') {
i++;
*state = &s1;
return true;
}
*state = &sFalse;
return false; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
}
//------------------------------------------------------------------------------
bool S1::CalcState(State** state) {
if(str[i] == ')') {
i++;
*state = &s3;
return true;
}
if(S()) {
*state = &s2;
return true;
}
erFlag++;
cout << "Position " << i << ", "
<< "Error 1: I want closed bracket or next opened bracket!\n";
*state = &sFalse;
return false;
}
//------------------------------------------------------------------------------
bool S2::CalcState(State** state) {
if(str[i] == ')') {
i++;
*state = &s3;
return true;
}
erFlag++;
cout << "Position " << i << ", " << "Error 2: I want closed bracket!\n";
*state = &sFalse;
return false;
}
//------------------------------------------------------------------------------
bool S3::CalcState(State** state) {
if(str[i] == '(') {
i++;
*state = &s1;
return true;
}
*state = &sTrue;
return false;
}
Сам S-автомат запускается с некоторого начального состояния и находится в цикле, выход из которого достигается по достижении конечного состояния или состояния ошибки, которые завершаются выдачей булевского значения false.
//------------------------------------------------------------------------------
// Автомат, реализующий распознавание нетерминала S.
bool S() {
State* s = &s0; // начальное состояние S-автомата
while(s->CalcState(&s));
return s->CalcState(&s);
}
Аналогичная схем использована и для реализации Z-автомата.
//==============================================================================
// Состояния, используемые в Z-автомате
//==============================================================================
// Прототип функции автомата, реализующего распознавание нетерминала Z.
bool Z();
//------------------------------------------------------------------------------
//_0: // Начало Z-диаграммы
class Z0: public State {
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
//_1: // Точка 1 Z-диаграммы
class Z1: public State {
bool CalcState(State** state) override;
};
//------------------------------------------------------------------------------
// Ложное состояние
class Zfalse: public State {
bool CalcState(State** state) override {
cout << "Zfalse: " << str[i] << "\n";
return false;
}
};
//------------------------------------------------------------------------------
// Истинное состояние
class Ztrue: public State {
bool CalcState(State** state) override {
return true;
}
};
//------------------------------------------------------------------------------
// Объекты, определяющие состояния S автомата
Z0 z0;
Z1 z1;
Zfalse zFalse;
Ztrue zTrue;
//------------------------------------------------------------------------------
// После этого можно описать реализации состояний для каждого класса
//------------------------------------------------------------------------------
bool Z0::CalcState(State** state) {
if(S()) {
*state = &z1;
return true;
}
*state = &zFalse;
return false; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
}
//------------------------------------------------------------------------------
bool Z1::CalcState(State** state) {
// За последней скобкой должен быть "конец строки"
if(str[i] == '\n') {
*state = &zTrue;
return false; // Для выхода из цикла разбора
}
erFlag++;
cout << "Position " << i << ", " << "Error 3: I want end of line!\n";
*state = &zFalse;
return false;
}
//------------------------------------------------------------------------------
// Автомат, реализующий распознавание нетерминала Z.
bool Z() {
State* z = &z0; // начальное состояние Z-автомата
while(z->CalcState(&z));
return z->CalcState(&z);
}
Обертка из функций, поддерживающих чтение символов, обработку ошибок и взаимодействие с пользователем, аналогична той, что реализована и в программах на языке C, отличаясь только использованием библиотек C++
using namespace std;
string str; // Строка с входной цепочкой, имитирующая входную ленту
int i; // Текущее положение входной головки
int erFlag; // Флаг, фиксирующий наличие ошибок в середине правила
// Функция, реализующая чтение символов в буфер из входного потока.
// Используется для ввода с клавиатуры распознаваемой строки.
// Ввод осуществляется до нажатия на клавишу Enter.
// Символ '\n' является концевым маркером входной строки.
void GetOneLine(istream &is, string &str) {
char ch;
str = "";
for(;;) {
is.get(ch);
if(is.fail() || ch == '\n') break;
str += ch;
}
str += '\n'; // Добавляется концевой маркер
}
//------------------------------------------------------------------------------
// Функция запускающая разбор и определяющая корректность его завершения,
// если первый символ не принадлежит цепочки
bool Parser() {
// Начальная инициализация.
erFlag = 0;
i = 0;
// Процесс пошел!
if(Z())
{
return true; // Все прошло нормально
}
else {
if(erFlag)
cout << "Position " << i << ", "
<< "Error 4: Internal Error!\n";
else
cout << "Position " << i << ", "
<< "Error 5: Incorrect first symbol of S!\n";
return false; // Есть ошибки
}
}
//------------------------------------------------------------------------------
// Главная функция используется для тестирования до тех пор,
// пока не будет прочитана пустая строка
int main () {
string strCursor;
str = "";
// Цикл распознавания различных входных цепочек
do {
// Чтение очередной входной цепочки в буфер
cout << "Input bracket\'s expression!: ";
// Формируем очередную строку скобок для распознавания.
GetOneLine(cin, str);
cout << str;
// Здесь начинается разбор принятой строки.
if(Parser())
cout << "+++++ OK! +++++\n";
else
cout << "----- Fatal error (look upper error message)! -----\n";
// Вывод разобранной строки и значения позиции входой головки.
cout << "Line: " << str;
strCursor = " Pos: " + string(i, '-');
strCursor +='^';
cout << strCursor << " i = " << i << "\n\n";
} while(str != "\n");
cout << "Goodbye!\n";
return 0;
}
Подвводя промежуточные итоги можно отметить, что использование ОО версии образца неплохо сочетается с рассмотренной "Бандой четырех" предметной областью, в которой и количество состояний невелико, и отсутствуют (как в моем примере) сложные иерархические зависимости между состояниями. То, что получилось выше, выглядит достаточно монструозно.
Процедурно-параметрические отношения в Состоянии
Аналогия со Стратегией в целом должна демонстрировать и близость схемы альтернатив, определяющих отношения в Состоянии. В данной ситуации демонстрируется, что все состояния вызываются из автомата, который запускается с некоторого начального состояния. После чего внутри его осуществляются переходы в соответствии с правилами, определяющими распознавание. Это может быть как goto, так и другие решения, включая процедурно-параметрическое.
Процедурное представление аналога Состояния
Автомат, как и в ОО программе запускает некоторое начальное состояние, после чего переходит в аналогичный цикл, используя процедурно-параметрический полиморфизм вместо объектно-ориентированного.
Процедурно-параметрическая имитация Состояния
В процедурно-параметрической версии состояния могут быть представлены как эволюционно расширяемые перечислимые типы. В связи с тем, что такие типы имеют одинаковый размер, то для их хранения достаточно использовать общую переменную. Замена одного типа на другой обеспечивается только изменением признака переменной. Исходя из того, что передача параметров в обработчики специализаций осушествляется по ссылке, никаких глобальных переменных для фиксации разных состояний не требуется. Каждый из автоматов, являясь функцией, хранит свое состояние в локальной переменной. Исходя из этого, S-автомат, его состояния и обработчики состояний будут выглядеть следующим образом.
//==============================================================================
// Описание автомата S, распознающего вложенность скобок
//==============================================================================
//------------------------------------------------------------------------------
// Обобщение, определяющее состояния автомата S
typedef struct StateS{}<S1, S2, S3, True, False: void;>StateS;
//------------------------------------------------------------------------------
// Обобщенная функция и обработчики, реализующие состояния автомата S
// Обобщенная функция реализует начальное состояние
_Bool CalcStateS<StateS* state>() {
//_0: // Начало диаграммы
if(str[i] == '(') {
i++;
init_spec(StateS.S1, state);
return 1;
}
init_spec(StateS.False, state);
return 0; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
};
_Bool CalcStateS<StateS.S1* state>() {
// _1: // Точка 1 диаграммы
if(str[i] == ')') {
i++;
init_spec(StateS.S3, state);
return 1;
}
if(S()) {
init_spec(StateS.S2, state);
return 1;
}
erFlag++;
printf(
"Position %d, Error 1: I want closed bracket or next opened bracket!\n", i);
init_spec(StateS.False, state);
return 0;
}
_Bool CalcStateS<StateS.S2* state>() {
// _2: // Точка 2 диаграммы
if(str[i] == ')') {
i++;
init_spec(StateS.S3, state);
return 1;
}
erFlag++;
printf("Position %d, Error 2: I want to close bracket!\n", i);
init_spec(StateS.False, state);
return 0;
}
_Bool CalcStateS<StateS.S3* state>() {
// _3: // Точка 3 диаграммы
if(str[i] == '(') {
i++;
init_spec(StateS.S1, state);
return 1;
}
init_spec(StateS.True, state);
return 0;
}
_Bool CalcStateS<StateS.False* state>() {
return 0;
}
_Bool CalcStateS<StateS.True* state>() {
return 1;
}
//------------------------------------------------------------------------------
// Автомат, реализующий распознавание нетерминала S.
_Bool S() {
struct StateS state;
while(CalcStateS<&state>());
return CalcStateS<&state>();
}
Смена состояния автомата осуществляется специальной функцией init_spec, изменяющей признак специализации, что позволяет имитировать оператор присваивания, изменеющий одно значение эволюционно расширяемого перечислимого типа на другое. Начальное значение S-автомата определяется переменной, являющейся обобщением, которое в цикле подменяется на значения различных специализаций.
Реализация Z-автомата строится по аналогичной схеме. Поэтому вряд ли требует дополнительных комментариев.
//==============================================================================
// Описание автомата Z, запускающий распознаватель
//==============================================================================
//------------------------------------------------------------------------------
// Обобщение, определяющее состояния автомата Z
typedef struct StateZ{}<S1, True, False: void;>StateZ;
//------------------------------------------------------------------------------
// Обобщенная функция и обработчики, реализующие состояния автомата Z
_Bool CalcStateZ<StateZ* state>() {
//_0: // Начало диаграммы
if(S()) {
init_spec(StateZ.S1, state);
return 1;
}
init_spec(StateZ.False, state);
return 0; // Первый символ цепочки некорректен
// что это ошибка, лучше определить снаружи
};
_Bool CalcStateZ<StateZ.S1* state>() {
// _1: // Точка 1 диаграммы
// За последней скобкой должен быть "конец строки"
if(str[i] == '\n') {
init_spec(StateZ.True, state);
return 0;
}
erFlag++;
printf("Position %d, Error 3: I want end of line!\n", i);
init_spec(StateZ.False, state);
return 0;
}
_Bool CalcStateZ<StateZ.False* state>() {
return 0;
}
_Bool CalcStateZ<StateZ.True* state>() {
return 1;
}
//------------------------------------------------------------------------------
// Автомат, реализующий распознавание нетерминала Z.
_Bool Z() {
struct StateZ state;
while(CalcStateZ<&state>());
return CalcStateZ<&state>();
}
Все остальная обертка аналогична той, что используется в ранее описанной процедурной программе.
Следует также отметить, что вместо имитации эволюционно-расширяемого перечислимого типа состояния могут быть реализованы как более сложные специализации, содержащие дополнительные данные. В этом случае, как и в случае ОО программ, внутри функций, определяющих автоматы, необходимо будет осуществлять локализацию состояний или передавать их извне с использованием дополнительных аргументов. Однако в целом вряд ли подобные решения будут сложнее, чем при ОО подходе.
Подводя итоги можно отметить, что в ПП реализации этого ОО паттерна ничего интересного не обнаружено. Состояние - достаточно банальный образец, имеющий очевидное решение для предлагаемых применений. Тем более, что для реализации автоматов с множеством числом состояний существуют и другие не менее интересные варианты. Например когда-то для Оберона, а сейчас и для Go предлагается в качестве состояний использовать функции. Но для своих решений, однако, я бы по старинке предпочел goto ;)
Содержание
|