FSM状态的实现技术

Question

您如何实现 FSM（编辑：有限状态机）状态？ 我通常将 FSM 视为一组函数， 调度员， 和一个线程来指示当前的运行状态。 意思是，我阻止对代表的函数/函子的调用 州。

刚才我用一种不同的风格实现了一个， 我仍然用函数（对象）表示状态，但是线程 只是调用一个 state->step() 方法，该方法尝试返回 尽快。如果状态已经完成并且 应该发生转变，它相应地表明了这一点。 我将其称为“轮询”风格，因为函数大多看起来 就像：

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

我知道它是 FSM 中的 FSM。

感觉比较简单，但是有一定的优点。 当线程被阻塞或处于某种状态时 while (!CanGoForward)checkGoForward(); 循环可能会很麻烦且难以操作， 轮询感觉更容易调试。 这是因为 FSM 对象在之后重新获得控制权 每一步，输出一些调试信息都是轻而易举的事。

好吧，我偏离了我的问题： 你们如何实现 FSM 的状态？

Answer 1

状态设计模式是实现 FSM 的一种有趣方式：

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

这是实现 FSM 的一种非常干净的方式，但它可能会很混乱，具体取决于 FSM 的复杂性（而不是状态的数量）。然而，优点是：

• 消除了代码重复（尤其是 if/else 语句）
• 更容易扩展新状态
• 您的类具有更好的内聚性，因此所有相关逻辑都位于一个位置 - 这也将使您的代码更容易编写测试为了。

此站点上有 Java 和 C++ 实现：

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

Answer 2

总有一种我称之为“飞面面条怪”的 FSM 实现风格（FSM 风格的 FSM）：使用大量的 goto。例如：

state1:
  do_something();
  goto state2;

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

state3:
  accept;

非常好的意大利面条代码:-)

Answer 3

我把它做成一个表，内存中的平面数组，每个单元格都是一个状态。请查看废弃的 DFA 项目的 cvs 源。对于示例：

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;
};

但这是为了一个非常具体的需求（匹配正则表达式）

Answer 4

我记得我的第一个 FSM 程序。我用 C 语言编写了一个非常简单的 switch 语句。从一种状态切换到另一种状态或进入下一种状态似乎很自然。

然后我开始使用表查找方法。我能够使用这种方法编写一些非常通用的编码风格。然而，当需求发生变化并且我必须支持一些额外的活动时，我遇到了几次麻烦。

我最近没有写任何FSM。我写的最后一个是针对 C++ 中的通信模块，其中我将“状态设计模式”与“命令模式”（操作）结合使用。

Answer 5

如果您要创建复杂的状态机，那么您可能需要查看 SMC - 状态机编译器。它采用状态机的文本表示并将其编译为您选择的语言 - 它支持 Java、C、C++、C#、Python、Ruby、Scala 等。