用单个协程实现有限状态机

Question

我正在寻找实现FSM的方法，这导致了我第一次遇到协程。

我看到了几个例子(这里、这里和这里)，这些例子暗示状态机可以由单个协程实现。然而，我注意到所有这些机器的共同点是，除了循环，它们都是树——也就是说，从开始节点到其他每个节点都有一条路径(不包括循环)——这很好地映射到嵌套ifs提供的分层控制流。我试图建模的状态机至少有一个状态，从起始节点到它有不止一条路径(如果消除了循环，它是一个有向无循环图)。我无法想象什么样的控制流(除了gotos)可以实现这一点，或者这是否可能。

或者，我可以使用一个单独的协程来处理每个状态，并向某种调度器协程屈服。然而，在这个设置中，我看不出使用协程而不是常规函数有什么特别的好处。

这里有一个简单的状态机，我在建模时遇到了问题：

A --'a'--> B
A --'b'--> C
B --'a'--> C
B --'b'--> A
C --'a'--> A
C --'b'--> B

这就是我目前所拥有的。最后的实现将在C++中使用Boost，但我使用Python进行原型设计。

#!/usr/bin/python3
def StateMachine():
while True:
print("  Entered state A")
input = (yield)
if input == "a":
print("  Entered state B")
input = (yield)
if input == "a":
# How to enter state C from here?
pass
elif input == "b":
continue
elif input == "b":
print("  Entered state C")
input = (yield)
if input == "b":
continue
elif input == "a":
# How to enter state B from here?
pass
if __name__ == "__main__":
sm = StateMachine()
sm.__next__()
while True:
for line in input():
sm.send(line)

这个协程可以被修复以正确地对状态机建模吗？还是我必须采取其他方式？

Answer 1

我会显式地为状态机建模：

def StateMachine():
state = 'A'
while True:
print(state)
input = (yield)
if state == 'A':
if input == 'a':
state = 'B'
elif input == 'b':
state = 'C'
else:
break
elif state == 'B':
if input == 'a':
state = 'C'
elif input == 'b':
state = 'A'
else:
break
elif state == 'C':
if input == 'a':
state = 'A'
elif input == 'b':
state = 'B'
else:
break
else:
break

这应该使用嵌套的switch语句或状态转换表非常巧妙地转换为C++。

如果您更喜欢隐式模型，则需要一种方法来处理状态机中的循环。在C或C++中，这可能最终成为goto。我不推荐这种方法，但如果你对它比显式状态更满意，下面是它可能看起来的样子：

#include <stdio.h>
#define start(state) switch(state) { case 0:;
#define finish default:;}
#define yield(state, value) do { state = __LINE__; return (value); case __LINE__:; } while(0)
struct coroutine {
int state;
};
int
run(struct coroutine *c, char input)
{
start(c->state)
{
A:
printf("Entered state An");
yield(c->state, 1);
if(input == 'a') goto B;
if(input == 'b') goto C;
B:
printf("Entered state Bn");
yield(c->state, 1);
if(input == 'a') goto C;
if(input == 'b') goto A;
C:
printf("Entered state Cn");
yield(c->state, 1);
if(input == 'a') goto A;
if(input == 'b') goto B;
} finish;
return 0;
}
int
main(void)
{
int a;
struct coroutine c = {0};
while((a = getchar()) != EOF && run(&c, a));
return 0;
}

Answer 2

理论上，每个有限状态机都可以用一个只有以下结构之一的协程来实现：

辅助变量的

• 检验
• goto语句
• 循环的多级出口

当然，if-then-else和while结构被认为是可用的。另一方面，只有单级出口的情况下，这种实现并不总是可行的。

因此，在没有状态变量和goto的情况下，编写了具体的示例，如下所示：

#!/usr/bin/python3 
# Python doesn't support multilevel exits, so try/except can be used instead.
# However, for this FSM, single-level exits are sufficient.  
def StateMachine():
while True:
while True:
print("  Entered state A")
input = (yield)
if input == "a":
print("  Entered state B")
input = (yield)
if input == "a": 
break
elif input == "b": 
pass
elif input == "b": 
break    
while True:
print("  Entered state C")
input = (yield)
if input == "a": 
break
elif input == "b": 
print("  Entered state B")
input = (yield)
if input == "a": 
pass
elif input == "b": 
break
if __name__=="__main__":
sm = StateMachine()
sm.__next__()
while True:
for line in input():
sm.send(line)