我正在制作一个混合 C 和 C++ 的小项目。我正在我的一个工作线程的核心构建一个小型状态机。
我想知道您的 SO 专家是否会分享您的状态机设计技术。
注意：我主要是在经过尝试和测试的实施技术之后。
更新：基于 SO 上收集的所有重要输入，我已经确定了这个架构：
问问题
95060 次
27 回答
182
我之前设计的状态机（C，不是 C++）都归结为一个struct数组和一个循环。该结构基本上由一个状态和事件（用于查找）以及一个返回新状态的函数组成，例如：
typedef struct {
int st;
int ev;
int (*fn)(void);
} tTransition;
然后你用简单的定义来定义你的状态和事件（ANY那些是特殊的标记，见下文）：
#define ST_ANY -1
#define ST_INIT 0
#define ST_ERROR 1
#define ST_TERM 2
: :
#define EV_ANY -1
#define EV_KEYPRESS 5000
#define EV_MOUSEMOVE 5001
然后定义转换调用的所有函数：
static int GotKey (void) { ... };
static int FsmError (void) { ... };
所有这些函数都被编写为不接受变量并为状态机返回新状态。在此示例中，全局变量用于在必要时将任何信息传递给状态函数。
使用全局变量并不像听起来那么糟糕，因为 FSM 通常被锁定在单个编译单元中，并且所有变量对于该单元都是静态的（这就是为什么我在上面的“全局”周围使用引号 - 它们在FSM，而不是真正的全球性）。与所有全局变量一样，它需要小心。
然后转换数组定义所有可能的转换以及为这些转换调用的函数（包括最后一个全能转换）：
tTransition trans[] = {
{ ST_INIT, EV_KEYPRESS, &GotKey},
: :
{ ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))
这意味着：如果您在该ST_INIT州并收到EV_KEYPRESS事件，请致电GotKey.
FSM 的工作就变成了一个相对简单的循环：
state = ST_INIT;
while (state != ST_TERM) {
event = GetNextEvent();
for (i = 0; i < TRANS_COUNT; i++) {
if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
state = (trans[i].fn)();
break;
}
}
}
}
如上所述，请注意ST_ANY作为通配符的使用，允许事件调用函数，无论当前状态如何。EV_ANY也类似地工作，允许处于特定状态的任何事件调用函数。
它还可以保证，如果您到达转换数组的末尾，则会收到一条错误消息，说明您的 FSM 没有正确构建（通过使用ST_ANY/EV_ANY组合.
我在很多通信项目中都使用过类似的代码，例如早期实现的通信堆栈和嵌入式系统协议。最大的优点是它的简单性和更改转换数组的相对容易性。
我毫不怀疑会有更高级别的抽象，现在可能更合适，但我怀疑它们都会归结为这种相同的结构。
而且，作为ldog注释中的状态，您可以通过将结构指针传递给所有函数（并在事件循环中使用它）来完全避免全局变量。这将允许多个状态机并排运行而不受干扰。
只需创建一个结构类型来保存特定于机器的数据（至少是状态）并使用它而不是全局变量。
我很少这样做的原因仅仅是因为我编写的大多数状态机都是单例类型（例如一次性、进程启动、配置文件读取），不需要运行多个实例. 但是，如果您需要运行多个，它具有价值。
于 2009-10-30T02:25:21.817 回答
83
其他答案很好，但是当状态机非常简单时，我使用的一个非常“轻量级”的实现看起来像：
enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };
enum state current_state = ST_NEW;
while (current_state != ST_END)
{
input = get_input();
switch (current_state)
{
case ST_NEW:
/* Do something with input and set current_state */
break;
case ST_OPEN:
/* Do something different and set current_state */
break;
/* ... etc ... */
}
}
当状态机足够简单以至于函数指针和状态转换表方法过大时，我会使用它。这对于逐个字符或逐个单词的解析通常很有用。
于 2009-10-30T05:04:36.417 回答
42
请原谅我违反了计算机科学中的每一条规则，但状态机是少数几个（我只能数出两个）goto语句不仅更有效，而且使您的代码更清晰、更易于阅读的地方之一。因为goto语句是基于标签的，所以您可以命名您的状态，而不必跟踪一堆乱七八糟的数字或使用枚举。它还使代码更简洁，因为您不需要所有额外的函数指针或巨大的 switch 语句和 while 循环。我有没有提到它也更有效？
下面是状态机的样子：
void state_machine() {
first_state:
// Do some stuff here
switch(some_var) {
case 0:
goto first_state;
case 1:
goto second_state;
default:
return;
}
second_state:
// Do some stuff here
switch(some_var) {
case 0:
goto first_state;
case 1:
goto second_state;
default:
return;
}
}
你明白了一般的想法。关键是您可以以一种有效的方式实现状态机，并且这种方式相对容易阅读，并向读者尖叫他们正在查看状态机。请注意，如果您使用goto语句，您仍然必须小心，因为这样做很容易击中自己的脚。
于 2009-10-31T03:33:31.910 回答
31
您可以考虑使用状态机编译器http://smc.sourceforge.net/
这个出色的开源实用程序接受以简单语言描述的状态机，并将其编译为十几种语言中的任何一种——包括 C 和 C++。该实用程序本身是用 Java 编写的，可以作为构建的一部分包含在内。
这样做的原因，而不是使用 GoF 状态模式或任何其他方法的手工编码，是因为一旦你的状态机被表达为代码，底层结构往往会在需要生成支持它的样板文件的重量下消失。使用这种方法可以很好地分离关注点，并保持状态机的结构“可见”。自动生成的代码进入您不需要接触的模块，这样您就可以返回并修改状态机的结构，而不会影响您编写的支持代码。
对不起，我太热情了，毫无疑问让所有人都失望了。但它是一流的实用程序，并且有据可查。
于 2009-10-30T17:21:16.360 回答
22
请务必查看 Miro Samek 的工作（博客State Space、网站State Machines & Tools），他在C/C++ 用户期刊上的文章很棒。
该网站包含状态机框架 (QP Framework)、事件处理程序 (QEP)、基本建模工具 (QM)和跟踪工具 (QSpy)的开源和商业许可的完整 (C/C++) 实现。允许绘制状态机、创建代码和调试它们。
这本书包含对实现的内容/原因以及如何使用它的广泛解释，也是理解分层和有限状态机基础知识的重要材料。
该网站还包含几个板级支持包的链接，以便在嵌入式平台上使用该软件。
于 2009-10-30T08:29:07.457 回答
11
我做了类似于 paxdiablo 描述的事情，只是我设置了一个二维函数指针数组，而不是状态/事件转换数组，事件值作为一个轴的索引，当前状态值作为另一个。然后我只是打电话state = state_table[event][state](params)，正确的事情发生了。当然，代表无效状态/事件组合的单元格会获得一个指向这样的函数的指针。
显然，这仅在状态和事件值都是连续范围并且从 0 开始或足够接近时才有效。
于 2009-10-30T17:06:56.433 回答
9
Stefan Heinzmann 在他的文章中给出了一个非常好的基于模板的 C++ 状态机“框架” 。
由于文章中没有指向完整代码下载的链接，因此我冒昧地将代码粘贴到项目中并进行检查。下面的东西经过测试，包括一些次要但非常明显的缺失部分。
这里的主要创新是编译器正在生成非常高效的代码。空的进入/退出动作没有成本。内联非空进入/退出操作。编译器也在验证状态图的完整性。缺少操作会产生链接错误。唯一没有被抓住的是失踪Top::init。
这是 Miro Samek 实现的一个非常好的替代方案，如果您可以生活而不会缺少什么——这远非一个完整的 UML Statechart 实现，尽管它正确实现了 UML 语义，而 Samek 的设计代码不处理退出/转换/entry 动作以正确的顺序。
如果此代码适用于您需要做的事情，并且您的系统有一个不错的 C++ 编译器，那么它的性能可能会比 Miro 的 C/C++ 实现更好。编译器会为您生成一个扁平的 O(1) 转换状态机实现。如果对装配输出的审核确认优化按预期工作，那么您将接近理论性能。最好的部分：它相对较小，易于理解的代码。
#ifndef HSM_HPP
#define HSM_HPP
// This code is from:
// Yet Another Hierarchical State Machine
// by Stefan Heinzmann
// Overload issue 64 december 2004
// http://accu.org/index.php/journals/252
/* This is a basic implementation of UML Statecharts.
* The key observation is that the machine can only
* be in a leaf state at any given time. The composite
* states are only traversed, never final.
* Only the leaf states are ever instantiated. The composite
* states are only mechanisms used to generate code. They are
* never instantiated.
*/
// Helpers
// A gadget from Herb Sutter's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
class Yes { char a[1]; };
class No { char a[10]; };
static Yes Test(B*); // undefined
static No Test(...); // undefined
public:
enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};
template<bool> class Bool {};
// Top State, Composite State and Leaf State
template <typename H>
struct TopState {
typedef H Host;
typedef void Base;
virtual void handler(Host&) const = 0;
virtual unsigned getId() const = 0;
};
template <typename H, unsigned id, typename B>
struct CompState;
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
typedef B Base;
typedef CompState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
typedef TopState<H> Base;
typedef CompState<H, 0, Base> This;
template <typename X> void handle(H&, const X&) const {}
static void init(H&); // no implementation
static void entry(H&) {}
static void exit(H&) {}
};
template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
typedef H Host;
typedef B Base;
typedef LeafState<H, id, Base> This;
template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
virtual void handler(H& h) const { handle(h, *this); }
virtual unsigned getId() const { return id; }
static void init(H& h) { h.next(obj); } // don't specialize this
static void entry(H&) {}
static void exit(H&) {}
static const LeafState obj; // only the leaf states have instances
};
template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;
// Transition Object
template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
typedef typename C::Host Host;
typedef typename C::Base CurrentBase;
typedef typename S::Base SourceBase;
typedef typename T::Base TargetBase;
enum { // work out when to terminate template recursion
eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
eS_C = IsDerivedFrom<S, C>::Res,
eC_S = IsDerivedFrom<C, S>::Res,
exitStop = eTB_CB && eS_C,
entryStop = eS_C || eS_CB && !eC_S
};
// We use overloading to stop recursion.
// The more natural template specialization
// method would require to specialize the inner
// template without specializing the outer one,
// which is forbidden.
static void exitActions(Host&, Bool<true>) {}
static void exitActions(Host&h, Bool<false>) {
C::exit(h);
Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
}
static void entryActions(Host&, Bool<true>) {}
static void entryActions(Host& h, Bool<false>) {
Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
C::entry(h);
}
Tran(Host & h) : host_(h) {
exitActions(host_, Bool<false>());
}
~Tran() {
Tran<T, S, T>::entryActions(host_, Bool<false>());
T::init(host_);
}
Host& host_;
};
// Initializer for Compound States
template <typename T>
struct Init {
typedef typename T::Host Host;
Init(Host& h) : host_(h) {}
~Init() {
T::entry(host_);
T::init(host_);
}
Host& host_;
};
#endif // HSM_HPP
测试代码如下。
#include <cstdio>
#include "hsm.hpp"
#include "hsmtest.hpp"
/* Implements the following state machine from Miro Samek's
* Practical Statecharts in C/C++
*
* |-init-----------------------------------------------------|
* | s0 |
* |----------------------------------------------------------|
* | |
* | |-init-----------| |-------------------------| |
* | | s1 |---c--->| s2 | |
* | |----------------|<--c----|-------------------------| |
* | | | | | |
* |<-d-| |-init-------| | | |-init----------------| | |
* | | | s11 |<----f----| | s21 | | |
* | /--| |------------| | | |---------------------| | |
* | a | | | | | | | | |
* | \->| | |------g--------->|-init------| | | |
* | | |____________| | | |-b->| s211 |---g--->|
* | |----b---^ |------f------->| | | | |
* | |________________| | |<-d-|___________|<--e----|
* | | |_____________________| | |
* | |_________________________| |
* |__________________________________________________________|
*/
class TestHSM;
typedef CompState<TestHSM,0> Top;
typedef CompState<TestHSM,1,Top> S0;
typedef CompState<TestHSM,2,S0> S1;
typedef LeafState<TestHSM,3,S1> S11;
typedef CompState<TestHSM,4,S0> S2;
typedef CompState<TestHSM,5,S2> S21;
typedef LeafState<TestHSM,6,S21> S211;
enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG };
class TestHSM {
public:
TestHSM() { Top::init(*this); }
~TestHSM() {}
void next(const TopState<TestHSM>& state) {
state_ = &state;
}
Signal getSig() const { return sig_; }
void dispatch(Signal sig) {
sig_ = sig;
state_->handler(*this);
}
void foo(int i) {
foo_ = i;
}
int foo() const {
return foo_;
}
private:
const TopState<TestHSM>* state_;
Signal sig_;
int foo_;
};
bool testDispatch(char c) {
static TestHSM test;
if (c<'a' || 'h'<c) {
return false;
}
printf("Signal<-%c", c);
test.dispatch((Signal)(c-'a'));
printf("\n");
return true;
}
int main(int, char**) {
testDispatch('a');
testDispatch('e');
testDispatch('e');
testDispatch('a');
testDispatch('h');
testDispatch('h');
return 0;
}
#define HSMHANDLER(State) \
template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const
HSMHANDLER(S0) {
switch (h.getSig()) {
case E_SIG: { Tran<X, This, S211> t(h);
printf("s0-E;");
return; }
default:
break;
}
return Base::handle(h, x);
}
HSMHANDLER(S1) {
switch (h.getSig()) {
case A_SIG: { Tran<X, This, S1> t(h);
printf("s1-A;"); return; }
case B_SIG: { Tran<X, This, S11> t(h);
printf("s1-B;"); return; }
case C_SIG: { Tran<X, This, S2> t(h);
printf("s1-C;"); return; }
case D_SIG: { Tran<X, This, S0> t(h);
printf("s1-D;"); return; }
case F_SIG: { Tran<X, This, S211> t(h);
printf("s1-F;"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S11) {
switch (h.getSig()) {
case G_SIG: { Tran<X, This, S211> t(h);
printf("s11-G;"); return; }
case H_SIG: if (h.foo()) {
printf("s11-H");
h.foo(0); return;
} break;
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S2) {
switch (h.getSig()) {
case C_SIG: { Tran<X, This, S1> t(h);
printf("s2-C"); return; }
case F_SIG: { Tran<X, This, S11> t(h);
printf("s2-F"); return; }
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S21) {
switch (h.getSig()) {
case B_SIG: { Tran<X, This, S211> t(h);
printf("s21-B;"); return; }
case H_SIG: if (!h.foo()) {
Tran<X, This, S21> t(h);
printf("s21-H;"); h.foo(1);
return;
} break;
default: break;
}
return Base::handle(h, x);
}
HSMHANDLER(S211) {
switch (h.getSig()) {
case D_SIG: { Tran<X, This, S21> t(h);
printf("s211-D;"); return; }
case G_SIG: { Tran<X, This, S0> t(h);
printf("s211-G;"); return; }
}
return Base::handle(h, x);
}
#define HSMENTRY(State) \
template<> inline void State::entry(TestHSM&) { \
printf(#State "-ENTRY;"); \
}
HSMENTRY(S0)
HSMENTRY(S1)
HSMENTRY(S11)
HSMENTRY(S2)
HSMENTRY(S21)
HSMENTRY(S211)
#define HSMEXIT(State) \
template<> inline void State::exit(TestHSM&) { \
printf(#State "-EXIT;"); \
}
HSMEXIT(S0)
HSMEXIT(S1)
HSMEXIT(S11)
HSMEXIT(S2)
HSMEXIT(S21)
HSMEXIT(S211)
#define HSMINIT(State, InitState) \
template<> inline void State::init(TestHSM& h) { \
Init<InitState> i(h); \
printf(#State "-INIT;"); \
}
HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)
于 2013-02-22T02:40:36.283 回答
5
我喜欢状态机（至少是用于程序控制的）的技术是使用函数指针。每个状态由不同的函数表示。该函数接受一个输入符号并返回下一个状态的函数指针。中央调度循环监视器获取下一个输入，将其提供给当前状态，并处理结果。
它的类型有点奇怪，因为 C 没有办法指示返回自身的函数指针的类型，所以状态函数 return void*。但是你可以这样做：
typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
state_handler current = initial_handler;
/* Let's assume returning null indicates end-of-machine */
while (current) {
current = current(get_input);
}
}
然后您的各个状态函数可以打开其输入以处理并返回适当的值。
于 2009-11-23T01:07:55.233 回答
5
最简单的情况
enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
static enum { THIS, THAT } state;
switch (state)
{
case THIS:
switch (event)
{
case ET_THIS:
// Handle event.
break;
default:
// Unhandled events in this state.
break;
}
break;
case THAT:
// Handle state.
break;
}
}
要点：状态是私有的，不仅对编译单元而且对 event_handler。特殊情况可以使用任何认为必要的结构与主开关分开处理。
更复杂的案例
当开关大于几个屏幕满时，将其拆分为处理每个状态的函数，使用状态表直接查找函数。状态仍然是事件处理程序私有的。状态处理函数返回下一个状态。如果需要，某些事件仍然可以在主事件处理程序中接受特殊处理。我喜欢为状态进入和退出以及状态机启动添加伪事件：
enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
static enum state_type state;
static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
enum state_type next_state = state_handler[state](event, parm);
if (NA != next_state && state != next_state)
{
(void)state_handler[state](ET_EXIT, 0);
state = next_state;
(void)state_handler[state](ET_ENTER, 0);
}
}
我不确定我是否掌握了语法，尤其是关于函数指针数组。我没有通过编译器运行任何这些。经过审查，我注意到我在处理伪事件时忘记显式丢弃下一个状态（调用 state_handler() 之前的 (void) 括号）。这是我喜欢做的事情，即使编译器默默地接受这个遗漏。它告诉代码的读者“是的，我确实是想在不使用返回值的情况下调用函数”，并且它可能会阻止静态分析工具发出警告。这可能是特殊的，因为我不记得见过其他人这样做。
要点：增加一点点复杂性（检查下一个状态是否与当前不同），可以避免在其他地方重复代码，因为状态处理函数可以享受进入和离开状态时发生的伪事件。请记住，在处理伪事件时状态不能改变，因为状态处理程序的结果在这些事件之后被丢弃。您当然可以选择修改行为。
状态处理程序如下所示：
static enum state_type handle_this(enum event_type event, union event_parm parm)
{
enum state_type next_state = NA;
switch (event)
{
case ET_ENTER:
// Start a timer to do whatever.
// Do other stuff necessary when entering this state.
break;
case ET_WHATEVER:
// Switch state.
next_state = THAT;
break;
case ET_TIMEOUT:
// Switch state.
next_state = FOO;
break;
case ET_EXIT:
// Stop the timer.
// Generally clean up this state.
break;
}
return next_state;
}
更复杂
当编译单元变得太大时（不管你觉得是什么，我应该说大约 1000 行），将每个状态处理程序放在一个单独的文件中。当每个状态处理程序变得超过几个屏幕时，将每个事件拆分到一个单独的函数中，类似于拆分状态切换的方式。您可以通过多种方式执行此操作，与状态分开或使用公用表，或组合各种方案。其中一些已被其他人覆盖在这里。如果需要速度，请对表进行排序并使用二进制搜索。
通用编程
我希望预处理器处理诸如排序表甚至从描述中生成状态机之类的问题，从而允许您“编写有关程序的程序”。我相信这就是 Boost 人利用 C++ 模板的目的，但我发现语法晦涩难懂。
二维表
我过去使用过状态/事件表，但我不得不说，对于最简单的情况，我认为它们没有必要，而且我更喜欢 switch 语句的清晰性和可读性，即使它确实超过了一个屏幕。正如其他人所指出的那样，对于更复杂的情况，表格很快就会失控。我在这里介绍的习惯用法允许您在需要时添加大量事件和状态，而无需维护内存消耗表（即使它可能是程序内存）。
免责声明
特殊需要可能会降低这些习语的用处，但我发现它们非常清晰且易于维护。
于 2009-12-24T21:45:49.297 回答
4
未经测试，但编码很有趣，现在比我原来的答案更精致；可以在mercurial.intuxication.org找到最新版本：
sm.h
#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
"use '#define SM_ARGS (void)' to get an empty argument list"
#endif
#ifndef SM_STATES
#error "SM_STATES undefined: " \
"you must provide a list of comma-separated states"
#endif
typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;
#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)
#define sm_def(NAME) \
static sm_state NAME ## _fn SM_ARGS; \
static const sm_state NAME = (sm_state)NAME ## _fn; \
static sm_state NAME ## _fn SM_ARGS
例子.c
#include <stdio.h>
#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"
sm_def(EVEN)
{
printf("even %i\n", i);
return ODD;
}
sm_def(ODD)
{
printf("odd %i\n", i);
return EVEN;
}
int main(void)
{
int i = 0;
sm_state state = EVEN;
for(; i < 10; ++i)
state = sm_transit(state)(i);
return 0;
}
于 2009-10-30T22:35:59.197 回答
4
在某处看到这个
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
于 2009-10-30T22:40:47.770 回答
4
我真的很喜欢 paxdiable 的回答，并决定为我的应用程序实现所有缺少的功能，例如保护变量和状态机特定数据。
我将我的实现上传到该站点以与社区分享。它已经使用 IAR Embedded Workbench for ARM 进行了测试。
于 2013-01-13T02:15:50.207 回答
4
另一个有趣的开源工具是statecharts.org 上的 Yakindu Statechart Tools。它利用 Harel 状态图，从而提供分层和并行状态，并生成 C 和 C++（以及 Java）代码。它不使用库，而是遵循“纯代码”方法。该代码基本上应用了 switch-case 结构。代码生成器也可以定制。此外，该工具还提供了许多其他功能。
于 2015-04-24T07:53:08.683 回答
4
下面是一个使用消息队列作为事件的 Linux 有限状态机示例。事件被放入队列并按顺序处理。状态会根据每个事件发生的情况而变化。
这是具有以下状态的数据连接的示例：
- 未初始化
- 初始化
- 连接的
- MTU 已协商
- 已认证
我添加的一个额外功能是每个消息/事件的时间戳。事件处理程序将忽略太旧的事件（它们已过期）。这在现实世界中经常发生，您可能会意外地陷入某种状态。
这个例子在 Linux 上运行，使用下面的 Makefile 来编译它并使用它。
state_machine.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h> // sysconf()
#include <errno.h> // errno
#include <string.h> // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h> // For O_* constants
#include <sys/stat.h> // For mode constants
#include <mqueue.h>
#include <poll.h>
//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
ST_UNKNOWN = 0,
ST_UNINIT,
ST_INIT,
ST_CONNECTED,
ST_MTU_NEGOTIATED,
ST_AUTHENTICATED,
ST_ERROR,
ST_DONT_CHANGE,
ST_TERM,
} fsmState_t;
//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
EV_UNKNOWN = 0,
EV_INIT_SUCCESS,
EV_INIT_FAIL,
EV_MASTER_CMD_MSG,
EV_CONNECT_SUCCESS,
EV_CONNECT_FAIL,
EV_MTU_SUCCESS,
EV_MTU_FAIL,
EV_AUTH_SUCCESS,
EV_AUTH_FAIL,
EV_TX_SUCCESS,
EV_TX_FAIL,
EV_DISCONNECTED,
EV_DISCON_FAILED,
EV_LAST_ENTRY,
} fsmEvName_t;
typedef struct fsmEvent_type
{
fsmEvName_t name;
struct timeval genTime; // Time the event was generated.
// This allows us to see how old the event is.
} fsmEvent_t;
// Finite State Machine Data Members
typedef struct fsmData_type
{
int connectTries;
int MTUtries;
int authTries;
int txTries;
} fsmData_t;
// Each row of the state table
typedef struct stateTable_type {
fsmState_t st; // Current state
fsmEvName_t evName; // Got this event
int (*conditionfn)(void *); // If this condition func returns TRUE
fsmState_t nextState; // Change to this state and
void (*fn)(void *); // Run this function
} stateTable_t;
// Finite State Machine state structure
typedef struct fsm_type
{
const stateTable_t *pStateTable; // Pointer to state table
int numStates; // Number of entries in the table
fsmState_t currentState; // Current state
fsmEvent_t currentEvent; // Current event
fsmData_t *fsmData; // Pointer to the data attributes
mqd_t mqdes; // Message Queue descriptor
mqd_t master_cmd_mqdes; // Master command message queue
} fsm_t;
// Wildcard events and wildcard state
#define EV_ANY -1
#define ST_ANY -1
#define TRUE (1)
#define FALSE (0)
// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO (sysconf(_SC_MQ_PRIO_MAX) - 1)
static void addev (fsm_t *fsm, fsmEvName_t ev);
static void doNothing (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError (void *fsm) {addev(fsm, EV_ANY);}
static int currentlyLessThanMaxConnectTries (void *fsm) {
fsm_t *l = (fsm_t *)fsm;
return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int isMoreThanMaxConnectTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries (void *fsm) {return TRUE;}
static int isMoreThanMaxMTUtries (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries (void *fsm) {return TRUE;}
static int isMoreThanMaxAuthTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries (void *fsm) {return FALSE;}
static int isMoreThanMaxTXtries (void *fsm) {return TRUE;}
static int didNotSelfDisconnect (void *fsm) {return TRUE;}
static int waitForEvent (fsm_t *fsm);
static void runEvent (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);
// Global State Table
const stateTable_t GST[] = {
// Current state Got this event If this condition func returns TRUE Change to this state and Run this function
{ ST_UNINIT, EV_INIT_SUCCESS, NULL, ST_INIT, &doNothing },
{ ST_UNINIT, EV_INIT_FAIL, NULL, ST_UNINIT, &doInit },
{ ST_INIT, EV_MASTER_CMD_MSG, NULL, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_SUCCESS, NULL, ST_CONNECTED, &doMTU },
{ ST_INIT, EV_CONNECT_FAIL, ¤tlyLessThanMaxConnectTries, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_FAIL, &isMoreThanMaxConnectTries, ST_INIT, &reportFailConnect },
{ ST_CONNECTED, EV_MTU_SUCCESS, NULL, ST_MTU_NEGOTIATED, &doAuth },
{ ST_CONNECTED, EV_MTU_FAIL, ¤tlyLessThanMaxMTUtries, ST_CONNECTED, &doMTU },
{ ST_CONNECTED, EV_MTU_FAIL, &isMoreThanMaxMTUtries, ST_CONNECTED, &doDisconnect },
{ ST_CONNECTED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_MTU_NEGOTIATED, EV_AUTH_SUCCESS, NULL, ST_AUTHENTICATED, &doTransaction },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, ¤tyLessThanMaxAuthTries, ST_MTU_NEGOTIATED, &doAuth },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, &isMoreThanMaxAuthTries, ST_MTU_NEGOTIATED, &doDisconnect },
{ ST_MTU_NEGOTIATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_AUTHENTICATED, EV_TX_SUCCESS, NULL, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_TX_FAIL, ¤tlyLessThanMaxTXtries, ST_AUTHENTICATED, &doTransaction },
{ ST_AUTHENTICATED, EV_TX_FAIL, &isMoreThanMaxTXtries, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_ANY, EV_DISCON_FAILED, NULL, ST_DONT_CHANGE, &doDisconnect },
{ ST_ANY, EV_ANY, NULL, ST_UNINIT, &fsmError } // Wildcard state for errors
};
#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))
int main()
{
int ret = 0;
fsmData_t dataAttr;
dataAttr.connectTries = 0;
dataAttr.MTUtries = 0;
dataAttr.authTries = 0;
dataAttr.txTries = 0;
fsm_t lfsm;
memset(&lfsm, 0, sizeof(fsm_t));
lfsm.pStateTable = GST;
lfsm.numStates = GST_COUNT;
lfsm.currentState = ST_UNINIT;
lfsm.currentEvent.name = EV_ANY;
lfsm.fsmData = &dataAttr;
struct mq_attr attr;
attr.mq_maxmsg = 30;
attr.mq_msgsize = sizeof(fsmEvent_t);
// Dev info
//printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));
ret = mq_unlink("/abcmq");
if (ret == -1) {
fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
}
lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
if (lfsm.mqdes == (mqd_t)-1) {
fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
return -1;
}
doInit(&lfsm); // This will generate the first event
runStateMachine(&lfsm);
return 0;
}
static void runStateMachine(fsm_t *fsm)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
// Cycle through the state machine
while (fsm->currentState != ST_TERM) {
printf("current state [");
printState(fsm->currentState);
printf("]\n");
ret = waitForEvent(fsm);
if (ret == 0) {
printf("got event [");
printEvent(fsm->currentEvent.name);
printf("]\n");
runEvent(fsm);
}
sleep(2);
}
}
static int waitForEvent(fsm_t *fsm)
{
//const int numFds = 2;
const int numFds = 1;
struct pollfd fds[numFds];
int timeout_msecs = -1; // -1 is forever
int ret = 0;
int i = 0;
ssize_t num = 0;
fsmEvent_t newEv;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return -1;
}
fsm->currentEvent.name = EV_ANY;
fds[0].fd = fsm->mqdes;
fds[0].events = POLLIN;
//fds[1].fd = fsm->master_cmd_mqdes;
//fds[1].events = POLLIN;
ret = poll(fds, numFds, timeout_msecs);
if (ret > 0) {
// An event on one of the fds has occurred
for (i = 0; i < numFds; i++) {
if (fds[i].revents & POLLIN) {
// Data may be read on device number i
num = mq_receive(fds[i].fd, (void *)(&newEv),
sizeof(fsmEvent_t), NULL);
if (num == -1) {
fprintf(stderr, "Error on mq_receive(), errno[%d] "
"strerror[%s]\n", errno, strerror(errno));
return -1;
}
if (newEventIsValid(&newEv)) {
fsm->currentEvent = newEv;
} else {
return -1;
}
}
}
} else {
fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
ret, errno, strerror(errno));
return -1;
}
return 0;
}
static int newEventIsValid(fsmEvent_t *event)
{
if (event == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return FALSE;
}
printf("[%s]\n", __func__);
struct timeval now;
getTime(&now);
if ( (event->name < EV_LAST_ENTRY) &&
((now.tv_sec - event->genTime.tv_sec) < (60*5))
)
{
return TRUE;
} else {
return FALSE;
}
}
//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
int i;
int condRet = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
// Find a relevant entry for this state and event
for (i = 0; i < fsm->numStates; i++) {
// Look in the table for our current state or ST_ANY
if ( (fsm->pStateTable[i].st == fsm->currentState) ||
(fsm->pStateTable[i].st == ST_ANY)
)
{
// Is this the event we are looking for?
if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
(fsm->pStateTable[i].evName == EV_ANY)
)
{
if (fsm->pStateTable[i].conditionfn != NULL) {
condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
}
// See if there is a condition associated
// or we are not looking for any condition
//
if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
{
// Set the next state (if applicable)
if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
fsm->currentState = fsm->pStateTable[i].nextState;
printf("new state [");
printState(fsm->currentState);
printf("]\n");
}
// Call the state callback function
fsm->pStateTable[i].fn(fsm);
break;
}
}
}
}
}
//------------------------------------------------
// EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
if (time == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
int ret = gettimeofday(time, NULL);
if (ret != 0) {
fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
errno, strerror(errno));
memset(time, 0, sizeof(struct timeval));
}
}
static void addev (fsm_t *fsm, fsmEvName_t ev)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s] ev[%d]\n", __func__, ev);
if (ev == EV_ANY) {
// Don't generate a new event, just return...
return;
}
fsmEvent_t newev;
getTime(&(newev.genTime));
newev.name = ev;
ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
if (ret == -1) {
fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
__func__, errno, strerror(errno));
}
}
//------------------------------------------------
// end EVENT HANDLERS
//------------------------------------------------
void printState(fsmState_t st)
{
switch(st) {
case ST_UNKNOWN:
printf("ST_UNKNOWN");
break;
case ST_UNINIT:
printf("ST_UNINIT");
break;
case ST_INIT:
printf("ST_INIT");
break;
case ST_CONNECTED:
printf("ST_CONNECTED");
break;
case ST_MTU_NEGOTIATED:
printf("ST_MTU_NEGOTIATED");
break;
case ST_AUTHENTICATED:
printf("ST_AUTHENTICATED");
break;
case ST_ERROR:
printf("ST_ERROR");
break;
case ST_TERM:
printf("ST_TERM");
break;
default:
printf("unknown state");
break;
}
}
void printEvent(fsmEvName_t ev)
{
switch (ev) {
case EV_UNKNOWN:
printf("EV_UNKNOWN");
break;
case EV_INIT_SUCCESS:
printf("EV_INIT_SUCCESS");
break;
case EV_INIT_FAIL:
printf("EV_INIT_FAIL");
break;
case EV_MASTER_CMD_MSG:
printf("EV_MASTER_CMD_MSG");
break;
case EV_CONNECT_SUCCESS:
printf("EV_CONNECT_SUCCESS");
break;
case EV_CONNECT_FAIL:
printf("EV_CONNECT_FAIL");
break;
case EV_MTU_SUCCESS:
printf("EV_MTU_SUCCESS");
break;
case EV_MTU_FAIL:
printf("EV_MTU_FAIL");
break;
case EV_AUTH_SUCCESS:
printf("EV_AUTH_SUCCESS");
break;
case EV_AUTH_FAIL:
printf("EV_AUTH_FAIL");
break;
case EV_TX_SUCCESS:
printf("EV_TX_SUCCESS");
break;
case EV_TX_FAIL:
printf("EV_TX_FAIL");
break;
case EV_DISCONNECTED:
printf("EV_DISCONNECTED");
break;
case EV_LAST_ENTRY:
printf("EV_LAST_ENTRY");
break;
default:
printf("unknown event");
break;
}
}
Makefile
CXX = gcc
COMPFLAGS = -c -Wall -g
state_machine: state_machine.o
$(CXX) -lrt state_machine.o -o state_machine
state_machine.o: state_machine.c
$(CXX) $(COMPFLAGS) state_machine.c
clean:
rm state_machine state_machine.o
于 2019-04-15T14:31:06.993 回答
3
这么晚了（像往常一样），但扫描迄今为止的答案，我认为缺少一些重要的东西；
我在我自己的项目中发现，不为每个有效的状态/事件组合提供函数会非常有帮助。我确实喜欢有效地拥有状态/事件的 2D 表的想法。但我喜欢表格元素不仅仅是一个简单的函数指针。相反，我尝试组织我的设计，使其核心包含一堆简单的原子元素或动作。这样我就可以在我的状态/事件表的每个交集处列出那些简单的原子元素。这个想法是您不必定义大量的 N 平方（通常非常简单）函数。为什么会有这么容易出错、耗时、难写、难读的东西，你能说出它的名字吗？
我还包括一个可选的新状态，以及表中每个单元格的可选函数指针。函数指针用于那些您不想只触发原子操作列表的特殊情况。
当您可以表达许多不同的功能时，您就知道您做对了，只需编辑您的表格，无需编写新代码。
于 2009-11-23T01:38:54.417 回答
3
好吧，我觉得我的和其他人的有点不同。代码和数据的分离比我在其他答案中看到的要多一点。我真的阅读了写这个的理论，它实现了一个完整的正则语言（遗憾的是没有正则表达式）。厄尔曼、明斯基、乔姆斯基。不能说我全部理解，但我尽可能直接地从古代大师那里汲取灵感：通过他们的话。
我使用指向谓词的函数指针来确定转换到“是”状态或“否”状态。这有助于为您以更像汇编语言的方式编程的常规语言创建有限状态接受器。请不要被我愚蠢的名字选择推迟。'捷克' == '检查'。'grok' == [去黑客词典查一下]。
因此，对于每次迭代，czek 都会以当前字符作为参数调用一个谓词函数。如果谓词返回 true，则字符被消耗（指针前进）并且我们按照“y”转换来选择下一个状态。如果谓词返回 false，则字符不被消耗，我们遵循“n”转换。所以每条指令都是一个双向分支！我当时一定在读《梅尔的故事》。
这段代码直接来自我的 postscript 解释器，并在 comp.lang.c 上的研究员的指导下演变成现在的形式。由于 postscript 基本上没有语法（只需要平衡括号），因此像这样的常规语言接受器也可以用作解析器。
/* currentstr is set to the start of string by czek
and used by setrad (called by israd) to set currentrad
which is used by israddig to determine if the character
in question is valid for the specified radix
--
a little semantic checking in the syntax!
*/
char *currentstr;
int currentrad;
void setrad(void) {
char *end;
currentrad = strtol(currentstr, &end, 10);
if (*end != '#' /* just a sanity check,
the automaton should already have determined this */
|| currentrad > 36
|| currentrad < 2)
fatal("bad radix"); /* should probably be a simple syntaxerror */
}
/*
character classes
used as tests by automatons under control of czek
*/
char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ";
#define EQ(a,b) a==b
#define WITHIN(a,b) strchr(a,b)!=NULL
int israd (int c) {
if (EQ('#',c)) { setrad(); return true; }
return false;
}
int israddig(int c) {
return strchrnul(alpha,toupper(c))-alpha <= currentrad;
}
int isdot (int c) {return EQ('.',c);}
int ise (int c) {return WITHIN("eE",c);}
int issign (int c) {return WITHIN("+-",c);}
int isdel (int c) {return WITHIN("()<>[]{}/%",c);}
int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);}
#undef WITHIN
#undef EQ
/*
the automaton type
*/
typedef struct { int (*pred)(int); int y, n; } test;
/*
automaton to match a simple decimal number
*/
/* /^[+-]?[0-9]+$/ */
test fsm_dec[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, -1 },
/* 2*/ { isdigit, 2, -1 },
};
int acc_dec(int i) { return i==2; }
/*
automaton to match a radix number
*/
/* /^[0-9]+[#][a-Z0-9]+$/ */
test fsm_rad[] = {
/* 0*/ { isdigit, 1, -1 },
/* 1*/ { isdigit, 1, 2 },
/* 2*/ { israd, 3, -1 },
/* 3*/ { israddig, 4, -1 },
/* 4*/ { israddig, 4, -1 },
};
int acc_rad(int i) { return i==4; }
/*
automaton to match a real number
*/
/* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */
/* represents the merge of these (simpler) expressions
[+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
[+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)?
The complexity comes from ensuring at least one
digit in the integer or the fraction with optional
sign and optional optionally-signed exponent.
So passing isdot in state 3 means at least one integer digit has been found
but passing isdot in state 4 means we must find at least one fraction digit
via state 5 or the whole thing is a bust.
*/
test fsm_real[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, 4 },
/* 2*/ { isdigit, 2, 3 },
/* 3*/ { isdot, 6, 7 },
/* 4*/ { isdot, 5, -1 },
/* 5*/ { isdigit, 6, -1 },
/* 6*/ { isdigit, 6, 7 },
/* 7*/ { ise, 8, -1 },
/* 8*/ { issign, 9, 9 },
/* 9*/ { isdigit, 10, -1 },
/*10*/ { isdigit, 10, -1 },
};
int acc_real(int i) {
switch(i) {
case 2: /* integer */
case 6: /* real */
case 10: /* real with exponent */
return true;
}
return false;
}
/*
Helper function for grok.
Execute automaton against the buffer,
applying test to each character:
on success, consume character and follow 'y' transition.
on failure, do not consume but follow 'n' transition.
Call yes function to determine if the ending state
is considered an acceptable final state.
A transition to -1 represents rejection by the automaton
*/
int czek (char *s, test *fsm, int (*yes)(int)) {
int sta = 0;
currentstr = s;
while (sta!=-1 && *s) {
if (fsm[sta].pred((int)*s)) {
sta=fsm[sta].y;
s++;
} else {
sta=fsm[sta].n;
}
}
return yes(sta);
}
/*
Helper function for toke.
Interpret the contents of the buffer,
trying automatons to match number formats;
and falling through to a switch for special characters.
Any token consisting of all regular characters
that cannot be interpreted as a number is an executable name
*/
object grok (state *st, char *s, int ns,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
if (czek(s, fsm_dec, acc_dec)) {
long num;
num = strtol(s,NULL,10);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MIN) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_rad, acc_rad)) {
long ra,num;
ra = (int)strtol(s,NULL,10);
if (ra > 36 || ra < 2) {
error(st,limitcheck);
}
num = strtol(strchr(s,'#')+1, NULL, (int)ra);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MAX) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_real, acc_real)) {
double num;
num = strtod(s,NULL);
if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) {
error(st,limitcheck);
} else {
return consreal(num);
}
}
else switch(*s) {
case '(': {
int c, defer=1;
char *sp = s;
while (defer && (c=next(st,src)) != EOF ) {
switch(c) {
case '(': defer++; break;
case ')': defer--;
if (!defer) goto endstring;
break;
case '\\': c=next(st,src);
switch(c) {
case '\n': continue;
case 'a': c = '\a'; break;
case 'b': c = '\b'; break;
case 'f': c = '\f'; break;
case 'n': c = '\n'; break;
case 'r': c = '\r'; break;
case 't': c = '\t'; break;
case 'v': c = '\v'; break;
case '\'': case '\"':
case '(': case ')':
default: break;
}
}
if (sp-s>ns) error(st,limitcheck);
else *sp++ = c;
}
endstring: *sp=0;
return cvlit(consstring(st,s,sp-s));
}
case '<': {
int c;
char d, *x = "0123456789abcdef", *sp = s;
while (c=next(st,src), c!='>' && c!=EOF) {
if (isspace(c)) continue;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d = (char)c << 4;
while (isspace(c=next(st,src))) /*loop*/;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d |= (char)c;
if (sp-s>ns) error(st,limitcheck);
*sp++ = d;
}
*sp = 0;
return cvlit(consstring(st,s,sp-s));
}
case '{': {
object *a;
size_t na = 100;
size_t i;
object proc;
object fin;
fin = consname(st,"}");
(a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0);
for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) {
if (i == na-1)
(a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0);
}
proc = consarray(st,i);
{ size_t j;
for (j=0; j<i; j++) {
a_put(st, proc, j, a[j]);
}
}
free(a);
return proc;
}
case '/': {
s[1] = (char)next(st,src);
puff(st, s+2, ns-2, src, next, back);
if (s[1] == '/') {
push(consname(st,s+2));
opexec(st, op_cuts.load);
return pop();
}
return cvlit(consname(st,s+1));
}
default: return consname(st,s);
}
return null; /* should be unreachable */
}
/*
Helper function for toke.
Read into buffer any regular characters.
If we read one too many characters, put it back
unless it's whitespace.
*/
int puff (state *st, char *buf, int nbuf,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
int c;
char *s = buf;
while (isreg(c=next(st,src))) {
if (s-buf >= nbuf-1) return false;
*s++ = c;
}
*s = 0;
if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */
return true;
}
/*
Helper function for Stoken Ftoken.
Read a token from src using next and back.
Loop until having read a bona-fide non-whitespace non-comment character.
Call puff to read into buffer up to next delimiter or space.
Call grok to figure out what it is.
*/
#define NBUF MAXLINE
object toke (state *st, object *src,
int (*next)(state *, object *),
void (*back)(state *, int, object *)) {
char buf[NBUF] = "", *s=buf;
int c,sta = 1;
object o;
do {
c=next(st,src);
//if (c==EOF) return null;
if (c=='%') {
if (DUMPCOMMENTS) fputc(c, stdout);
do {
c=next(st,src);
if (DUMPCOMMENTS) fputc(c, stdout);
} while (c!='\n' && c!='\f' && c!=EOF);
}
} while (c!=EOF && isspace(c));
if (c==EOF) return null;
*s++ = c;
*s = 0;
if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back);
if (sta) {
o=grok(st,buf,NBUF-1,src,next,back);
return o;
} else {
return null;
}
}
于 2011-07-20T07:44:49.563 回答
3
boost.org 带有 2 种不同的状态图实现：
与往常一样，boost 会将您带入模板地狱。
第一个库用于性能更关键的状态机。第二个库为您提供了从 UML 状态图到代码的直接转换路径。
这是SO question，要求对两位作者的回答进行比较。
于 2012-01-15T12:27:38.243 回答
2
这一系列 Ars OpenForum 帖子介绍了一些复杂的控制逻辑，其中包括一个非常易于理解的 C 语言状态机实现。
于 2009-10-30T02:23:50.290 回答
2
您可以考虑UML-state-machine-in-c，它是 C 中的“轻量级”状态机框架。我编写了这个框架来支持有限状态机和分层状态机。与状态表或简单的 switch case 相比，框架方法更具可扩展性。它可以用于简单的有限状态机到复杂的分层状态机。
状态机由state_machine_t结构表示。它只包含两个成员“Event”和一个指向“state_t”的指针。
struct state_machine_t
{
uint32_t Event; //!< Pending Event for state machine
const state_t* State; //!< State of state machine.
};
state_machine_t必须是您的状态机结构的第一个成员。例如
struct user_state_machine
{
state_machine_t Machine; // Base state machine. Must be the first member of user derived state machine.
// User specific state machine members
uint32_t param1;
uint32_t param2;
...
};
state_t包含状态处理程序以及进入和退出操作的可选处理程序。
//! finite state structure
struct finite_state{
state_handler Handler; //!< State handler to handle event of the state
state_handler Entry; //!< Entry action for state
state_handler Exit; //!< Exit action for state.
};
如果框架配置为分层状态机，则state_t包含指向父状态和子状态的指针。
框架提供了一个 APIdispatch_event来将事件分派到状态机并switch_state触发状态转换。
有关如何实现分层状态机的更多详细信息，请参阅GitHub存储库。
代码示例，
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md https://github.com/kiishor/UML-State-Machine-in-C /blob/master/demo/simple_state_machine_enhanced/readme.md
于 2019-12-25T04:55:12.497 回答
1
你的问题很笼统，
这里有两篇可能有用的参考文章，
-
本文描述了一种为嵌入式系统实现状态机的简单方法。出于本文的目的，状态机被定义为一种可以处于少数状态之一的算法。状态是导致输入到输出以及输入到下一个状态的规定关系的条件。
精明的读者会很快注意到本文中描述的状态机是 Mealy 机。Mealy 机是一种状态机，其输出是当前状态和输入的函数，与 Moore 机相反，Moore 机的输出仅是状态的函数。- 用 C 和 C++ 编写状态机
我在本文中的重点是状态机基础知识和一些用 C 或 C++ 编写状态机的简单编程指南。我希望这些简单的技术可以变得更加普遍，以便您（和其他人）可以直接从源代码中轻松看到状态机结构。
- 用 C 和 C++ 编写状态机
于 2009-10-30T02:18:11.583 回答
1
我在 Java 和 Python 项目中成功使用了状态机编译器。
于 2009-12-20T18:41:14.073 回答
1
鉴于您暗示您可以使用 C++ 并因此使用 OO 代码，我建议评估“GoF”状态模式（GoF = 四人组，编写设计模式书的人，将设计模式带到了聚光灯下）。
它不是特别复杂，并且被广泛使用和讨论，因此很容易在线查看示例和解释。
以后维护您的代码的任何其他人也很可能会识别它。
如果担心效率，那么实际上值得进行基准测试以确保非 OO 方法更有效，因为许多因素会影响性能，而且它并不总是简单的 OO 不好，功能代码好。同样，如果内存使用对您来说是一个限制，那么再次值得做一些测试或计算，看看如果您使用状态模式，这是否真的会成为您的特定应用程序的问题。
正如 Craig 所建议的，以下是“Gof”状态模式的一些链接：
于 2011-12-16T15:46:49.990 回答
1
这是一篇有很多答案的旧帖子，但我想我应该将自己的方法添加到 C 中的有限状态机中。我制作了一个 Python 脚本来为任意数量的状态生成骨架 C 代码。该脚本记录在 GituHub 的FsmTemplateC
这个例子是基于我读过的其他方法。它不使用 goto 或 switch 语句，而是在指针矩阵（查找表）中具有转换函数。该代码依赖于一个大的多行初始化器宏和 C99 特性（指定初始化器和复合文字），所以如果你不喜欢这些东西，你可能不喜欢这种方法。
这是一个旋转门示例的 Python 脚本，它使用FsmTemplateC生成骨架 C 代码：
# dict parameter for generating FSM
fsm_param = {
# main FSM struct type string
'type': 'FsmTurnstile',
# struct type and name for passing data to state machine functions
# by pointer (these custom names are optional)
'fopts': {
'type': 'FsmTurnstileFopts',
'name': 'fopts'
},
# list of states
'states': ['locked', 'unlocked'],
# list of inputs (can be any length > 0)
'inputs': ['coin', 'push'],
# map inputs to commands (next desired state) using a transition table
# index of array corresponds to 'inputs' array
# for this example, index 0 is 'coin', index 1 is 'push'
'transitiontable': {
# current state | 'coin' | 'push' |
'locked': ['unlocked', ''],
'unlocked': [ '', 'locked']
}
}
# folder to contain generated code
folder = 'turnstile_example'
# function prefix
prefix = 'fsm_turnstile'
# generate FSM code
code = fsm.Fsm(fsm_param).genccode(folder, prefix)
生成的输出标头包含 typedef：
/* function options (EDIT) */
typedef struct FsmTurnstileFopts {
/* define your options struct here */
} FsmTurnstileFopts;
/* transition check */
typedef enum eFsmTurnstileCheck {
EFSM_TURNSTILE_TR_RETREAT,
EFSM_TURNSTILE_TR_ADVANCE,
EFSM_TURNSTILE_TR_CONTINUE,
EFSM_TURNSTILE_TR_BADINPUT
} eFsmTurnstileCheck;
/* states (enum) */
typedef enum eFsmTurnstileState {
EFSM_TURNSTILE_ST_LOCKED,
EFSM_TURNSTILE_ST_UNLOCKED,
EFSM_TURNSTILE_NUM_STATES
} eFsmTurnstileState;
/* inputs (enum) */
typedef enum eFsmTurnstileInput {
EFSM_TURNSTILE_IN_COIN,
EFSM_TURNSTILE_IN_PUSH,
EFSM_TURNSTILE_NUM_INPUTS,
EFSM_TURNSTILE_NOINPUT
} eFsmTurnstileInput;
/* finite state machine struct */
typedef struct FsmTurnstile {
eFsmTurnstileInput input;
eFsmTurnstileCheck check;
eFsmTurnstileState cur;
eFsmTurnstileState cmd;
eFsmTurnstileState **transition_table;
void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput);
} FsmTurnstile;
/* transition functions */
typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
- 枚举
eFsmTurnstileCheck用于确定转换是否被阻止EFSM_TURNSTILE_TR_RETREAT、允许继续进行EFSM_TURNSTILE_TR_ADVANCE，或者函数调用之前没有转换EFSM_TURNSTILE_TR_CONTINUE。 - enum
eFsmTurnstileState只是状态列表。 - enum
eFsmTurnstileInput只是输入列表。 FsmTurnstilestruct 是状态机的核心，具有转换检查、函数查找表、当前状态、命令状态以及运行机器的主要函数的别名。- 每个函数指针（别名）
FsmTurnstile只能从结构中调用，并且必须将其第一个输入作为指向自身的指针，以保持持久状态、面向对象的风格。
现在对于标题中的函数声明：
/* fsm declarations */
void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input);
函数名称的格式为{prefix}_{from}_{to}，其中{from}是前一个（当前）状态，{to}是下一个状态。请注意，如果转换表不允许某些转换，则将设置 NULL 指针而不是函数指针。最后，魔术发生在宏上。在这里，我们构建转换表（状态枚举矩阵）和状态转换函数查找表（函数指针矩阵）：
/* creation macro */
#define FSM_TURNSTILE_CREATE() \
{ \
.input = EFSM_TURNSTILE_NOINPUT, \
.check = EFSM_TURNSTILE_TR_CONTINUE, \
.cur = EFSM_TURNSTILE_ST_LOCKED, \
.cmd = EFSM_TURNSTILE_ST_LOCKED, \
.transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \
(eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
EFSM_TURNSTILE_ST_UNLOCKED, \
EFSM_TURNSTILE_ST_LOCKED \
}, \
(eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
EFSM_TURNSTILE_ST_UNLOCKED, \
EFSM_TURNSTILE_ST_LOCKED \
} \
}, \
.state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \
(pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
fsm_turnstile_locked_locked, \
fsm_turnstile_locked_unlocked \
}, \
(pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
fsm_turnstile_unlocked_locked, \
fsm_turnstile_unlocked_unlocked \
} \
}, \
.run = fsm_turnstile_run \
}
创建 FSM 时，FSM_EXAMPLE_CREATE()必须使用宏。
现在，在源代码中，上面声明的每个状态转换函数都应该被填充。该FsmTurnstileFopts结构可用于向/从状态机传递数据。每个转换都必须设置fsm->check为等于以EFSM_EXAMPLE_TR_RETREAT阻止它转换或EFSM_EXAMPLE_TR_ADVANCE允许它转换到命令状态。可以在 (FsmTemplateC)[ https://github.com/ChisholmKyle/FsmTemplateC]找到一个工作示例。
这是代码中非常简单的实际用法：
/* create fsm */
FsmTurnstile fsm = FSM_TURNSTILE_CREATE();
/* create fopts */
FsmTurnstileFopts fopts = {
.msg = ""
};
/* initialize input */
eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT;
/* main loop */
for (;;) {
/* wait for timer signal, inputs, interrupts, whatever */
/* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */
/* run state machine */
my_fsm.run(&my_fsm, &my_fopts, my_input);
}
所有这些标题业务和所有这些功能只是为了拥有一个简单而快速的界面，在我看来是值得的。
于 2015-07-27T23:51:30.653 回答
0
您可以使用开源库OpenFST。
OpenFst 是一个用于构建、组合、优化和搜索加权有限状态传感器 (FST) 的库。加权有限状态换能器是自动机，其中每个转换都有一个输入标签、一个输出标签和一个权重。更熟悉的有限状态接受器被表示为一个转换器，每个转换的输入和输出标签都相等。有限状态接受器用于表示字符串集合（特别是常规或有理集合）；有限状态换能器用于表示字符串对之间的二元关系（特别是有理换能）。权重可用于表示进行特定转换的成本。
于 2012-01-23T21:44:19.610 回答
0
void (* StateController)(void);
void state1(void);
void state2(void);
void main()
{
StateController=&state1;
while(1)
{
(* StateController)();
}
}
void state1(void)
{
//do something in state1
StateController=&state2;
}
void state2(void)
{
//do something in state2
//Keep changing function direction based on state transition
StateController=&state1;
}
于 2016-01-30T09:36:39.883 回答
0
我个人将自引用结构与指针数组结合使用。不久前我在github上上传了一个教程，链接：
https://github.com/mmelchger/polling_state_machine_c
注意：我确实意识到这个线程已经很老了，但我希望得到关于状态机设计的输入和想法，并能够为 C 中可能的状态机设计提供一个示例。
于 2016-12-13T09:55:03.997 回答
-1
这是一种使用宏的状态机方法，这样每个函数都可以有自己的一组状态：https ://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code -在
它的标题是“模拟多任务”，但这不是唯一的用途。
此方法使用回调来拾取它停止的每个函数。每个函数都包含每个函数独有的状态列表。中央“空闲循环”用于运行状态机。“空闲循环”不知道状态机是如何工作的，“知道要做什么”的是各个功能。为了编写函数代码，只需创建一个状态列表并使用宏来“暂停”和“恢复”。当我为 Nexus 7000 交换机编写收发器库时，我在 Cisco 使用了这些宏。
于 2020-03-21T12:33:35.370 回答