そして、プロトコルの実装を書き始めた多くの人々は、美しくエレガントにそれを書く方法を考えたので、1か月で、すべてのメモリ
そして、ここでステートマシンが助けになります。それらは有限ステートマシン （ 正規表現で使用される）でもあります。
実際、正規表現を通して、私は彼らに来ました。
最近、私は4つのボタンを備えたデバイスのシンプルな機能を実装する必要がありました。潜在的に混potentiallyとしたボタン押下で2つのコードシーケンスを強調表示し、シーケンスが見つかったときに特定のアクションを実行します。
例で説明しましょう。A、B、C、D、およびコードシーケンスACDAの4つのボタンがあります。 次に、B、C、A、D、A、C、D、A、Bを連続して押すと、デバイスは8回（最後から2番目）のプレス後に電球を点灯します。 正規表現の観点から見ると、タスクは単純です。入力行でサブストリング「ACDA」を探しています。 見つかったらすぐに-電球をオンにします。 しかし、正規表現を操作するためのライブラリをマイクロコントローラにドラッグしたくありませんでした。 私はすべてが自分で簡単にできると感じました。 次に、特定のサブシーケンスの検索に対応する有限状態マシンを独立して実装しようとすることにしました。
そして今、少し理論と実践：
有限状態マシンの主な機能は、可能な状態のセット、信号（イベント）のセット、および遷移表によって記述されることです。 遷移表は、現在の状態と新しい状態の受信信号からのペアの比較です。
処理が必要な3つの状態と3つの信号を持つオートマトンがあると想像してください。 各信号が到着すると、マシンは新しい状態にコミットします。
このタスクのための最も直感的で扱いにくいコード：
enum states { initial = 0, state_1, state_final }; enum signals { sign0, sign1, sign_N }; enum signals getSignal(); void doFSM() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); switch (current_state) { case initial: switch (current_signal) { case sign0: current_state = state_1; break; case sign1: current_state = initial; break; case signN: current_state = state_1; break; } break; case state_1: switch (current_signal) { case sign0: current_state = initial; break; case sign1: current_state = state_1; break; case signN: current_state = state_final; break; } break; case state_final: switch (current_signal) { case sign0: current_state = initial; break; case sign1: current_state = initial; break; case signN: current_state = initial; break; } break; } } }
明らかに、このコードはあまり読みやすくなく、状態と信号の数が増えると壊滅的に成長します。
さらに、各遷移に同じタイプの何らかのアクションを追加する場合（たとえば、ロギングは次のようなものです）
printf("Current = %d, signal = %d\n", current_state, current_signal);
）、これによりコードに多数の変更が生成されます。 そのような変更を編集すると、ほぼ間違いなく何らかのエラーが発生し、デバッグが地獄に変わります。
2つのネストされたスイッチの本質はテーブル（列と列）からの選択であり、正式な有限状態マシンは、各行が信号に対応し、各列が状態に対応し、交差する状態の遷移表の形式で都合よく記述されることを思い出してください自動機。
移行テーブルを定義することにより、既存のコードを簡素化してみましょう。タフトロジーは申し訳ありませんが、テーブルです。
enum states FSM_table[3][3] = { [initial][sign0] = state_1, [initial][sign1] = initial, [initial][sign_N] = state_1, [state_1][sign0] = initial, [state_1][sign1] = state_1, [state_1][sign_N] = state_final, [state_final][sign0] = initial, [state_final][sign1] = initial, [state_final][sign_N] = initial };
実証されたタイプのデータ初期化は、 指定された初期化として知られ、C99で導入されました。
次に、取得したデータ構造を処理する必要があります-doFSM_table関数を作成します。
void doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); current_state = FSM_table[current_state][current_signal]; } }
コードはよりシンプルでわかりやすいですよね？
同様のエントリのボーナスがさらにいくつかあります。
- マシンの各ステップにデバッグ出力を追加することほど簡単なことはありません。
デバッグ出力付きのdoFSM_tablevoid doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); enum states new_state = FSM_table[current_state][current_signal]; printf("Current = %d, signal = %d, new = %d\n", current_state, current_signal, new_state); current_state = new_state; } }
- 収集されたバイナリコードは大幅に減少します。これは、マイクロコントローラーで非常に役立ちます。
- 必要に応じて、たとえば新しい構成をロードするときなど、実行時に遷移テーブルを直接変更できます。
結果のオートマトンをさらに普遍化し、状態遷移以外のアクションを実行できるようにするには、テーブル内の遷移に対応するハンドラー関数へのポインターを追加します。
各遷移で任意のアクションを持つマシン
typedef void (*transition_callback)(enum states state, enum signals signal); struct transition { enum states new_state; transition_callback worker; }; void initial_1_fxn(enum states state, enum signals signal); void initial_1N_fxn(enum states state, enum signals signal); void fxn2(enum states state, enum signals signal); void fxn3(enum states state, enum signals signal); void to_initial_fxn(enum states state, enum signals signal); struct transition FSM_table[3][3] = { [initial][sign0] = {state_1, initial_1_fxn}, [initial][sign1] = {initial, NULL}, [initial][sign_N] = {state_1, initial_1N_fxn}, [state_1][sign0] = {initial, fxn2}, [state_1][sign1] = {state_1, fxn3}, [state_1][sign_N] = {state_final, NULL}, [state_final][sign0] = {initial, to_initial_fxn}, [state_final][sign1] = {initial, to_initial_fxn}, [state_final][sign_N] = {initial, to_initial_fxn} }; void doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); enum states new_state = FSM_table[current_state][current_signal].new_state; transition_callback worker = FSM_table[current_state][current_signal].worker; if (worker != NULL) { worker(current_state, current_signal); } current_state = new_state; } }
一般的に、このメカニズムは長い間改善できますが、この記事の目的は、有限状態マシンを実装するためのユニバーサルライブラリを開発することではなく、複雑なライブラリや言語。
結論として、始めたサブシーケンスを見つけるタスクについて判明した表を示します。
結果の状態テーブル：
enum states FSM_table[9][4] = { [initial ... sACDA][bA ... bD] = initial, // . [initial][bA] = sA, // // ABADC [sA][bB] = sAB, [sAB][bA] = sABA, [sABA][bD] = sABAD, [sABAD][bC] = sABADC, // ACDA [sA][bC] = sAC, [sAC][bD] = sACD, [sACD][bA] = sACDA };