FSM狀態的實現技術

如何執行FSM（編輯：有限狀態機）狀態？我通常會考慮一個像一組函數的FSM，調度程序，和一個線程來指示當前的運行狀態。意思是說，我阻止了對代表狀態的函數/函子的調用。FSM狀態的實現技術

剛纔我已經實現了一個不同的風格，在那裏我仍然代表與功能（對象）S狀態，但線程只是調用一個方法state->step()，它試圖儘可能快地返回。如果州已經完成並且應該進行轉換，則表示相應地。我稱此爲「投票」的風格，因爲功能大多看起來像：

void step() 
{ 
    if(!HaveReachedGoal) 
    { 
    doWhateverNecessary(); 
    return; // get out as fast as possible 
    } 
    // ... test perhaps some more subgoals 
    indicateTransition(); 
}

我知道，這是一個有限狀態機內的FSM。

這感覺相當簡單，但它有一定的優勢。雖然一個線程被阻塞，或者持有某種類型的循環可能很麻煩並且笨拙，但是輪詢更容易進行調試。這是因爲FSM對象每步都在之後重新獲得控制權，並且發佈一些調試信息是一件輕而易舉的事情。

那麼我偏離我的問題：你如何實現有限狀態機的狀態？

來源

2010-06-21 AndreasT

飛行意大利麪怪物？ – Skilldrick 2010-06-21 11:21:47

@Skilldrick：有限狀態機 – sepp2k 2010-06-21 11:24:47

有限狀態機（如果你不是在開玩笑）。 – 2010-06-21 11:25:49

狀態設計模式是實現FSM的一種有趣的方式：

http://en.wikipedia.org/wiki/State_pattern

這是一個非常乾淨的FSM實現方式，但根據FSM的複雜性（但不是狀態量）它可能是混亂的。然而，其優點是：

你消除重複代碼（尤其是if/else語句）
更容易與新州
你班有更好的凝聚力，因此所有相關的邏輯是在一個延長地方 - 這也應該讓你的代碼更容易編寫測試。

有一個Java和C++在這個網站實現：

http://www.vincehuston.org/dp/state.html

來源

2010-06-21 11:33:08

總有一種我稱之爲飛行意大利麪怪物的FSM風格（FSM風格FSM）：使用lotsa goto s。例如：

state1: 
    do_something(); 
    goto state2; 

state2: 
    if (condition) goto state1; 
    else   goto state3; 

state3: 
    accept;

非常好的麪條代碼:-)

來源

2010-06-21 11:28:17

該死！那些FSM是scaaaaary！ ;-) – AndreasT 2010-06-21 11:32:46

我做到了作爲表，在存儲器中的平陣列，每個小區是一個狀態。請看看the abandoned DFA project的cvs源碼。對於example：

class DFA { 
    DFA(); 
    DFA(int mychar_groups,int mycharmap[256],int myi_state); 
    ~DFA(); 
    void add_trans(unsigned int from,char sym,unsigned int to); 
    void add_trans(unsigned int from,unsigned int symn,unsigned int to); 
    /*adds a transition between state from to state to*/ 
    int add_state(bool accepting=false); 
    int to(int state, int symn); 
    int to(int state, char sym); 
    void set_char(char used_chars[],int); 
    void set_char(set<char> char_set); 
    vector<int > table; /*contains the table of the dfa itself*/ 
    void normalize(); 

    vector<unsigned int> char_map; 
    unsigned int char_groups; /*number of characters the DFA uses, 
        char_groups=0 means 1 character group is used*/ 
    unsigned int i_state; /*initial state of the DFA*/ 
    void switch_table_state(int first,int sec); 
    unsigned int num_states; 
    set<int > accepting_states; 
};

但是，這是一個非常特殊需要（正則表達式匹配）

來源

2010-06-21 11:28:22

謝謝Elazar。我正在具體詢問國家，而不是FSM的結構。由於我試圖模擬動態過程隨着時間的推移這個例子（儘管優雅）並沒有多大幫助。我的切換表將非常稀疏。通常只有兩個或（當前最大）三個不同的轉換就足夠了（atm）。 – AndreasT 2010-06-21 11:59:20

如果要創建一個複雜的狀態機，那麼你可能想看看SMC - 狀態機編譯器。這需要一個狀態機的文本表示，並將其編譯成您選擇的語言 - 它支持Java，C，C++，C＃，Python，Ruby，Scala和其他許多語言。

來源

2010-06-21 12:16:33

我記得我的第一個FSM程序。我用C寫了一個非常簡單的開關聲明。從一種狀態切換到另一種狀態或繼續到下一個狀態似乎很自然。

然後我進一步使用表查找方法。我能夠使用這種方法編寫一些非常通用的編碼風格。但是，當需求發生變化時，我被抓了幾次，我不得不支持一些額外的事件。

我最近沒有寫任何FSM。我寫的最後一篇文章是針對C++中的comms模塊，其中我使用了「狀態設計模式」和「命令模式」（action）。

來源

2010-06-21 12:47:24 Syd

FSM狀態的實現技術

回答

相關問題