代码之家 › 专栏 › 技术社区 › AndreasT

FSM状态的实现技术

states finite-automata language-agnostic

AndreasT · 技术社区 · 14 年前

如何实现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。

感觉很简单,但有一定的优势。当一个线程被阻塞或保持在某种类型 while (!CanGoForward)checkGoForward(); 回路可能很笨重,很难操作, 投票更容易调试。那是因为 FSM 对象在之后重新获得控制权每一步,以及发布一些调试信息都是轻而易举的。

我偏离了我的问题: 如何做你实施FSMS的状态?

5 回复 | 直到 14 年前

Robben_Ford_Fan_boy 14 年前

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

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

这是一种非常干净的实现FSM的方法,但根据您的FSM的复杂性(但不是状态的数量),它可能会很混乱。然而,其优势在于:

消除了代码重复(尤其是if/else语句)
新的州更容易扩展
您的类具有更好的内聚性,因此所有相关的逻辑都在一个地方——这也应该使您的代码更容易编写测试。

在这个站点上有一个Java和C++实现:

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

Konrad Rudolph 14 年前

这里总是我所说的飞行意大利面怪兽执行FSMS(FSM风格FSMS)的风格:使用lotsa goto 例如:

state1:
  do_something();
  goto state2;

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

state3:
  accept;

很好的意大利面代码:—)

Elazar Leibovich 14 年前

我把它当作一张表,一个平面数组放在内存中,每个单元都是一个状态。请看一下 the abandoned DFA project . 为了 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;
};

但这是一个非常特殊的需求(匹配正则表达式)

Syd 14 年前

我记得我的第一个FSM计划。我用C写的很简单转换语句。从一个状态切换到另一个状态,或者从后到下一个状态似乎是很自然的。

然后我开始使用 表查找方法 . 我可以使用这种方法编写一些非常通用的编码样式。但是,当需求发生变化时,有几次我被抓住了,我必须支持一些额外的事件。

我最近没有写任何FSM。我写的最后一个是C++中的一个CAMS模块,在这里我用了一个 状态设计模式 “结合a” 命令模式 “(行动)。

Dave Kirby 14 年前

如果您正在创建一个复杂的状态机,那么您可能需要签出 SMC -状态机编译器。这需要一个状态机的文本表示,并将其编译成您所选择的语言——它支持Java、C、C++、Cype、Python、Ruby、斯卡拉和其他许多语言。