Хабрахабр

Легковесное ядро конечного автомата с автогенератором дерева для embedded проектов

image

Введение

В моей практике часто возникали ситуации, когда применение конечного автомата являлось наиболее верным решением, однако от него приходилось отказываться ввиду срочности разработки, сложности поддержки, или же по каким-либо иным причинам. В этом посте мне хотелось бы поделиться с вами разработанным мною решением, позволяющим без труда встраивать в свои проекты конечные автоматы с возможностью наглядного отображения структуры дерева.

Суть решения

Сразу оговорюсь: данное решение предназначено для интеграции в проекты, разработанные на C++. Поддержка других языков на данный момент отсутствует (если будут надобность, их поддержка будет добавлена в будущем).
Решение представляет из себя связку из двух этапов:

  1. В PlantUML файле создается дерево проекта, написанное в едином стиле, после чего вызывается программа-генератор, порождающая C++ файл, содержащий в себе дерево связей между вершинами графа. Правила описания дерева имеются в описании проекта на github-е. Для сборки понадобится наличие библиотеки QT 5.10 и выше.
  2. В требуемый класс добавляется поддержка конечного автомата.
    • В классе, к которому необходимо добавить поддержку конечного автомата, создается объект шаблонного класса fsm_class. В качестве параметра шаблона передается ранее упомянутый класс.
    • Так же в класс добавляются static методы, реализующие шаги конечного автомата.
    • В определенном методе класса вызывается функция связывания дерева конечного автомата с его ядром, после чего вызывается метод, запускающий проход по графу.

Постановка задачи

Рассмотрим использование этого решения на примере распознавания входного сообщения, принятого откуда-то из вне.
Параметры сообщения следующие:

  1. Сообщение приходит в виде массива символов неопределенной длины, но не больше 512 символов (включая 0-терминатор).
  2. Сообщение заканчивается 0-терминатором.

Достоверно известно, что сообщение состоит из последовательности строк: «команда» + «параметры», разделенной символом пробела. Строка «команда» может принимать значения «read» или «set», а «параметры» требуется только если введена команда «set». В этом случае ожидается значение для int-переменной.

Решение задачи

  1. Создадим пустой каталог и добавим туда субмодули ядра fsm и программы-генератора.
    git submodule add git@github.com:Vadimatorik/module_fsm.git
    git submodule add git@github.com:Vadimatorik/plantuml_to_fsm_tree_generator.git
    
  2. Создадим папку user_code и в ней файлы user_string_parsing.cpp и user_string_parsing.h, которые будут содержать описание класса, занимающегося анализом входящего сообщения.
  3. Напишем заготовку нашего класса.
    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;
    };
    
  4. Создадим в папке user_code файл tree.pu, который будет содержать описание дерева нашего конечного автомата
  5. Опишем наш конечный автомат:
    @startuml

    [*] --> start

    state "team_search" as start {
    start: Ищем во входной строке
    start: поддерживаемую команду.
    }

    start --> fts: 0
    start --> arg1: 1
    start --> arg2: 2

    state "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: 1

    state "set_param_done" as spd {
    spd: Выводим сообщение о том,
    spd: что параметр был принят верно.
    }

    state "set_param_fail" as spn {
    spn: Выводим сообщение о том,
    spn: что параметр не был принят.
    }

    @enduml


    Дерево имеет следующий вид:image

  6. Добавим в наш класс 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;
    };
    
  7. Реализуем методы класса.
    /// Имя вершины формируется как:
    /// имя классе + имя старового метода + _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();
    }
    
  8. Реализуем вершины графа:
    #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;
    }
    
  9. Создадим объект нашего класса в основной программе (файле 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;
    }
    
  10. Напишем 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
    
    
  11. Скомпилируем наш проект. Сначала программу-генератор, а затем и проект.
    make pfsm_build
    make all
    

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

Теги
Показать больше

Похожие статьи

Кнопка «Наверх»
Закрыть