FSM数据结构设计

Question

我想编写一个以空闲状态开始的FSM,并根据某个事件从一个状态移动到另一个状态.我不熟悉FSM的编码,谷歌没有帮助.感谢是否有人可以发布可用于相同的C数据结构.

谢谢,syuga2012

Answer 1

我们过去为Telcos实现了有限状态机,并且总是使用预先填充的结构数组:

/* States */
#define ST_ANY    0
#define ST_START  1
: : : : :

/* Events */
#define EV_INIT   0
#define EV_ERROR  1
: : : : :

/* Rule functions */
int initialize(void) {
    /* Initialize FSM here */
    return ST_INIT_DONE
}
: : : : :

/* Structures for transition rules */
typedef struct {
    int state;
    int event;
    (int)(*fn)();
} rule;
rule ruleset[] = {
    {ST_START, EV_INIT, initialize},
    : : : : :
    {ST_ANY, EV_ERROR, error},
    {ST_ANY, EV_ANY, fatal_fsm_error}
};

我可能将函数指针fn声明为错误,因为这是来自内存.基本上,状态机在数组中搜索相关的状态和事件,并调用函数执行必须完成的操作然后返回新状态.

由于规则的优先级取决于它们在数组中的位置,因此首先放置特定状态并且ST_ANY条目持续存在.找到的第一条规则是使用的规则.

另外,我记得每个州的第一条规则都有一系列索引来加速搜索(所有具有相同起始状态的规则都被分组).

还要记住,这是纯粹的C - 使用C++可能有更好的方法.

Answer 2

请参阅维基百科了解正式定义。您需要决定您的状态集S、您的输入字母 Σ 和您的转换函数 δ 。最简单的表示是让S为整数 0, 1, 2, ..., N -1 的集合，其中N是状态数，Σ 为整数 0, 1, 2, ..., N -1 的集合。 ., M -1，其中M是输入的数量，然后 δ 只是一个大的N × M矩阵。最后，您可以通过存储N位数组来存储接受状态集合，其中如果第 i个状态是接受状态，则第 i 位为 1 ；如果不是接受状态，则第 i 位为 0。

例如，维基百科文章图 3 中的 FSM 如下：

#define NSTATES 2
#define NINPUTS 2
const int transition_function[NSTATES][NINPUTS] = {{1, 0}, {0, 1}};
const int is_accepting_state[NSTATES] = {1, 0};

int main(void)
{
    int current_state = 0;  // initial state
    while(has_more_input())
    {
        // advance to next state based on input
        int input = get_next_input();
        current_state = transition_function[current_state][input];
    }

    int accepted = is_accepting_state[current_state];
    // do stuff
}