用一个协程实现一个有限状态机
我正在研究如何实现FSM，这导致了我第一次遇到协程。
我看到了几个例子（这里，这里和这里）提示一个状态机可以通过一个协程来实现。 但是，我注意到所有这些机器的共同之处在于，不包括周期，它们是树 - 也就是说，从起始节点到所有其他节点都有一条路径（不包括周期） - 并且很好地映射到分层控制流由嵌套if s提供。 我试图建模的状态机至少有一个状态，从起始节点到它有多条路径（如果循环被消除，它是一个有向无环图）。 我无法想象什么样的控制流程（除了goto s）能够实现这一点，或者如果可能的话。
或者，我可以使用单独的协程来处理每个状态并产生某种调度协程。 但是，在此设置中，我没有看到使用协同程序比常规功能有什么特别的好处。
这是一个简单的状态机，我在建模时遇到了麻烦：
A --'a'--> B
A --'b'--> C
B --'a'--> C
B --'b'--> A
C --'a'--> A
C --'b'--> B
到目前为止，这是我所拥有的。 最终的实现将使用Boost在C ++中，但我使用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)
这个协程可以修正以正确模拟状态机吗？ 还是我必须采取其他方式呢？
我将显式地为状态机建模：
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;
}
从理论上讲，每个有限状态机都可以用一个协程来实现，只有以下一种结构：
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)
上一篇: Implementing a finite state machine with a single coroutine