1

您如何实现 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 的状态？

4

5 回答 5

1

总有我称之为飞行意大利面怪物的 FSM 实现风格（FSM-style FSM）：使用 lota goto。例如：

state1:
  do_something();
  goto state2;

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

state3:
  accept;

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

于 2010-06-21T11:28:17.477 回答
1

我把它做成一个表格，内存中的一个平面数组，每个单元格都是一个状态。请看一下废弃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;
};

但这是出于非常特殊的需求（匹配正则表达式）

于 2010-06-21T11:28:22.507 回答
1

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

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

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

  • 您消除了代码重复（尤其是 if/else 语句）
  • 使用新状态更容易扩展
  • 你的类有更好的凝聚力，所以所有相关的逻辑都在一个地方——这也应该让你的代码更容易编写测试。

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

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

于 2010-06-21T11:33:08.817 回答
1

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

然后我开始使用表查找方法。我能够使用这种方法编写一些非常通用的编码风格。但是，当需求发生变化并且我必须支持一些额外的事件时，我被抓住了几次。

I have not written any FSMs lately. The last one I wrote was for a comms module in C++ where I used a "state design pattern" in conjunction with a "command pattern" (action).

于 2010-06-21T12:47:24.063 回答
0

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

于 2010-06-21T12:16:33.803 回答