典型的なステートマシンの実装パターンはありますか?

私は、ほとんどのステートマシンでテーブル駆動型のアプローチを使用することを好みます:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

これはもちろん、複数のステートマシンなどをサポートするように拡張できます。遷移アクションにも対応できます。

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

テーブル駆動型のアプローチは、保守と拡張が容易で、状態図へのマッピングが簡単です。

FSM について言及した別の C の質問に対する私の回答を見たことがあるかもしれません。これが私のやり方です:

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

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

以下のマクロを定義して

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

これは、特定のケースに合わせて変更できます。たとえば、ファイル FSMFILE があるとします。 FSM を駆動したいので、次の文字を読み取るアクションをマクロ自体に組み込むことができます:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

これで、2 つのタイプの遷移ができました。1 つは状態に移行して新しい文字を読み取るもので、もう 1 つは入力を消費せずに状態に移行するものです。

次のような方法で EOF の処理を自動化することもできます:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

このアプローチの良い点は、描画した状態図を実際のコードに直接変換できることです。逆に、コードから状態図を簡単に描画できます。

FSM を実装するための他の手法では、遷移の構造は制御構造 (while、if、switch ...) に埋め込まれ、変数値 (通常は state 変数) であり、優れた図を複雑なコードに関連付けるのは複雑な作業になる場合があります。

このテクニックは、残念ながらもう発行されていない偉大な「Computer Language」誌に掲載された記事から学びました。

テーブルアプローチも使用しました。ただし、オーバーヘッドがあります。ポインターの 2 つ目のリストを保存する理由() のない C の関数は const ポインターです。できること:

struct state;
typedef void (*state_func_t)( struct state* );

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

        // do other program logic, run other state machines, etc
    }
}

もちろん、恐怖要因 (つまり、安全性と速度) によっては、有効なポインターを確認したい場合があります。ステートマシンが 3 つほどのステートよりも大きい場合、上記のアプローチは、同等のスイッチまたはテーブルアプローチよりも少ない命令である必要があります。次のようにマクロ化することもできます:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

また、OPの例から、ステートマシンを考えたり設計したりするときに単純化する必要があると感じています。遷移状態をロジックに使用する必要はありません。各状態関数は、過去の状態を明示的に知らなくても、その役割を実行できる必要があります。基本的に、現在の状態から別の状態に移行する方法を設計します。

最後に、「機能」境界に基づいてステートマシンの設計を開始しないでください。そのためにはサブ機能を使用してください。代わりに、続行する前に何かが発生するまで待機する必要がある時期に基づいて、状態を分割します。これにより、結果が得られるまでにステートマシンを実行する必要がある回数を最小限に抑えることができます。これは、I/O 関数や割り込みハンドラを書くときに重要です。

また、従来の switch ステートメントのいくつかの長所と短所:

長所: