Как стать автором
Обновить

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

Время на прочтение 6 мин
Количество просмотров 6.1K
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

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

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн