РЕАЛИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ (FINITE STATE MACHINE) НА ЯЗЫКЕ ПРОГРАММИРОВАНИЕ С ПРИ ПОМОЩИ МАКРОСОВ

АННОТАЦИЯ

Цель работы – описать способ реализации конечных автоматов (Finite State Machine) [1] на языке программирования С в среде ОС Linux [2]. Реализация базируется на использовании трёх макросов, которые являются обёрткой над объявлением структур определённого типа. Данные структуры и представляют собой всё необходимое для описания состояний машин и списка команд для обработки, макросы же позволяют представить реализацию в простой для понимания форме и упростить процесс расширения уже написанного кода.

Реализация конечных автоматов необходима для разработки и исследования технологии функционирования объектов пассивной оптической сети [3].

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

Ключевые слова: конечные автоматы, Finite State Machine, макрос, структура, программная реализация

При реализации конечного автомата (Finite State Machine) с помощью языка программирования С необходимо обеспечить выполнение следующих требований:

• Простая реализация: код должен быть понятен другому программисту без излишних комментариев;
• Динамически расширяемая реализация: процесс добавления нового состояния или перехода в существующее состояние должен выполняться быстро и не занимать много времени.

Чтобы соответствовать этим требованиям, можно воспользоваться таким средством языка С, как макросы. Макрос позволяет скрыть сложную программную реализацию за простой дружелюбной конструкцией, которая не вызывает сложностей при анализе и сразу показывает суть кода.

Прежде чем перейти к макросам, необходимо определить структуры, которые будут спрятаны за ними.

Основной структурой является Machine_state, объявление которой имеет следующий вид:

typedef struct Machine_state

{

    char const *name;

    struct Machine_state_handler handlers[MAX_HANDLERS_COUNT];

} Machine_state;

Листинг 1. Объявление структуры Machine_state

Данная структура используется для описания всех возможных состояний, в котором может находиться машина. Структура имеет два поля:

• name – имя состояния, используется для вывода сообщений в консоль, чтобы отслеживать текущее состояние объекта;
• handlers – массив обработчиков состояния (размер задаётся по необходимости).

Остановимся подробнее на последнем поле. Данный массив определяет набор обработчиков, которые будут вызваны при получении определённой команды. На каждую команду задаётся один обработчик, чтобы гарантировать уникальность действия. Сама структура Machine_state_handler имеет следующее объявление:

typedef struct Machine_state_handler

{

    enum Commands command;

    Handler_callback callback;

    struct Machine_state const *next_state;

} Machine_state_handler;

Листинг 2. Объявление структуры Machine_state_handler

Всю суть структуры описывают её поля:

• command – номер команды, по которому будет вызван данный обработчик. Тип этого поля может быть произвольным, зависит от специфики реализации;
• callback – функция, которая будет вызвана при работе с этим обработчиком. Именно в этой функции описывается основная логика работы над машиной (тип поля также зависит от реализации);
• next_state – состояние, в которое перейдёт машина в конце работы обработчика. С помощью этого поля и строится схема переходов объекта между состояниями (в случае, если переход не требуется, то в качестве значения поля можно указать текущее состояние машины).

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

#define STATE_DECLARE(__STATE_NAME__) \

    extern struct Machine_node STATE_ ## __STATE_NAME__

#define STATE(__STATE_NAME__, ...) \

    struct Machine_node STATE_ ## __STATE_NAME__ = \

{#__STATE_NAME__, __VA_ARGS__}

#define STATE_HANDLER(__CMD__, __CALLBACK__, __NEXT_STATE_NAME__) \

    {__CMD__, __CALLBACK__, &STATE_ ## __NEXT_STATE_NAME__}

Листинг 3. Объявление макросов для описания состояния машин

• STATE_DECLARE – определение состояния. Данный макрос можно использовать для определения состояния в коде до его объявления, чтобы при описании других состояний можно было использовать текущее (аналогично прототипу static-функции, объявление которой расположено в начале файла, а определение – в середине или в конце);
• STATE – объявление состояния, хранит всю необходимую информацию: название, список команд, которые можно обработать, и так далее;
• STATE_HANDLER – описание обработчика команды. "Какая функция будет вызвана при получении команды? И в какое состояние перейдёт объект после выполнения данного обработчика?": на эти вопросы отвечает этот макрос. Стоит отметить, что данный макрос есть смысл использовать только внутри макроса STATE.

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

STATE_DECLARE(OBJECT_FAIL)

STATE_DECLARE(OBJECT_INIT)

STATE(OBJECT_FAIL,

{

   STATE_HANDLER(COMMAND_INGRESS, object_fail_ingress, OBJECT_FAIL),

   STATE_HANDLER(COMMAND_RECONFIG, object_fail_reconf, OBJECT_FAIL),

     });

STATE(OBJECT_INIT,

{

   STATE_HANDLER(COMMAND_INGRESS, object_init_ingress, OBJECT_INIT),

   STATE_HANDLER(COMMAND_FAIL, object_init_fail, OBJECT_FAIL),

   STATE_HANDLER(COMMAND_OK, object_init_ok, OBJECT_OK),

});

Листинг 4. Пример использования макросов для описания состояний

Первые две строки определяют два состояния - OBJECT_FAIL и OBJECT_INIT. Дальнейший код описывает эти состояния: в случае, если объект находится в состоянии OBJECT_INIT, он может обработать команды INGRESS, FAIL и OK. При получении команды INGRESS вызовется функция object_init_ingress, и состояние объекта останется прежним. При получении команды FAIL вызовется функция object_init_fail, и состояние объекта сменится на OBJECT_FAIL, и так далее. В процессе реализации можно дополнять существующие состояния и добавлять новые, связывая их с текущими.

Список литературы:

1. Детерминированные и недетерминированные конечные автоматы [Электронный ресурс]. / статья о различных видах конечных автоматов и их реализации на языке Delphi. URL: https://www.delphiplus.org/fundamentalnie-algoritmy-i-struktury-dannih/ispolzovanie-konechnogo-avtomata-sintaksicheskii-analiz.html (дата обращения: 15.04.2021).
2. UNIX. Профессиональное программирование, 3-е издание. / Стивенс Р., Раго С. – Пер. с англ. – СПб.: Символ-Плюс, 2014. – 1104 с., ил.
3. «Научное сообщество студентов XXI столетия. Технические науки»: Электронный сборник статей по материалам XCVIII студенческой международной научно-практической конференции. – Новосибирск: Изд. ООО «СибАК». – 2021. – No2 (97) / [Электронный ресурс]. URL: https://sibac.info/archive/technic/2(97).pdf