C дизайн конечного автомата

Эта серия сообщений Ars OpenForum о несколько сложной логике управления включает в себя очень простую реализацию в виде конечного автомата на C.

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

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

Я бы использовал его, когда конечный автомат достаточно прост, чтобы подход с указателем функции и таблицей переходов состояний был излишним. Это часто бывает полезно при посимвольном или пословном синтаксическом анализе.

Ваш вопрос довольно общий,
Вот две справочные статьи, которые могут быть полезны:

1. Реализация встроенного конечного автомата

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

   • Кодирование конечных автоматов на C и C ++

     ] Моя озабоченность в этой статье связана с основами конечных автоматов и некоторыми простыми рекомендациями по программированию для кодирования конечных автоматов на C или C ++. Я надеюсь, что эти простые методы станут более распространенными, так что вы (и другие) сможете легко увидеть структуру конечного автомата прямо из исходного кода.

Где-то это видел

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0)
      NEXTSTATE(y);
    else
      NEXTSTATE(x);
  }
}

Чрезвычайно непроверено, но интересно кодировать, теперь в более усовершенствованной версии, чем мой исходный ответ; последние версии можно найти на mercurial.intuxication.org :

sm.h

#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
    "use '#define SM_ARGS (void)' to get an empty argument list"
#endif

#ifndef SM_STATES
#error "SM_STATES undefined: " \
    "you must provide a list of comma-separated states"
#endif

typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;

#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)

#define sm_def(NAME) \
    static sm_state NAME ## _fn SM_ARGS; \
    static const sm_state NAME = (sm_state)NAME ## _fn; \
    static sm_state NAME ## _fn SM_ARGS

example.c

#include <stdio.h>

#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"

sm_def(EVEN)
{
    printf("even %i\n", i);
    return ODD;
}

sm_def(ODD)
{
    printf("odd  %i\n", i);
    return EVEN;
}

int main(void)
{
    int i = 0;
    sm_state state = EVEN;

    for(; i < 10; ++i)
        state = sm_transit(state)(i);

    return 0;
}

Обязательно ознакомьтесь с работой Миро Самека (блог State Space , веб-сайт State Machines & Tools ), статьи которого на Журнал пользователей C / C ++ был великолепен.

Веб-сайт содержит полную (C / C ++) реализацию как с открытым исходным кодом, так и с коммерческой лицензией структуры конечного автомата (QP Framework) , обработчик событий (QEP) , базовый инструмент моделирования (QM) и инструмент трассировки (QSpy) , которые позволяют рисовать конечные автоматы, создавать код и отлаживать их.

Книга содержит подробное объяснение того, что / почему реализации и как ее использовать, а также является отличным материалом для понимания основ иерархических и конечных автоматов.

Веб-сайт также содержит ссылки на несколько пакетов поддержки плат для использования программного обеспечения со встроенными платформами.

Pardon me for breaking every rule in computer science, but a state machine is one of the few (I can count only two off hand) places where a goto statement is not only more efficient, but also makes your code cleaner and easier to read. Because goto statements are based on labels, you can name your states instead of having to keep track of a mess of numbers or use an enum. It also makes for much cleaner code since you don't need all the extra cruft of function pointers or huge switch statements and while loops. Did I mention it's more efficient too?

Here's what a state machine might look like:

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

You get the general idea. The point is that you can implement the state machine in an efficient way and one that is relatively easy to read and screams at the reader that they are looking at a state machine. Note that if you are using goto statements, you must still be careful as it is very easy to shoot yourself in the foot while doing so.

Я сделал что-то похожее на то, что описывает paxdiablo, только вместо массива переходов между состояниями / событиями я установил двумерный массив указателей на функции со значением события как индекс одной оси и текущее значение состояния в качестве другой. Затем я просто вызываю state = state_table [event] [state] (params) , и все происходит правильно. Ячейки, представляющие недопустимые комбинации состояния / события, конечно же, получают указатель на функцию, которая говорит об этом.

Очевидно, это работает, только если значения состояния и события находятся в смежных диапазонах и начинаются с 0 или достаточно близко.

Вы можете рассмотреть компилятор конечного автомата http://smc.sourceforge.net/

Эта великолепная утилита с открытым исходным кодом принимает описание конечного автомата на простом языке и компилирует его на любой из дюжины языков, включая C и C ++. Сама утилита написана на Java и может быть включена как часть сборки.

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

Извините, я проявляю чрезмерный энтузиазм и, несомненно, всех отталкиваю. Но это первоклассная утилита, к тому же хорошо задокументированная.

Мне нравится техника для конечных автоматов (по крайней мере, для управления программами) - использовать указатели на функции. Каждое состояние представлено отдельной функцией. Функция принимает входной символ и возвращает указатель функции для следующего состояния. Мониторы центрального цикла диспетчеризации принимают следующий ввод, передают его в текущее состояние и обрабатывают результат.

Набирать его становится немного странно, так как C не имеет способа указать типы указателей функций, возвращающих себя , поэтому функции состояния возвращают void * . Но можно сделать примерно так:

Так поздно (как обычно), но, просматривая ответы на сегодняшний день, я думаю, что чего-то важного не хватает;

Я обнаружил в своих собственных проектах, что это может быть очень полезно для не имеют функцию для каждой допустимой комбинации состояния / события. Мне нравится идея эффективно иметь 2D-таблицу состояний / событий. Но мне нравится, чтобы элементы таблицы были чем-то большим, чем простой указатель на функцию. Вместо этого я пытаюсь организовать свой дизайн таким образом, чтобы в его основе было множество простых элементарных элементов или действий. Таким образом, я могу перечислить эти простые атомарные элементы на каждом пересечении моей таблицы состояний / событий. Идея состоит в том, что вы не должны определять массу из N возведенных в квадрат (обычно очень простых) функций. Почему есть что-то настолько подверженное ошибкам, отнимающее много времени, трудное для написания, трудное для чтения, вы его называете?

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

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

Я использовал компилятор конечного автомата в Java и Python проекты к успеху.

Простейший случай

enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum { THIS, THAT } state;
  switch (state)
  {
    case THIS:
    switch (event)
    {
      case ET_THIS:
      // Handle event.
      break;

      default:
      // Unhandled events in this state.
      break;
    }
    break;

    case THAT:
    // Handle state.
    break;
  }
}

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

Более сложный случай

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

enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum state_type state;
  static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
  enum state_type next_state = state_handler[state](event, parm);
  if (NA != next_state && state != next_state)
  {
    (void)state_handler[state](ET_EXIT, 0);
    state = next_state;
    (void)state_handler[state](ET_ENTER, 0);
  }
}

Я не уверен, что я прибил синтаксис, особенно в отношении массива указателей функций. Я не запускал ничего из этого через компилятор. После проверки, Я заметил, что забыл явно отбросить следующее состояние при обработке псевдособытий (скобка (пустая) перед вызовом state_handler ()). Я люблю это делать, даже если компиляторы молча принимают это упущение. Он сообщает читателям кода, что «да, я действительно имел в виду вызвать функцию без использования возвращаемого значения», и может помешать инструментам статического анализа предупреждать об этом. Это может быть идиосинкразией, потому что я не помню, чтобы кто-то еще делал это.

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

Обработчик состояния может выглядеть так:

static enum state_type handle_this(enum event_type event, union event_parm parm)
{
  enum state_type next_state = NA;
  switch (event)
  {
    case ET_ENTER:
    // Start a timer to do whatever.
    // Do other stuff necessary when entering this state.
    break;

    case ET_WHATEVER:
    // Switch state.
    next_state = THAT;
    break;

    case ET_TIMEOUT:
    // Switch state.
    next_state = FOO;
    break;

    case ET_EXIT:
    // Stop the timer.
    // Generally clean up this state.
    break;
  }
  return next_state;
}

Повышенная сложность

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

Общее программирование

Я хотел бы, чтобы препроцессор имел дело с такими проблемами, как сортировка таблиц или даже генерация конечных автоматов из описаний, позволяя вам «писать программы о программах». Я считаю, что это то, для чего люди Boost используют шаблоны C ++, но я считаю их синтаксис загадочным.

Двумерные таблицы

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