Введение
В моей практике часто возникали ситуации, когда применение конечного автомата являлось наиболее верным решением, однако от него приходилось отказываться ввиду срочности разработки, сложности поддержки, или же по каким-либо иным причинам. В этом посте мне хотелось бы поделиться с вами разработанным мною решением, позволяющим без труда встраивать в свои проекты конечные автоматы с возможностью наглядного отображения структуры дерева.
Суть решения
Сразу оговорюсь: данное решение предназначено для интеграции в проекты, разработанные на C++. Поддержка других языков на данный момент отсутствует (если будут надобность, их поддержка будет добавлена в будущем).
Решение представляет из себя связку из двух этапов:
- В PlantUML файле создается дерево проекта, написанное в едином стиле, после чего вызывается программа-генератор, порождающая C++ файл, содержащий в себе дерево связей между вершинами графа. Правила описания дерева имеются в описании проекта на github-е. Для сборки понадобится наличие библиотеки QT 5.10 и выше.
- В требуемый класс добавляется поддержка конечного автомата.
- В классе, к которому необходимо добавить поддержку конечного автомата, создается объект шаблонного класса fsm_class. В качестве параметра шаблона передается ранее упомянутый класс.
- Так же в класс добавляются static методы, реализующие шаги конечного автомата.
- В определенном методе класса вызывается функция связывания дерева конечного автомата с его ядром, после чего вызывается метод, запускающий проход по графу.
Постановка задачи
Рассмотрим использование этого решения на примере распознавания входного сообщения, принятого откуда-то из вне.
Параметры сообщения следующие:
- Сообщение приходит в виде массива символов неопределенной длины, но не больше 512 символов (включая 0-терминатор).
- Сообщение заканчивается 0-терминатором.
Достоверно известно, что сообщение состоит из последовательности строк: «команда» + «параметры», разделенной символом пробела. Строка «команда» может принимать значения «read» или «set», а «параметры» требуется только если введена команда «set». В этом случае ожидается значение для int-переменной.
Решение задачи
- Создадим пустой каталог и добавим туда субмодули ядра fsm и программы-генератора.
git submodule add git@github.com:Vadimatorik/module_fsm.git git submodule add git@github.com:Vadimatorik/plantuml_to_fsm_tree_generator.git - Создадим папку user_code и в ней файлы user_string_parsing.cpp и user_string_parsing.h, которые будут содержать описание класса, занимающегося анализом входящего сообщения.
- Напишем заготовку нашего класса.
class user_string_parsing_class { public: user_string_parsing_class(); void start_parsing ( char* string ); private: /// Указатель на текущий символ строки. char* p = nullptr; /// Данные, которые мы будем считывать и записывать. int data = 0; /// Конечный автомат. fsm_class< user_string_parsing_class > fsm; }; - Создадим в папке user_code файл tree.pu, который будет содержать описание дерева нашего конечного автомата
- Опишем наш конечный автомат:
@startuml[*] --> start
state "team_search" as start {
start: Ищем во входной строке
start: поддерживаемую команду.
}start --> fts: 0
start --> arg1: 1
start --> arg2: 2state "team_search_fail" as fts {
fts: Поддерживаемой команды
fts: найдено не было.
fts: Выводим список поддерживаемых
fts: команд.
}state "set_param" as arg1 {
arg1: Проверяем входной параметр.
}state "read_param" as arg2 {
arg2: Выводим требуемый параметр.
}arg1 --> spd: 0
arg1 --> spn: 1state "set_param_done" as spd {
spd: Выводим сообщение о том,
spd: что параметр был принят верно.
}state "set_param_fail" as spn {
spn: Выводим сообщение о том,
spn: что параметр не был принят.
}@enduml
Дерево имеет следующий вид:
- Добавим в наш класс static-методы, являющиеся вершинами графа. Для более короткой записи объявим их через define. Наш файл user_string_parsing.h примет вид:
#pragma once #include "fsm.h" #define HANDLER_USPC_FSM_STEP(NAME_STEP) static int NAME_STEP ( const fsm_step< user_string_parsing_class >* previous_step, user_string_parsing_class* obj ) class user_string_parsing_class { public: user_string_parsing_class(); void start_parsing ( char* string ); HANDLER_USPC_FSM_STEP( fsm_step_func_team_search ); HANDLER_USPC_FSM_STEP( fsm_step_func_team_search_fail ); HANDLER_USPC_FSM_STEP( fsm_step_func_set_param ); HANDLER_USPC_FSM_STEP( fsm_step_func_read_param ); HANDLER_USPC_FSM_STEP( fsm_step_func_set_param_done ); HANDLER_USPC_FSM_STEP( fsm_step_func_set_param_fail ); private: /// Указатель на текущий символ строки. char* p = nullptr; /// Данные, которые мы будем считывать и записывать. int data = 0; /// Конечный автомат. fsm_class< user_string_parsing_class > fsm; }; - Реализуем методы класса.
/// Имя вершины формируется как: /// имя классе + имя старового метода + _fsm_step /// user_string_parsing_class_ + team_search + _fsm_step extern const fsm_step< user_string_parsing_class > user_string_parsing_class_team_search_fsm_step; user_string_parsing_class::user_string_parsing_class() { /// Производим связывание машины состояния с начальным шагом и объектом. this->fsm.relinking( &user_string_parsing_class_team_search_fsm_step, this ); } void user_string_parsing_class::start_parsing ( char* string ) { /// Сохраняем указатель на сообщение, которое будем проверять. this->p = string; /// Запускаем анализ сообщения. this->fsm.start(); } - Реализуем вершины графа:
#define FSM_F_USPC const fsm_step< user_string_parsing_class >* previous_step, user_string_parsing_class* obj int user_string_parsing_class::fsm_step_func_team_search ( FSM_F_USPC ) { ( void )previous_step; if ( strncmp( obj->p, "set", sizeof( "set" ) - 1 ) == 0 ) { obj->p += sizeof( "set" ); return 1; } if ( strcmp( obj->p, "read" ) == 0 ) { return 2; } return 0; } int user_string_parsing_class::fsm_step_func_team_search_fail ( FSM_F_USPC ) { ( void )previous_step; ( void )obj; cout << "Command search fail! Available commands: set, read." << endl << endl; return 0; } int user_string_parsing_class::fsm_step_func_set_param ( FSM_F_USPC ) { ( void )previous_step; int r; r = sscanf( obj->p, "%d", &obj->data ); return ( r == 1 ) ? 0 : 1; } int user_string_parsing_class::fsm_step_func_read_param ( FSM_F_USPC ) { ( void )previous_step; cout << "Data = " << obj->data << endl; return 0; } int user_string_parsing_class::fsm_step_func_set_param_done ( FSM_F_USPC ) { ( void )previous_step; ( void )obj; cout << "The parameter done set!" << endl << endl; return 0; } int user_string_parsing_class::fsm_step_func_set_param_fail ( FSM_F_USPC ) { ( void )previous_step; ( void )obj; cout << "The parameter must be int!" << endl << endl; return 0; } - Создадим объект нашего класса в основной программе (файле main.cpp) и пропустим через несколько тестов:
#include <fstream> #include <stdint.h> #include <string.h> #include "user_string_parsing.h" using namespace std; /// Наше входящее сообщение будет находиться тут. char buf[512]; /// Метод эмитирует приход нового сообщения. void get_data ( char* b, int n ) { switch( n ) { case 0: memcpy( b, "fsdfhsd", sizeof("fsdfhsd") ); break; case 1: memcpy( b, "read", sizeof("read") ); break; case 2: memcpy( b, "set", sizeof("set") ); break; case 3: memcpy( b, "set sfdf", sizeof("set sfdf") ); break; case 4: memcpy( b, "set 21", sizeof("set 21") ); break; case 5: memcpy( b, "read", sizeof("read") ); break; } } int main ( void ) { user_string_parsing_class usp; for ( int l = 0; l < 6; l++ ) { get_data( buf, l ); usp.start_parsing( buf ); } return 0; } - Напишем makefile, который будет иметь раздельные цели сборки программы-генератора деревьев, а так же нашей программы с использованием ранее скомпилированного генератор.
CPP := g++ CPP_FLAGS := -O0 -g3 -Werror -Wall -Wextra -std=c++1z LDFLAGS := -O0 -g3 -Werror -Wall -Wextra PU = plantuml_to_fsm_tree_generator/build/plantuml_to_fsm_tree_generator # Собираем все необходимые данные из папки user_code. USER_CPP_FILE := $(shell find user_code/ -maxdepth 5 -type f -name "*.cpp" ) USER_DIR := $(shell find user_code/ -maxdepth 5 -type d -name "*" ) USER_PATH := $(addprefix -I, $(USER_DIR)) USER_OBJ_FILE := $(addprefix build/obj/, $(USER_CPP_FILE)) USER_OBJ_FILE := $(patsubst %.cpp, %.o, $(USER_OBJ_FILE)) PROJECT_PATH += $(USER_PATH) PROJECT_OBJ_FILE += $(USER_OBJ_FILE) FSM_PU_FILE = $(shell find user_code/ -maxdepth 5 -type f -name "*.pu" ) FSM_CPP_FILE += $(patsubst %.pu, %.cpp, $(FSM_PU_FILE)) FSM_OBJ_FILE += $(patsubst %.pu, build/obj/%.o, $(FSM_PU_FILE)) PROJECT_OBJ_FILE += $(FSM_OBJ_FILE) include module_fsm/makefile %.cpp: %.pu @echo [PU] $< @$(PU) $< $@ user_string_parsing_class user_string_parsing.h build/obj/%.o: %.cpp @echo [CPP] $< @mkdir -p $(dir $@) @$(CPP) $(CPP_FLAGS) $(PROJECT_PATH) -c $< -o $@ all: $(PROJECT_OBJ_FILE) @$(CPP) $(PROJECT_OBJ_FILE) -o build/example @size --format=Berkeley build/example clean: @rm -R build/ @echo Clean all! pfsm_build: mkdir -p plantuml_to_fsm_tree_generator/build cd plantuml_to_fsm_tree_generator/build && qmake -qt=qt5 .. && make pfsm_clean: cd plantuml_to_fsm_tree_generator/ && rm -R build pfsm_rebuild: cd plantuml_to_fsm_tree_generator/ && rm -R build mkdir plantuml_to_fsm_tree_generator/build cd plantuml_to_fsm_tree_generator/build && qmake -qt=qt5 .. && make - Скомпилируем наш проект. Сначала программу-генератор, а затем и проект.
make pfsm_build make all
Описанный в статье пример можно загрузить и попробовать собрать отсюда.
Обо всех неточностях, опечатках, ошибках, пожеланиях просьба писать в личных сообщениях.
Автор: Вадим
