C と C++ が混在する小さなプロジェクトを作成しています。私は、ワーカー スレッドの 1 つの中心に、小さなステート マシンを 1 つ構築しています。
SO の専門家が、ステート マシンの設計テクニックを共有してくれるかどうか疑問に思っていました。
注：私は主に、試行およびテストされた実装手法の後です。
更新: SO で収集されたすべての優れた入力に基づいて、次のアーキテクチャに落ち着きました。
95060 次
27 に答える
182
私が以前に設計したステート マシン (C++ ではなく C) はすべて、struct配列とループに行き着きました。構造は基本的に、状態とイベント (ルックアップ用)、および次のような新しい状態を返す関数で構成されます。
typedef struct {
int st;
int ev;
int (*fn)(void);
} tTransition;
次に、状態とイベントを単純な定義で定義します (これらANYは特別なマーカーです。以下を参照してください)。
#define ST_ANY -1
#define ST_INIT 0
#define ST_ERROR 1
#define ST_TERM 2
: :
#define EV_ANY -1
#define EV_KEYPRESS 5000
#define EV_MOUSEMOVE 5001
次に、トランジションによって呼び出されるすべての関数を定義します。
static int GotKey (void) { ... };
static int FsmError (void) { ... };
これらの関数はすべて、変数を使用せず、ステート マシンの新しい状態を返すように記述されています。この例では、グローバル変数を使用して、必要に応じて状態関数に情報を渡します。
FSM は通常、単一のコンパイル ユニット内に閉じ込められ、すべての変数はそのユニットに対して静的であるため、グローバルの使用は思ったほど悪くはありません (これが、上記の「グローバル」を引用符で囲んだ理由です。 FSM、真にグローバルではありません)。すべてのグローバルと同様に、注意が必要です。
次に、transitions 配列は、可能なすべての遷移と、それらの遷移に対して呼び出される関数を定義します (すべてをキャッチする最後のものを含む)。
tTransition trans[] = {
{ ST_INIT, EV_KEYPRESS, &GotKey},
: :
{ ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))
つまり、そのST_INIT状態でイベントを受け取ったEV_KEYPRESS場合は、 を呼び出しますGotKey。
FSM の動作は比較的単純なループになります。
state = ST_INIT;
while (state != ST_TERM) {
event = GetNextEvent();
for (i = 0; i < TRANS_COUNT; i++) {
if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
state = (trans[i].fn)();
break;
}
}
}
}
上記のように、ST_ANYワイルドカードとして を使用することに注意してください。これにより、現在の状態に関係なく、イベントが関数を呼び出すことができます。EV_ANYも同様に機能し、特定の状態のイベントで関数を呼び出すことができます。
また、transitions 配列の最後に到達した場合、FSM が正しく構築されていないことを示すエラーが発生することも保証できます (ST_ANY/EV_ANY組み合わせを使用することにより.
私はこれに似たコードを、組み込みシステム用の通信スタックやプロトコルの初期実装など、非常に多くの通信プロジェクトで使用してきました。大きな利点は、トランジション配列を変更する際の単純さと比較的容易さでした。
今日ではより適切な高レベルの抽象化が存在することは間違いありませんが、それらはすべてこの同じ種類の構造に要約されると思います。
また、ldogコメントに記載されているように、すべての関数に構造体ポインターを渡す (そしてそれをイベント ループで使用する) ことで、グローバルを完全に回避できます。これにより、複数のステート マシンを干渉することなく並行して実行できます。
マシン固有のデータ (最低限の状態) を保持する構造体型を作成し、それをグローバルの代わりに使用するだけです。
私がほとんどそうしなかった理由は、単純に、私が書いたステート マシンのほとんどがシングルトン タイプ (1 回限り、プロセス開始時、構成ファイルの読み取りなど) であり、複数のインスタンスを実行する必要がないためです。 . ただし、複数実行する必要がある場合は価値があります。
于 2009-10-30T02:25:21.817 に答える
83
他の答えは良いですが、ステートマシンが非常に単純な場合に使用した非常に「軽量」な実装は次のようになります。
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 ... */
}
}
ステート マシンが十分に単純で、関数ポインタと状態遷移テーブルのアプローチが過剰である場合に、これを使用します。これは、文字ごとまたは単語ごとの解析に役立つことがよくあります。
于 2009-10-30T05:04:36.417 に答える
31
State Machine Compiler http://smc.sourceforge.net/を検討してください。
この素晴らしいオープン ソース ユーティリティは、単純な言語でステート マシンの記述を受け入れ、それを C や C++ を含む 12 ほどの言語のいずれかにコンパイルします。ユーティリティ自体は Java で記述されており、ビルドの一部として含めることができます。
GoF ステート パターンやその他のアプローチを使用して手作業でコーディングするのではなく、これを行う理由は、ステート マシンがコードとして表現されると、それをサポートするために生成する必要があるボイラープレートの重みで、基礎となる構造が消えてしまう傾向があるためです。このアプローチを使用すると、問題をうまく分離でき、ステート マシンの構造を「見える」状態に保つことができます。自動生成されたコードは、触れる必要のないモジュールに入ります。そのため、記述したサポート コードに影響を与えることなく、ステート マシンの構造に戻っていじることができます。
申し訳ありませんが、私は熱狂しすぎており、間違いなくみんなを先延ばしにしています. しかし、これは一流のユーティリティであり、十分に文書化されています。
于 2009-10-30T17:21:16.360 に答える
22
Miro Samek (ブログState Space、Web サイトState Machines & Tools )の作品を必ずチェックしてください。C/C++ Users Journalの記事は素晴らしいものでした。
Web サイトには、ステート マシン フレームワーク (QP フレームワーク)、イベント ハンドラー (QEP)、基本モデリング ツール (QM)、およびトレース ツール (QSpy)のオープン ソースおよび商用ライセンスの両方での完全な (C/C++) 実装が含まれています。ステート マシンの描画、コードの作成、およびデバッグを許可します。
この本には、実装の内容と理由、およびその使用方法に関する広範な説明が含まれており、階層および有限状態マシンの基礎を理解するための優れた資料でもあります。
この Web サイトには、組み込みプラットフォームでソフトウェアを使用するためのいくつかのボード サポート パッケージへのリンクも含まれています。
于 2009-10-30T08:29:07.457 に答える
11
私はpaxdiabloが説明するものと同様のことをしましたが、状態/イベント遷移の配列の代わりに、イベント値を1つの軸のインデックスとして、現在の状態値をとして、関数ポインターの2次元配列を設定しましたもう一方。その後、電話をかけるだけstate = state_table[event][state](params)で、正しいことが起こります。もちろん、無効な状態/イベントの組み合わせを表すセルは、そう言う関数へのポインタを取得します。
明らかに、これは状態とイベントの値が両方とも連続した範囲であり、0 から始まるか十分に近い場合にのみ機能します。
于 2009-10-30T17:06:56.433 に答える
9
非常に優れたテンプレート ベースの C++ ステート マシン「フレームワーク」が、Stefan Heinzmann の記事で提供されています。
この記事には完全なコードのダウンロードへのリンクがないため、コードをプロジェクトに貼り付けて確認することにしました。以下のものはテストされており、いくつかのマイナーではあるがかなり明らかな欠落部分が含まれています.
ここでの主な革新は、コンパイラが非常に効率的なコードを生成していることです。空の出入りアクションにはコストがかかりません。空でない開始/終了アクションはインライン化されます。コンパイラは、ステートチャートの完全性も検証しています。アクションが欠落していると、リンク エラーが発生します。捕まえられないのは行方不明だけTop::initです。
これは、Miro Samek の実装の非常に優れた代替手段です。欠けているものなしで生活できるのであれば、これは完全な UML Statechart の実装にはほど遠いですが、UML セマンティクスを正しく実装していますが、Samek のコードは設計上、終了/遷移を処理しません。 /entry アクションを正しい順序で。
このコードが必要なことを実行し、システムに適切な C++ コンパイラがあれば、おそらく Miro の C/C++ 実装よりも優れたパフォーマンスを発揮します。コンパイラは、フラット化された O(1) 遷移ステート マシンの実装を生成します。アセンブリ出力の監査により、最適化が意図したとおりに機能することが確認された場合、理論上のパフォーマンスに近づくことができます。最良の部分: 比較的小さく、理解しやすいコードです。
#ifndef HSM_HPP
#define HSM_HPP
// This code is from:
// Yet Another Hierarchical State Machine
// by Stefan Heinzmann
// Overload issue 64 december 2004
// http://accu.org/index.php/journals/252
/* This is a basic implementation of UML Statecharts.
* The key observation is that the machine can only
* be in a leaf state at any given time. The composite
* states are only traversed, never final.
* Only the leaf states are ever instantiated. The composite
* states are only mechanisms used to generate code. They are
* never instantiated.
*/
// Helpers
// A gadget from Herb Sutter's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
class Yes { char a[1]; };
class No { char a[10]; };
static Yes Test(B*); // undefined
static No Test(...); // undefined
public:
enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};
template<bool> class Bool {};
// Top State, Composite State and Leaf State
template <typename H>
struct TopState {
typedef H Host;
typedef void Base;
virtual void handler(Host&) const = 0;
virtual unsigned getId() const = 0;
};
template <typename H, unsigned id, typename B>
struct CompState;
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
typedef B Base;
typedef CompState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
typedef TopState<H> Base;
typedef CompState<H, 0, Base> This;
template <typename X> void handle(H&, const X&) const {}
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
typedef H Host;
typedef B Base;
typedef LeafState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
virtual void handler(H& h) const { handle(h, *this); }
virtual unsigned getId() const { return id; }
static void init(H& h) { h.next(obj); } // don't specialize this
static void entry(H&) {}
static void exit(H&) {}
static const LeafState obj; // only the leaf states have instances
};
template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;
// Transition Object
template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
typedef typename C::Host Host;
typedef typename C::Base CurrentBase;
typedef typename S::Base SourceBase;
typedef typename T::Base TargetBase;
enum { // work out when to terminate template recursion
eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
eS_C = IsDerivedFrom<S, C>::Res,
eC_S = IsDerivedFrom<C, S>::Res,
exitStop = eTB_CB && eS_C,
entryStop = eS_C || eS_CB && !eC_S
};
// We use overloading to stop recursion.
// The more natural template specialization
// method would require to specialize the inner
// template without specializing the outer one,
// which is forbidden.
static void exitActions(Host&, Bool<true>) {}
static void exitActions(Host&h, Bool<false>) {
C::exit(h);
Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
}
static void entryActions(Host&, Bool<true>) {}
static void entryActions(Host& h, Bool<false>) {
Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
C::entry(h);
}
Tran(Host & h) : host_(h) {
exitActions(host_, Bool<false>());
}
~Tran() {
Tran<T, S, T>::entryActions(host_, Bool<false>());
T::init(host_);
}
Host& host_;
};
// Initializer for Compound States
template <typename T>
struct Init {
typedef typename T::Host Host;
Init(Host& h) : host_(h) {}
~Init() {
T::entry(host_);
T::init(host_);
}
Host& host_;
};
#endif // HSM_HPP
テストコードは次のとおりです。
#include <cstdio>
#include "hsm.hpp"
#include "hsmtest.hpp"
/* Implements the following state machine from Miro Samek's
* Practical Statecharts in C/C++
*
* |-init-----------------------------------------------------|
* | s0 |
* |----------------------------------------------------------|
* | |
* | |-init-----------| |-------------------------| |
* | | s1 |---c--->| s2 | |
* | |----------------|<--c----|-------------------------| |
* | | | | | |
* |<-d-| |-init-------| | | |-init----------------| | |
* | | | s11 |<----f----| | s21 | | |
* | /--| |------------| | | |---------------------| | |
* | a | | | | | | | | |
* | \->| | |------g--------->|-init------| | | |
* | | |____________| | | |-b->| s211 |---g--->|
* | |----b---^ |------f------->| | | | |
* | |________________| | |<-d-|___________|<--e----|
* | | |_____________________| | |
* | |_________________________| |
* |__________________________________________________________|
*/
class TestHSM;
typedef CompState<TestHSM,0> Top;
typedef CompState<TestHSM,1,Top> S0;
typedef CompState<TestHSM,2,S0> S1;
typedef LeafState<TestHSM,3,S1> S11;
typedef CompState<TestHSM,4,S0> S2;
typedef CompState<TestHSM,5,S2> S21;
typedef LeafState<TestHSM,6,S21> S211;
enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG };
class TestHSM {
public:
TestHSM() { Top::init(*this); }
~TestHSM() {}
void next(const TopState<TestHSM>& state) {
state_ = &state;
}
Signal getSig() const { return sig_; }
void dispatch(Signal sig) {
sig_ = sig;
state_->handler(*this);
}
void foo(int i) {
foo_ = i;
}
int foo() const {
return foo_;
}
private:
const TopState<TestHSM>* state_;
Signal sig_;
int foo_;
};
bool testDispatch(char c) {
static TestHSM test;
if (c<'a' || 'h'<c) {
return false;
}
printf("Signal<-%c", c);
test.dispatch((Signal)(c-'a'));
printf("\n");
return true;
}
int main(int, char**) {
testDispatch('a');
testDispatch('e');
testDispatch('e');
testDispatch('a');
testDispatch('h');
testDispatch('h');
return 0;
}
#define HSMHANDLER(State) \
template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const
HSMHANDLER(S0) {
switch (h.getSig()) {
case E_SIG: { Tran<X, This, S211> t(h);
printf("s0-E;");
return; }
default:
break;
}
return Base::handle(h, x);
}
HSMHANDLER(S1) {
switch (h.getSig()) {
case A_SIG: { Tran<X, This, S1> t(h);
printf("s1-A;"); return; }
case B_SIG: { Tran<X, This, S11> t(h);
printf("s1-B;"); return; }
case C_SIG: { Tran<X, This, S2> t(h);
printf("s1-C;"); return; }
case D_SIG: { Tran<X, This, S0> t(h);
printf("s1-D;"); return; }
case F_SIG: { Tran<X, This, S211> t(h);
printf("s1-F;"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S11) {
switch (h.getSig()) {
case G_SIG: { Tran<X, This, S211> t(h);
printf("s11-G;"); return; }
case H_SIG: if (h.foo()) {
printf("s11-H");
h.foo(0); return;
} break;
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S2) {
switch (h.getSig()) {
case C_SIG: { Tran<X, This, S1> t(h);
printf("s2-C"); return; }
case F_SIG: { Tran<X, This, S11> t(h);
printf("s2-F"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S21) {
switch (h.getSig()) {
case B_SIG: { Tran<X, This, S211> t(h);
printf("s21-B;"); return; }
case H_SIG: if (!h.foo()) {
Tran<X, This, S21> t(h);
printf("s21-H;"); h.foo(1);
return;
} break;
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S211) {
switch (h.getSig()) {
case D_SIG: { Tran<X, This, S21> t(h);
printf("s211-D;"); return; }
case G_SIG: { Tran<X, This, S0> t(h);
printf("s211-G;"); return; }
}
return Base::handle(h, x);
}
#define HSMENTRY(State) \
template<> inline void State::entry(TestHSM&) { \
printf(#State "-ENTRY;"); \
}
HSMENTRY(S0)
HSMENTRY(S1)
HSMENTRY(S11)
HSMENTRY(S2)
HSMENTRY(S21)
HSMENTRY(S211)
#define HSMEXIT(State) \
template<> inline void State::exit(TestHSM&) { \
printf(#State "-EXIT;"); \
}
HSMEXIT(S0)
HSMEXIT(S1)
HSMEXIT(S11)
HSMEXIT(S2)
HSMEXIT(S21)
HSMEXIT(S211)
#define HSMINIT(State, InitState) \
template<> inline void State::init(TestHSM& h) { \
Init<InitState> i(h); \
printf(#State "-INIT;"); \
}
HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)
于 2013-02-22T02:40:36.283 に答える
5
ステート マシン (少なくともプログラム制御用のもの) で私が気に入っている手法は、関数ポインターを使用することです。各状態は、異なる関数によって表されます。関数は入力シンボルを受け取り、次の状態の関数ポインターを返します。中央のディスパッチ ループ モニターは、次の入力を受け取り、それを現在の状態に送り、結果を処理します。
C には自分自身を返す関数ポインターの型を示す方法がないため、状態関数は を返しvoid*ます。しかし、次のようなことができます：
typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
state_handler current = initial_handler;
/* Let's assume returning null indicates end-of-machine */
while (current) {
current = current(get_input);
}
}
次に、個々の状態関数は、入力をオンにして処理し、適切な値を返すことができます。
于 2009-11-23T01:07:55.233 に答える
5
最も単純なケース
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 に対しても非公開です。特殊なケースは、必要と思われる構成を使用して、メイン スイッチとは別に処理することができます。
より複雑なケース
スイッチが 2 つの画面よりも大きくなった場合は、状態テーブルを使用して関数を直接検索し、各状態を処理する関数に分割します。状態は、イベント ハンドラーに対してまだプライベートです。状態ハンドラ関数は次の状態を返します。必要に応じて、一部のイベントはメイン イベント ハンドラーで特別な扱いを受けることができます。状態の開始と終了、およびおそらく状態マシンの開始に疑似イベントをスローするのが好きです。
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() の呼び出しの前の (void) 括弧) を処理するときに、次の状態を明示的に破棄するのを忘れていたことに気付きました。これは、コンパイラが省略を暗黙のうちに受け入れたとしても、私がやりたいことです。コードの読者に「はい、実際には戻り値を使用せずに関数を呼び出すつもりでした」と伝え、静的分析ツールがそれについて警告するのを止める可能性があります。他の誰かがこれをしているのを見た覚えがないので、それは独特かもしれません.
ポイント: 少し複雑にする (次の状態が現在の状態と異なるかどうかを確認する) ことで、別の場所でコードの重複を回避できます。これは、状態ハンドラー関数が、状態に出入りするときに発生する疑似イベントを利用できるためです。これらのイベントの後に状態ハンドラーの結果が破棄されるため、疑似イベントを処理するときに状態を変更できないことに注意してください。もちろん、動作を変更することもできます。
状態ハンドラーは次のようになります。
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 行と言うべきです)、各状態ハンドラーを別のファイルに入れます。各状態ハンドラーが 2 つの画面よりも長くなった場合は、状態スイッチが分割されたのと同様に、各イベントを別の関数に分割します。これは、状態とは別に、共通テーブルを使用するか、さまざまなスキームを組み合わせて、さまざまな方法で行うことができます。それらのいくつかは、他の人によってここでカバーされています。速度が必要な場合は、テーブルを並べ替え、バイナリ検索を使用します。
汎用プログラミング
プリプロセッサが、テーブルの並べ替えや、記述からのステート マシンの生成などの問題を処理して、「プログラムについてプログラムを書く」ことができるようにしてほしいと思います。これが、Boost の人々が C++ テンプレートを悪用しているものだと思いますが、構文がわかりにくいと思います。
2 次元テーブル
過去に状態/イベントテーブルを使用したことがありますが、最も単純なケースではそれらは必要ないと言わざるを得ません.1画面いっぱいに拡張されたとしても、switchステートメントの明確さと読みやすさを好みます. より複雑なケースでは、他の人が指摘しているように、テーブルはすぐに手に負えなくなります。ここで紹介するイディオムを使用すると、必要に応じて多数のイベントと状態を追加できます。メモリを消費するテーブルを維持する必要はありません (プログラム メモリであっても)。
免責事項
特別なニーズがあると、これらのイディオムはあまり役に立たなくなるかもしれませんが、非常に明確で保守しやすいことがわかりました。
于 2009-12-24T21:45:49.297 に答える
4
非常にテストされていませんが、コーディングするのは楽しいです。今では、元の回答よりも洗練されたバージョンになっています。最新バージョンは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;
}
于 2009-10-30T22:35:59.197 に答える
4
これをどこかで見た
#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);
}
}
于 2009-10-30T22:40:47.770 に答える
4
もう 1 つの興味深いオープン ソース ツールは、statecharts.org の Yakindu Statechart Toolsです。Harel ステートチャートを利用することで、階層的で並列的な状態を提供し、C および C++ (および Java) コードを生成します。ライブラリは使用しませんが、「プレーン コード」アプローチに従います。このコードは、基本的に switch-case 構造を適用します。コード ジェネレーターはカスタマイズすることもできます。さらに、このツールは他にも多くの機能を提供します。
于 2015-04-24T07:53:08.683 に答える
4
私は paxdiable の回答がとても気に入り、ガード変数やステート マシン固有のデータなど、アプリケーションに不足しているすべての機能を実装することにしました。
実装をこのサイトにアップロードして、コミュニティと共有しました。ARM 用の IAR Embedded Workbench を使用してテストされています。
于 2013-01-13T02:15:50.207 に答える
4
メッセージ キューをイベントとして使用する Linux の有限ステート マシンの例を次に示します。イベントはキューに入れられ、順番に処理されます。各イベントの発生状況に応じて状態が変化します。
これは、次のような状態のデータ接続の例です。
- 初期化されていない
- 初期化済み
- 接続済み
- MTU ネゴシエート
- 認証済み
私が追加したもう 1 つの機能は、各メッセージ/イベントのタイムスタンプです。イベント ハンドラーは、古すぎる (有効期限が切れている) イベントを無視します。これは、予期しない状態で立ち往生する可能性がある現実の世界で多く発生する可能性があります。
この例は Linux で実行されます。以下の Makefile を使用してコンパイルし、いろいろ試してみてください。
state_machine.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h> // sysconf()
#include <errno.h> // errno
#include <string.h> // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h> // For O_* constants
#include <sys/stat.h> // For mode constants
#include <mqueue.h>
#include <poll.h>
//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
ST_UNKNOWN = 0,
ST_UNINIT,
ST_INIT,
ST_CONNECTED,
ST_MTU_NEGOTIATED,
ST_AUTHENTICATED,
ST_ERROR,
ST_DONT_CHANGE,
ST_TERM,
} fsmState_t;
//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
EV_UNKNOWN = 0,
EV_INIT_SUCCESS,
EV_INIT_FAIL,
EV_MASTER_CMD_MSG,
EV_CONNECT_SUCCESS,
EV_CONNECT_FAIL,
EV_MTU_SUCCESS,
EV_MTU_FAIL,
EV_AUTH_SUCCESS,
EV_AUTH_FAIL,
EV_TX_SUCCESS,
EV_TX_FAIL,
EV_DISCONNECTED,
EV_DISCON_FAILED,
EV_LAST_ENTRY,
} fsmEvName_t;
typedef struct fsmEvent_type
{
fsmEvName_t name;
struct timeval genTime; // Time the event was generated.
// This allows us to see how old the event is.
} fsmEvent_t;
// Finite State Machine Data Members
typedef struct fsmData_type
{
int connectTries;
int MTUtries;
int authTries;
int txTries;
} fsmData_t;
// Each row of the state table
typedef struct stateTable_type {
fsmState_t st; // Current state
fsmEvName_t evName; // Got this event
int (*conditionfn)(void *); // If this condition func returns TRUE
fsmState_t nextState; // Change to this state and
void (*fn)(void *); // Run this function
} stateTable_t;
// Finite State Machine state structure
typedef struct fsm_type
{
const stateTable_t *pStateTable; // Pointer to state table
int numStates; // Number of entries in the table
fsmState_t currentState; // Current state
fsmEvent_t currentEvent; // Current event
fsmData_t *fsmData; // Pointer to the data attributes
mqd_t mqdes; // Message Queue descriptor
mqd_t master_cmd_mqdes; // Master command message queue
} fsm_t;
// Wildcard events and wildcard state
#define EV_ANY -1
#define ST_ANY -1
#define TRUE (1)
#define FALSE (0)
// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO (sysconf(_SC_MQ_PRIO_MAX) - 1)
static void addev (fsm_t *fsm, fsmEvName_t ev);
static void doNothing (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError (void *fsm) {addev(fsm, EV_ANY);}
static int currentlyLessThanMaxConnectTries (void *fsm) {
fsm_t *l = (fsm_t *)fsm;
return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int isMoreThanMaxConnectTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries (void *fsm) {return TRUE;}
static int isMoreThanMaxMTUtries (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries (void *fsm) {return TRUE;}
static int isMoreThanMaxAuthTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries (void *fsm) {return FALSE;}
static int isMoreThanMaxTXtries (void *fsm) {return TRUE;}
static int didNotSelfDisconnect (void *fsm) {return TRUE;}
static int waitForEvent (fsm_t *fsm);
static void runEvent (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);
// Global State Table
const stateTable_t GST[] = {
// Current state Got this event If this condition func returns TRUE Change to this state and Run this function
{ ST_UNINIT, EV_INIT_SUCCESS, NULL, ST_INIT, &doNothing },
{ ST_UNINIT, EV_INIT_FAIL, NULL, ST_UNINIT, &doInit },
{ ST_INIT, EV_MASTER_CMD_MSG, NULL, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_SUCCESS, NULL, ST_CONNECTED, &doMTU },
{ ST_INIT, EV_CONNECT_FAIL, ¤tlyLessThanMaxConnectTries, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_FAIL, &isMoreThanMaxConnectTries, ST_INIT, &reportFailConnect },
{ ST_CONNECTED, EV_MTU_SUCCESS, NULL, ST_MTU_NEGOTIATED, &doAuth },
{ ST_CONNECTED, EV_MTU_FAIL, ¤tlyLessThanMaxMTUtries, ST_CONNECTED, &doMTU },
{ ST_CONNECTED, EV_MTU_FAIL, &isMoreThanMaxMTUtries, ST_CONNECTED, &doDisconnect },
{ ST_CONNECTED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_MTU_NEGOTIATED, EV_AUTH_SUCCESS, NULL, ST_AUTHENTICATED, &doTransaction },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, ¤tyLessThanMaxAuthTries, ST_MTU_NEGOTIATED, &doAuth },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, &isMoreThanMaxAuthTries, ST_MTU_NEGOTIATED, &doDisconnect },
{ ST_MTU_NEGOTIATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_AUTHENTICATED, EV_TX_SUCCESS, NULL, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_TX_FAIL, ¤tlyLessThanMaxTXtries, ST_AUTHENTICATED, &doTransaction },
{ ST_AUTHENTICATED, EV_TX_FAIL, &isMoreThanMaxTXtries, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_ANY, EV_DISCON_FAILED, NULL, ST_DONT_CHANGE, &doDisconnect },
{ ST_ANY, EV_ANY, NULL, ST_UNINIT, &fsmError } // Wildcard state for errors
};
#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))
int main()
{
int ret = 0;
fsmData_t dataAttr;
dataAttr.connectTries = 0;
dataAttr.MTUtries = 0;
dataAttr.authTries = 0;
dataAttr.txTries = 0;
fsm_t lfsm;
memset(&lfsm, 0, sizeof(fsm_t));
lfsm.pStateTable = GST;
lfsm.numStates = GST_COUNT;
lfsm.currentState = ST_UNINIT;
lfsm.currentEvent.name = EV_ANY;
lfsm.fsmData = &dataAttr;
struct mq_attr attr;
attr.mq_maxmsg = 30;
attr.mq_msgsize = sizeof(fsmEvent_t);
// Dev info
//printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));
ret = mq_unlink("/abcmq");
if (ret == -1) {
fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
}
lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
if (lfsm.mqdes == (mqd_t)-1) {
fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
return -1;
}
doInit(&lfsm); // This will generate the first event
runStateMachine(&lfsm);
return 0;
}
static void runStateMachine(fsm_t *fsm)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
// Cycle through the state machine
while (fsm->currentState != ST_TERM) {
printf("current state [");
printState(fsm->currentState);
printf("]\n");
ret = waitForEvent(fsm);
if (ret == 0) {
printf("got event [");
printEvent(fsm->currentEvent.name);
printf("]\n");
runEvent(fsm);
}
sleep(2);
}
}
static int waitForEvent(fsm_t *fsm)
{
//const int numFds = 2;
const int numFds = 1;
struct pollfd fds[numFds];
int timeout_msecs = -1; // -1 is forever
int ret = 0;
int i = 0;
ssize_t num = 0;
fsmEvent_t newEv;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return -1;
}
fsm->currentEvent.name = EV_ANY;
fds[0].fd = fsm->mqdes;
fds[0].events = POLLIN;
//fds[1].fd = fsm->master_cmd_mqdes;
//fds[1].events = POLLIN;
ret = poll(fds, numFds, timeout_msecs);
if (ret > 0) {
// An event on one of the fds has occurred
for (i = 0; i < numFds; i++) {
if (fds[i].revents & POLLIN) {
// Data may be read on device number i
num = mq_receive(fds[i].fd, (void *)(&newEv),
sizeof(fsmEvent_t), NULL);
if (num == -1) {
fprintf(stderr, "Error on mq_receive(), errno[%d] "
"strerror[%s]\n", errno, strerror(errno));
return -1;
}
if (newEventIsValid(&newEv)) {
fsm->currentEvent = newEv;
} else {
return -1;
}
}
}
} else {
fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
ret, errno, strerror(errno));
return -1;
}
return 0;
}
static int newEventIsValid(fsmEvent_t *event)
{
if (event == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return FALSE;
}
printf("[%s]\n", __func__);
struct timeval now;
getTime(&now);
if ( (event->name < EV_LAST_ENTRY) &&
((now.tv_sec - event->genTime.tv_sec) < (60*5))
)
{
return TRUE;
} else {
return FALSE;
}
}
//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
int i;
int condRet = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
// Find a relevant entry for this state and event
for (i = 0; i < fsm->numStates; i++) {
// Look in the table for our current state or ST_ANY
if ( (fsm->pStateTable[i].st == fsm->currentState) ||
(fsm->pStateTable[i].st == ST_ANY)
)
{
// Is this the event we are looking for?
if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
(fsm->pStateTable[i].evName == EV_ANY)
)
{
if (fsm->pStateTable[i].conditionfn != NULL) {
condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
}
// See if there is a condition associated
// or we are not looking for any condition
//
if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
{
// Set the next state (if applicable)
if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
fsm->currentState = fsm->pStateTable[i].nextState;
printf("new state [");
printState(fsm->currentState);
printf("]\n");
}
// Call the state callback function
fsm->pStateTable[i].fn(fsm);
break;
}
}
}
}
}
//------------------------------------------------
// EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
if (time == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
int ret = gettimeofday(time, NULL);
if (ret != 0) {
fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
errno, strerror(errno));
memset(time, 0, sizeof(struct timeval));
}
}
static void addev (fsm_t *fsm, fsmEvName_t ev)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s] ev[%d]\n", __func__, ev);
if (ev == EV_ANY) {
// Don't generate a new event, just return...
return;
}
fsmEvent_t newev;
getTime(&(newev.genTime));
newev.name = ev;
ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
if (ret == -1) {
fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
__func__, errno, strerror(errno));
}
}
//------------------------------------------------
// end EVENT HANDLERS
//------------------------------------------------
void printState(fsmState_t st)
{
switch(st) {
case ST_UNKNOWN:
printf("ST_UNKNOWN");
break;
case ST_UNINIT:
printf("ST_UNINIT");
break;
case ST_INIT:
printf("ST_INIT");
break;
case ST_CONNECTED:
printf("ST_CONNECTED");
break;
case ST_MTU_NEGOTIATED:
printf("ST_MTU_NEGOTIATED");
break;
case ST_AUTHENTICATED:
printf("ST_AUTHENTICATED");
break;
case ST_ERROR:
printf("ST_ERROR");
break;
case ST_TERM:
printf("ST_TERM");
break;
default:
printf("unknown state");
break;
}
}
void printEvent(fsmEvName_t ev)
{
switch (ev) {
case EV_UNKNOWN:
printf("EV_UNKNOWN");
break;
case EV_INIT_SUCCESS:
printf("EV_INIT_SUCCESS");
break;
case EV_INIT_FAIL:
printf("EV_INIT_FAIL");
break;
case EV_MASTER_CMD_MSG:
printf("EV_MASTER_CMD_MSG");
break;
case EV_CONNECT_SUCCESS:
printf("EV_CONNECT_SUCCESS");
break;
case EV_CONNECT_FAIL:
printf("EV_CONNECT_FAIL");
break;
case EV_MTU_SUCCESS:
printf("EV_MTU_SUCCESS");
break;
case EV_MTU_FAIL:
printf("EV_MTU_FAIL");
break;
case EV_AUTH_SUCCESS:
printf("EV_AUTH_SUCCESS");
break;
case EV_AUTH_FAIL:
printf("EV_AUTH_FAIL");
break;
case EV_TX_SUCCESS:
printf("EV_TX_SUCCESS");
break;
case EV_TX_FAIL:
printf("EV_TX_FAIL");
break;
case EV_DISCONNECTED:
printf("EV_DISCONNECTED");
break;
case EV_LAST_ENTRY:
printf("EV_LAST_ENTRY");
break;
default:
printf("unknown event");
break;
}
}
Makefile
CXX = gcc
COMPFLAGS = -c -Wall -g
state_machine: state_machine.o
$(CXX) -lrt state_machine.o -o state_machine
state_machine.o: state_machine.c
$(CXX) $(COMPFLAGS) state_machine.c
clean:
rm state_machine state_machine.o
于 2019-04-15T14:31:06.993 に答える
3
（いつものように）遅くなりましたが、これまでの回答をスキャンすると、何か重要なものが欠けていると思います。
私自身のプロジェクトで、すべての有効な状態/イベントの組み合わせに対して機能を持たないことが非常に役立つことを発見しました。私は、状態/イベントの 2D テーブルを効果的に持つというアイデアが好きです。しかし、私はテーブル要素が単純な関数ポインター以上のものであることを好みます。代わりに、デザインを整理して、その中心にある単純なアトミック要素またはアクションの束を構成しようとします。そうすれば、状態/イベント テーブルの各交差部分にある単純なアトミック要素を一覧表示できます。アイデアは、大量の N 二乗 (通常は非常に単純な) 関数を定義する必要がないということです。エラーが発生しやすく、時間がかかり、書きにくく、読みにくいものがあるのはなぜですか?
また、オプションの新しい状態と、テーブル内の各セルのオプションの関数ポインターも含めます。関数ポインターは、アトミック アクションのリストを単に起動したくない例外的なケースのために用意されています。
テーブルを編集するだけで、多くの異なる機能を表現でき、新しいコードを記述する必要がない場合は、それが正しく行われていることがわかります。
于 2009-11-23T01:38:54.417 に答える
3
よし、私のは他の人とはちょっと違うと思う。他の回答で見られるよりも、コードとデータをもう少し分離します。私はこれを書くための理論を本当に読みました。これは完全な正規言語を実装しています (悲しいことに、正規表現なしで)。ウルマン、ミンスキー、チョムスキー。すべてを理解したとは言えませんが、昔の巨匠たちの言葉を可能な限り直接的に取り入れました。
「はい」状態または「いいえ」状態への遷移を決定する述語への関数ポインターを使用します。これにより、よりアセンブリ言語に似た方法でプログラムする通常の言語の有限状態アクセプターの作成が容易になります。私のばかげた名前の選択に惑わされないでください。'czek' == 'check'. 'grok' == [ハッカー辞書で調べてください].
そのため、反復ごとに czek は現在の文字を引数として述語関数を呼び出します。述語が true を返す場合、文字が消費され (ポインタが進み)、次の状態を選択するために「y」遷移に従います。述語が false を返す場合、文字は消費されず、'n' 遷移に従います。したがって、すべての命令は双方向の分岐です。当時、メルの物語を読んでいたに違いない。
このコードは私のポストスクリプト インタープリターから直接取得したもので、comp.lang.c のフェローからの多くの指導を受けて現在の形式に発展しました。Postscript には基本的に構文がないため (バランスのとれた括弧のみが必要)、このような正規言語アクセプターはパーサーとしても機能します。
/* currentstr is set to the start of string by czek
and used by setrad (called by israd) to set currentrad
which is used by israddig to determine if the character
in question is valid for the specified radix
--
a little semantic checking in the syntax!
*/
char *currentstr;
int currentrad;
void setrad(void) {
char *end;
currentrad = strtol(currentstr, &end, 10);
if (*end != '#' /* just a sanity check,
the automaton should already have determined this */
|| currentrad > 36
|| currentrad < 2)
fatal("bad radix"); /* should probably be a simple syntaxerror */
}
/*
character classes
used as tests by automatons under control of czek
*/
char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ";
#define EQ(a,b) a==b
#define WITHIN(a,b) strchr(a,b)!=NULL
int israd (int c) {
if (EQ('#',c)) { setrad(); return true; }
return false;
}
int israddig(int c) {
return strchrnul(alpha,toupper(c))-alpha <= currentrad;
}
int isdot (int c) {return EQ('.',c);}
int ise (int c) {return WITHIN("eE",c);}
int issign (int c) {return WITHIN("+-",c);}
int isdel (int c) {return WITHIN("()<>[]{}/%",c);}
int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);}
#undef WITHIN
#undef EQ
/*
the automaton type
*/
typedef struct { int (*pred)(int); int y, n; } test;
/*
automaton to match a simple decimal number
*/
/* /^[+-]?[0-9]+$/ */
test fsm_dec[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, -1 },
/* 2*/ { isdigit, 2, -1 },
};
int acc_dec(int i) { return i==2; }
/*
automaton to match a radix number
*/
/* /^[0-9]+[#][a-Z0-9]+$/ */
test fsm_rad[] = {
/* 0*/ { isdigit, 1, -1 },
/* 1*/ { isdigit, 1, 2 },
/* 2*/ { israd, 3, -1 },
/* 3*/ { israddig, 4, -1 },
/* 4*/ { israddig, 4, -1 },
};
int acc_rad(int i) { return i==4; }
/*
automaton to match a real number
*/
/* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */
/* represents the merge of these (simpler) expressions
[+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
[+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)?
The complexity comes from ensuring at least one
digit in the integer or the fraction with optional
sign and optional optionally-signed exponent.
So passing isdot in state 3 means at least one integer digit has been found
but passing isdot in state 4 means we must find at least one fraction digit
via state 5 or the whole thing is a bust.
*/
test fsm_real[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, 4 },
/* 2*/ { isdigit, 2, 3 },
/* 3*/ { isdot, 6, 7 },
/* 4*/ { isdot, 5, -1 },
/* 5*/ { isdigit, 6, -1 },
/* 6*/ { isdigit, 6, 7 },
/* 7*/ { ise, 8, -1 },
/* 8*/ { issign, 9, 9 },
/* 9*/ { isdigit, 10, -1 },
/*10*/ { isdigit, 10, -1 },
};
int acc_real(int i) {
switch(i) {
case 2: /* integer */
case 6: /* real */
case 10: /* real with exponent */
return true;
}
return false;
}
/*
Helper function for grok.
Execute automaton against the buffer,
applying test to each character:
on success, consume character and follow 'y' transition.
on failure, do not consume but follow 'n' transition.
Call yes function to determine if the ending state
is considered an acceptable final state.
A transition to -1 represents rejection by the automaton
*/
int czek (char *s, test *fsm, int (*yes)(int)) {
int sta = 0;
currentstr = s;
while (sta!=-1 && *s) {
if (fsm[sta].pred((int)*s)) {
sta=fsm[sta].y;
s++;
} else {
sta=fsm[sta].n;
}
}
return yes(sta);
}
/*
Helper function for toke.
Interpret the contents of the buffer,
trying automatons to match number formats;
and falling through to a switch for special characters.
Any token consisting of all regular characters
that cannot be interpreted as a number is an executable name
*/
object grok (state *st, char *s, int ns,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
if (czek(s, fsm_dec, acc_dec)) {
long num;
num = strtol(s,NULL,10);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MIN) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_rad, acc_rad)) {
long ra,num;
ra = (int)strtol(s,NULL,10);
if (ra > 36 || ra < 2) {
error(st,limitcheck);
}
num = strtol(strchr(s,'#')+1, NULL, (int)ra);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MAX) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_real, acc_real)) {
double num;
num = strtod(s,NULL);
if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) {
error(st,limitcheck);
} else {
return consreal(num);
}
}
else switch(*s) {
case '(': {
int c, defer=1;
char *sp = s;
while (defer && (c=next(st,src)) != EOF ) {
switch(c) {
case '(': defer++; break;
case ')': defer--;
if (!defer) goto endstring;
break;
case '\\': c=next(st,src);
switch(c) {
case '\n': continue;
case 'a': c = '\a'; break;
case 'b': c = '\b'; break;
case 'f': c = '\f'; break;
case 'n': c = '\n'; break;
case 'r': c = '\r'; break;
case 't': c = '\t'; break;
case 'v': c = '\v'; break;
case '\'': case '\"':
case '(': case ')':
default: break;
}
}
if (sp-s>ns) error(st,limitcheck);
else *sp++ = c;
}
endstring: *sp=0;
return cvlit(consstring(st,s,sp-s));
}
case '<': {
int c;
char d, *x = "0123456789abcdef", *sp = s;
while (c=next(st,src), c!='>' && c!=EOF) {
if (isspace(c)) continue;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d = (char)c << 4;
while (isspace(c=next(st,src))) /*loop*/;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d |= (char)c;
if (sp-s>ns) error(st,limitcheck);
*sp++ = d;
}
*sp = 0;
return cvlit(consstring(st,s,sp-s));
}
case '{': {
object *a;
size_t na = 100;
size_t i;
object proc;
object fin;
fin = consname(st,"}");
(a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0);
for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) {
if (i == na-1)
(a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0);
}
proc = consarray(st,i);
{ size_t j;
for (j=0; j<i; j++) {
a_put(st, proc, j, a[j]);
}
}
free(a);
return proc;
}
case '/': {
s[1] = (char)next(st,src);
puff(st, s+2, ns-2, src, next, back);
if (s[1] == '/') {
push(consname(st,s+2));
opexec(st, op_cuts.load);
return pop();
}
return cvlit(consname(st,s+1));
}
default: return consname(st,s);
}
return null; /* should be unreachable */
}
/*
Helper function for toke.
Read into buffer any regular characters.
If we read one too many characters, put it back
unless it's whitespace.
*/
int puff (state *st, char *buf, int nbuf,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
int c;
char *s = buf;
while (isreg(c=next(st,src))) {
if (s-buf >= nbuf-1) return false;
*s++ = c;
}
*s = 0;
if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */
return true;
}
/*
Helper function for Stoken Ftoken.
Read a token from src using next and back.
Loop until having read a bona-fide non-whitespace non-comment character.
Call puff to read into buffer up to next delimiter or space.
Call grok to figure out what it is.
*/
#define NBUF MAXLINE
object toke (state *st, object *src,
int (*next)(state *, object *),
void (*back)(state *, int, object *)) {
char buf[NBUF] = "", *s=buf;
int c,sta = 1;
object o;
do {
c=next(st,src);
//if (c==EOF) return null;
if (c=='%') {
if (DUMPCOMMENTS) fputc(c, stdout);
do {
c=next(st,src);
if (DUMPCOMMENTS) fputc(c, stdout);
} while (c!='\n' && c!='\f' && c!=EOF);
}
} while (c!=EOF && isspace(c));
if (c==EOF) return null;
*s++ = c;
*s = 0;
if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back);
if (sta) {
o=grok(st,buf,NBUF-1,src,next,back);
return o;
} else {
return null;
}
}
于 2011-07-20T07:44:49.563 に答える
3
boost.org には、2 つの異なるステート チャートの実装が付属しています。
いつものように、ブーストはあなたをテンプレート地獄に連れて行きます。
最初のライブラリは、よりパフォーマンスが重要なステート マシン用です。2 番目のライブラリは、UML ステートチャートからコードへの直接的な移行パスを提供します。
これは、両方の著者が回答する2つの比較を求めるSOの質問です。
于 2012-01-15T12:27:38.243 に答える
2
この一連の Ars OpenForum の投稿では、やや複雑な制御ロジックについて、C でのステート マシンとしての非常にわかりやすい実装が含まれています。
于 2009-10-30T02:23:50.290 に答える
1
私はJavaおよびPythonプロジェクトでステートマシンコンパイラを使用して成功しました。
于 2009-12-20T18:41:14.073 に答える
1
あなたの質問は非常に一般的
です. 役に立つかもしれない2つの参考記事があります.
-
この記事では、組み込みシステムのステート マシンを実装する簡単な方法について説明します。この記事では、ステート マシンは少数の状態の 1 つになるアルゴリズムとして定義されています。状態とは、入力と出力、および入力と次の状態の所定の関係を引き起こす条件です。
知識のある読者は、この記事で説明されているステート マシンが Mealy マシンであることにすぐに気付くでしょう。Mealy マシンは、出力が現在の状態と入力の両方の関数である状態マシンであり、出力が状態のみの関数である Moore マシンとは対照的です。- C および C++ でのステート マシンのコーディング
この記事では、ステート マシンの基礎と、C または C++ でステート マシンをコーディングするための簡単なプログラミング ガイドラインについて説明します。これらの単純な手法がより一般的になり、ソース コードからステート マシンの構造をすぐに確認できるようになることを願っています。
- C および C++ でのステート マシンのコーディング
于 2009-10-30T02:18:11.583 に答える
1
C++ と OO コードを使用できることを暗示していることを考えると、「GoF」状態パターン (GoF = Gang of Four、デザイン パターンを脚光を浴びたデザイン パターンの本を書いた人) を評価することをお勧めします。
これは特に複雑ではなく、広く使用され、議論されているため、例と説明をオンラインで簡単に確認できます。
また、後日、コードを保守している他の誰かが認識できる可能性が非常に高くなります。
効率が心配な場合は、実際にベンチマークを行って、多くの要因がパフォーマンスに影響を与えるため、非オブジェクト指向アプローチがより効率的であることを確認する価値があります。オブジェクト指向が悪いだけで機能コードが良いとは限りません。同様に、メモリ使用量が制約になっている場合は、状態パターンを使用する場合に特定のアプリケーションでこれが実際に問題になるかどうかを確認するために、いくつかのテストまたは計算を行う価値があります。
Craig が示唆するように、以下は「Gof」状態パターンへのリンクです。
于 2011-12-16T15:46:49.990 に答える
0
オープンソースライブラリOpenFSTを使用できます。
OpenFstは、重み付き有限状態トランスデューサ（FST）を構築、結合、最適化、および検索するためのライブラリです。重み付き有限状態トランスデューサはオートマトンであり、各遷移には入力ラベル、出力ラベル、および重みがあります。より馴染みのある有限状態アクセプターは、各遷移の入力ラベルと出力ラベルが等しいトランスデューサーとして表されます。有限状態アクセプターは、文字列のセット（具体的には、通常のセットまたは合理的なセット）を表すために使用されます。有限状態トランスデューサは、文字列のペア間の二項関係を表すために使用されます（具体的には、有理変換）。重みは、特定の遷移を行うためのコストを表すために使用できます。
于 2012-01-23T21:44:19.610 に答える
0
void (* StateController)(void);
void state1(void);
void state2(void);
void main()
{
StateController=&state1;
while(1)
{
(* StateController)();
}
}
void state1(void)
{
//do something in state1
StateController=&state2;
}
void state2(void)
{
//do something in state2
//Keep changing function direction based on state transition
StateController=&state1;
}
于 2016-01-30T09:36:39.883 に答える
0
私は個人的に、ポインター配列と組み合わせて自己参照構造体を使用しています。しばらく前に github にチュートリアルをアップロードしました。リンク:
https://github.com/mmelchger/polling_state_machine_c
注: このスレッドがかなり古いものであることは承知していますが、ステート マシンの設計に関する意見や考えを得て、C で可能なステート マシン設計の例を提供できることを願っています。
于 2016-12-13T09:55:03.997 に答える