State Machine

C言語でのState Machine実装

C言語でステートマシンを実装する場合、 どのような実装が考えられるだろうか。 文法a(bc|d)を受理するステートマシンについて switch case文と構造体を使う実装を比較してみよう。

switch case文を使う実装

最も原始的な実装としてswitch caseとenumを組み合わせた方法が挙げられる。

typedef enum state{STATE_INIT,STATE_A,STATE_B,STATE_COMPLETE,STATE_ERROR}state_t;

state_t state_next(state_t s, char c){
  switch (c){
    case STATE_INIT:
      return c=='a'?STATE_A:STATE_ERROR;
    case STATE_A:
      return c=='b'?STATE_B:
             c=='d'?STATE_COMPLETE:STATE_ERROR;
    case STATE_B:
      return c=='c'?STATE_COMPLETE:STATE_ERROR;
    default:
      return STATE_ERROR:
  }
}

これの呼び出し例は次のようになる。

void demo(){
  const char *str="abc";
  state_t s=STATE_INIT;
  for (;*str;str++){
    s=state_next(*str);
    if (s==STATE_ERROR)break;
    if (s==STATE_COMPLETE){
      puts("complete!!");
      break;
    }
  }
}

この方法では、状態が少ないうちは容易な記述で比較的わかりやすいが 状態が増えてくるとswitch case文が肥大化してしまう。 更によくステートマシンの実装で使われるaction,enter,exitも実装すると 肥大化したswitch case文が散逸してしまう。

そして、状態遷移を示す関数を実装するときに状態が既知でないと実装できない。

構造体を使った実装

構造体を用いた実装を考えてみよう。 まず、状態を保存する構造体は次のように書ける。

struct state{
  const char *name;//デバック用に名前をつけておくことをおすすめする。
  void (*action)(void*context);//今回は使わない
  state_t* (*next)(void*context,char);//次のstateを返す(nullable)
  // NOTE: 今回は文字を受理するステートマシンとして書いているため
  // 第二引数をcharにしているがより汎用的に書くならばvoid*にするとよい。
  void (*enter)(void*context);//stateが開始するときに呼び出される(nullable)
  void (*exit)(void*context);//stateが終了するときに呼び出される(nullable)
  void *context;//これをいれることでstate machineの入れ子を実現できる(nullable)
}state_t;

次に、文法a(bc|d)を受理するステートマシンの状態遷移を示す。

Tags: ,