C状态机devise

我正在用混合C和C ++编写一个小项目。 我正在build立一个小型的国家机器在我工作线程的中心。

我想知道你们的专家是否会分享你们的状态机devise技术。

注意：我主要是经过testing和实施的技术。

更新：基于所有收集的伟大意见，我已经解决了这个架构：

Answer 1

我以前devise的状态机（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) { ... }; 

所有这些函数都被写成不带variables并返回状态机的新状态。 在这个例子中，全局variables用来在需要的时候将任何信息传递给状态函数。

使用全局variables并不像听起来那么糟糕，因为FSM通常被locking在单个编译单元中，而且所有的variables对于那个单元都是静态的（这就是为什么我在上面用“全局variables”引用引号的原因 – 它们在FSM，而不是真正的全球）。 和所有的全局variables一样，它需要关心。

转换数组然后定义了所有可能的转换和为这些转换调用的函数（包括最后一个）。

 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作为通配符，允许事件调用一个函数，而不pipe当前状态如何。 EV_ANY也同样起作用，允许在特定状态下的任何事件调用一个函数。

它也可以保证，如果你到达了transitions数组的末尾，你会得到一个错误，说明你的FSM没有被正确构build（通过使用ST_ANY/EV_ANY组合。

我在许多通信项目上使用了类似的代码，例如早期实现embedded式系统的通信协议栈和协议。 最大的好处是简单，相对容易地改变转换数组。

毫无疑问，现在可能会有更高层次的抽象，但我怀疑他们都会归结为这种结构。

---

而且，正如ldog在评论中指出的那样，您可以通过将结构指针传递给所有函数（并在事件循环中使用它）来完全避免全局variables。 这将允许多个状态机并排运行而不受干扰。

只需创build一个结构types来保存特定于计算机的数据（最低状态）并使用它来代替全局variables。

我很less这么做的原因很简单，因为我写的大多数状态机都是单例types（例如一次性，在进程启动，configuration文件读取等），不需要运行多个实例。 但是如果你需要运行一个以上的话，它是有价值的。

Answer 2

其他答案是好的，但是当状态机非常简单的时候，我使用了一个非常“轻量级”的实现，如下所示：

 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 ... */ } } 

当状态机足够简单，以至于函数指针和状态转换表的方法是矫枉过正的时候，我会使用它。 这通常用于逐字符或逐字parsing。

Answer 3

请原谅我打破计算机科学中的每一条规则，但是状态机是less数几个（我可以只计算两个）的地方之一， goto语句不仅更有效率，而且使代码更清晰，更易于阅读。 因为goto语句是基于标签的，所以你可以命名你的状态，而不必跟踪一堆数字或者使用一个枚举。 这也使得代码更清洁，因为你不需要额外的函数指针或巨大的开关语句和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语句，则必须小心谨慎，因为在此过程中拍摄自己的脚很容易。

Answer 4

您可以考虑使用State Machine Compiler http://smc.sourceforge.net/

这个华丽的开源实用程序以简单的语言接受状态机的描述，并将其编译为十几种语言中的任何一种 – 包括C和C ++。 该实用程序本身是用Java编写的，可以作为构build的一部分。

这样做的原因，而不是使用GoF状态模式或任何其他方法手动编码，是一旦你的状态机被表示为代码，底层结构往往消失在需要生成的样板的权重，以支持它。 使用这种方法可以让您很好地分离关注点，并保持状态机的结构“可见”。 自动生成的代码将进入您不需要触摸的模块，以便您可以返回并摆脱状态机的结构，而不会影响您编写的支持代码。

对不起，我过于热心了，无疑把大家都关了。 但它是一个顶尖的实用程序，也有很好的文档。

Answer 5

请务必检查在C / C ++用户日志中的文章Miro Samek（博客State Space ，网站State Machines＆Tools ）的工作。

该网站包含完整的（C / C ++）实现，包括状态机框架（QP框架） ， 事件处理程序（QEP） ， 基本build模工具（QM）和跟踪工具（QSpy）的开源和商业许可证允许绘制状态机，创build代码并debugging它们。

本书包含了关于实现的原因和如何使用它的广泛的解释，也是深入了解分级和有限状态机基本原理的重要资料。

该网站还包含几个板卡支持包的链接，以便使用embedded式平台的软件。

Answer 6

我做了类似于paxdiablo描述的东西，而不是一个状态/事件转换数组，我设置了一个二维的函数指针数组，事件值作为一个轴的索引，当前状态值为另一个。 然后，我只是调用state = state_table[event][state](params) ，正确的事情发生。 表示无效状态/事件组合的单元格当然会得到一个指向这样的函数的指针。

显然，只有当状态和事件值都是连续的范围，并且从0开始或足够接近时，这才起作用。

Answer 7

Stefan Heinzmann在他的文章中给出了一个非常好的基于模板的C ++状态机“框架”。

由于本文没有链接到完整的代码下载，所以我冒昧地将代码粘贴到一个项目中并检查出来。 下面的东西进行了testing，包括less量，但非常明显的缺失件。

这里的主要创新是编译器生成非常高效的代码。 空入/退出行动没有成本。 非空的进入/退出动作被内联。 编译器也在validation状态图的完整性。 缺less操作会生成链接错误。 唯一没有被捕获的是缺less的Top::init 。

这是Miro Samek实现的一个非常好的select，如果你可以没有缺失的东西，那么这个实现远不是一个完整的UML状态图实现，尽pipe它正确地实现了UML语义，而Samek的devise代码不能处理退出/转换/input操作按正确的顺序。

如果此代码适用于您需要执行的操作，并且您的系统具有体面的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 

testing代码如下。

 #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) 

Answer 8

我喜欢的状态机（至less是程序控制）的技术是使用函数指针。 每个状态都由不同的function表示。 该函数接受一个input符号并返回下一个状态的函数指针。 中央调度循环监视器接受下一个input，将其馈送到当前状态，并处理结果。

键入它有点奇怪，因为C没有办法指示types的函数指针返回自己，所以状态函数返回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); } } 

然后，您的各个状态function可以切换其input来处理并返回适当的值。

Answer 9

最简单的情况

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

点：国家是私人的，不仅是编制单位，而且是事件处理。 特殊情况可以使用任何必要的构造与主开关分开处理。

更复杂的情况

当开关比满屏的屏幕大一些时，把它分成处理每个状态的函数，用状态表直接查找函数。 状态对于事件处理程序仍然是私有的。 状态处理函数返回下一个状态。 如果需要，一些事件在主事件处理程序中仍然可以得到特殊处理。 我喜欢抛出状态进入和退出的伪事件，也许状态机启动：

 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）括号）时显式抛弃下一个状态。 即使编译者默默地接受了这个省略，我也喜欢这样做。 它告诉读者代码：“是的，我确实是在不使用返回值的情况下调用函数”，这可能会阻止静态分析工具发出警告。 这可能是特别的，因为我不记得有人看到这样做。

要点：添加一点复杂性（检查下一个状态是否与当前状态不同），可以避免重复的代码，因为状态处理函数可以享受进入和离开状态时发生的伪事件。 请记住，在处理伪事件时不能更改状态，因为状态处理程序的结果在这些事件之后被丢弃。 你当然可以select修改行为。

状态处理程序看起来像这样：

 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行），把每个状态处理程序放在一个单独的文件中。 当每个状态处理程序比两个屏幕更长时，将每个事件拆分成一个单独的函数，类似于状态开关被拆分的方式。 您可以通过多种方式与国家分开或通过使用公用表格或合并各种scheme。 其中一些已被其他人覆盖。 对表格进行sorting，如果速度是要求，则使用二进制search。

generics编程

我希望预处理器能够处理诸如sorting表甚至从描述中生成状态机等问题，从而允许您“编写关于程序的程序”。 我相信这是Boost人正在利用C ++模板，但是我觉得这个语法是神秘的。

二维表

过去我使用过状态/事件表，但是我不得不说，对于最简单的情况，我不认为它们是必需的，我更喜欢switch语句的清晰性和可读性，即使它延伸过一个屏幕。 对于更复杂的情况，表格很快就会像其他人注意到的那样失控。 我在这里提出的习惯用法，可以让你在不需要维护内存消耗表（即使可能是程序存储器）的情况下添加一些事件和状态。

放弃

特殊需求可能会使这些习语变得不那么有用，但是我发现它们是非常清楚和可维护的。

Answer 10

非常未经testing，但有趣的代码，现在在一个比我原来的答案更精致的版本; 最新版本可以在mercurial.intuxication.orgfind：

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 

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

Answer 11

另一个有趣的开源工具是statecharts.org上的Yakindu Statechart Tools 。 它利用Harel状态图，从而提供分层和并行状态，并生成C和C ++（以及Java）代码。 它不使用库，但遵循“明码”的方法。 代码基本上应用了开关结构。 代码生成器也可以定制。 另外该工具还提供了许多其他function。

Answer 12

即将到来（像往常一样），但扫描答案的date，我认为重要的东西缺失;

我在自己的项目中发现，对于每个有效的状态/事件组合都没有函数是非常有帮助的。 我确实喜欢有一个2D状态/事件表的想法。 But I like the table elements to be more than a simple function pointer. Instead I try to organize my design so at it's heart it comprises a bunch of simple atomic elements or actions. That way I can list those simple atomic elements at each intersection of my state/event table. The idea is that you don't have to define a mass of N squared (typically very simple) functions. Why have something so error-prone, time consuming, hard to write, hard to read, you name it ?

I also include an optional new state, and an optional function pointer for each cell in the table. The function pointer is there for those exceptional cases where you don't want to just fire off a list of atomic actions.

You know you are doing it right when you can express a lot of different functionality, just by editing your table, with no new code to write.

Answer 13

Alrght, I think mine's just a little different from everybody else's. A little more separation of code and data than I see in the other answers. I really read up on the theory to write this, which implements a full Regular-language (without regular expressions, sadly). Ullman, Minsky, Chomsky. Can't say I understood it all, but I've drawn from the old masters as directly as possible: through their words.

I use a function pointer to a predicate that determines the transition to a 'yes' state or a 'no' state. This facilitates the creation of a finite state acceptor for a regular language that you program in a more assembly-language-like manner. Please don't be put-off by my silly name choices. 'czek' == 'check'. 'grok' == [go look it up in the Hacker Dictionary].

So for each iteration, czek calls a predicate function with the current character as argument. If the predicate returns true, the character is consumed (the pointer advanced) and we follow the 'y' transition to select the next state. If the predicate returns false, the character is NOT consumed and we follow the 'n' transition. So every instruction is a two-way branch! I must have been reading The Story of Mel at the time.

This code comes straight from my postscript interpreter , and evolved into its current form with much guidance from the fellows on comp.lang.c. Since postscript basically has no syntax (only requiring balanced brackets), a Regular Language Accepter like this functions as the parser as well.

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

Answer 14

boost.org comes with 2 different state chart implementations:

• Meta State Machine
• Statechart

As always, boost will beam you into template hell.

The first library is for more performance-critical state machines. The second library gives you a direct transition path from a UML Statechart to code.

Here's the SO question asking for a comparison between the two where both of the authors respond.

Answer 15

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.

Answer 16

Saw this somewhere

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

Answer 17

Given that you imply you can use C++ and hence OO code, I would suggest evaluating the 'GoF'state pattern (GoF = Gang of Four, the guys who wrote the design patterns book which brought design patterns into the limelight).

It is not particularly complex and it is widely used and discussed so it is easy to see examples and explanations on line.

It will also quite likely be recognizable by anyone else maintaining your code at a later date.

If efficiency is the worry, it would be worth actually benchmarking to make sure that a non OO approach is more efficient as lots of factors affect performance and it is not always simply OO bad, functional code good. Similarly, if memory usage is a constraint for you it is again worth doing some tests or calculations to see if this will actually be an issue for your particular application if you use the state pattern.

The following are some links to the 'Gof' state pattern, as Craig suggests:

• http://en.wikipedia.org/wiki/State_pattern
• http://www.vincehuston.org/dp/state.html

Answer 18

I really liked paxdiable's answer and decided to implement all the missing features for my application like guard variables and state machine specific data.

I uploaded my implementation to this site to share with the community. It has been tested using IAR Embedded Workbench for ARM.

https://sourceforge.net/projects/compactfsm/

Answer 19

Your question is quite generic,
Here are two reference articles that might be useful,

1. Embedded State Machine Implementation

   This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
   A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

   • Coding State Machines in C and C++
     

     My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

Answer 20

I have used State Machine Compiler in Java and Python projects to with success.

Answer 21

This is an old post with lots of answers, but I thought I'd add my own approach to the finite state machine in C. I made a Python script to produce the skeleton C code for any number of states. That script is documented on GituHub at FsmTemplateC

This example is based on other approaches I've read about. It doesn't use goto or switch statements but instead has transition functions in a pointer matrix (look-up table). The code relies on a big multi-line initializer macro and C99 features (designated initializers and compound literals) so if you don't like these things, you might not like this approach.

Here is a Python script of a turnstile example which generates skeleton C-code using FsmTemplateC :

 # 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) 

The generated output header contains the typedefs:

 /* 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 *); 

• enum eFsmTurnstileCheck is used to determine whether a transition was blocked with EFSM_TURNSTILE_TR_RETREAT , allowed to progress with EFSM_TURNSTILE_TR_ADVANCE , or the function call was not preceded by a transition with EFSM_TURNSTILE_TR_CONTINUE .
• enum eFsmTurnstileState is simply the list of states.
• enum eFsmTurnstileInput is simply the list of inputs.
• The FsmTurnstile struct is the heart of the state machine with the transition check, function lookup table, current state, commanded state, and an alias to the primary function that runs the machine.
• Every function pointer (alias) in FsmTurnstile should only be called from the struct and has to have its first input as a pointer to itself so as to maintain a persistent state, object-oriented style.

Now for the function declarations in the header:

 /* 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); 

Function names are in the format {prefix}_{from}_{to} , where {from} is the previous (current) state and {to} is the next state. Note that if the transition table does not allow for certain transitions, a NULL pointer instead of a function pointer will be set. Finally, the magic happens with a macro. Here we build the transition table (matrix of state enums) and the state transition functions look up table (a matrix of function pointers):

 /* 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 \ } 

When creating the FSM, the macro FSM_EXAMPLE_CREATE() has to be used.

Now, in the source code every state transition function declared above should be populated. The FsmTurnstileFopts struct can be used to pass data to/from the state machine. Every transition must set fsm->check to be equal to either EFSM_EXAMPLE_TR_RETREAT to block it from transitioning or EFSM_EXAMPLE_TR_ADVANCE to allow it to transition to the commanded state. A working example can be found at (FsmTemplateC)[ https://github.com/ChisholmKyle/FsmTemplateC%5D .

Here is the very simple actual usage in your code:

 /* 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); } 

All that header business and all those functions just to have a simple and fast interface is worth it in my mind.

Answer 22

You could use the open source library OpenFST .

OpenFst is a library for constructing, combining, optimizing, and searching weighted finite-state transducers (FSTs). Weighted finite-state transducers are automata where each transition has an input label, an output label, and a weight. The more familiar finite-state acceptor is represented as a transducer with each transition's input and output label equal. Finite-state acceptors are used to represent sets of strings (specifically, regular or rational sets); finite-state transducers are used to represent binary relations between pairs of strings (specifically, rational transductions). The weights can be used to represent the cost of taking a particular transition.

Answer 23

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

Answer 24

I personally use self referencing structs in combination with pointer arrays. I uploaded a tutorial on github a while back, link:

https://github.com/mmelchger/polling_state_machine_c

Note: I do realise that this thread is quite old, but I hope to get input and thoughts on the design of the state-machine as well as being able to provide an example for a possible state-machine design in C.