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

Question

我正在寻找实现FSM的方法,这导致我第一次遇到协同程序.

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

或者,我可以使用单独的协程来处理每个状态并屈服于某种调度程序协程.但是,我认为在此设置中使用协同程序而不是常规函数没有任何特别的好处.

这是一个我在建模时遇到问题的简单状态机:

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)

可以修复此协程以正确建模状态机吗？或者我必须采取其他方式吗？

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 A\n");
        yield(c->state, 1);
        if(input == 'a') goto B;
        if(input == 'b') goto C;
B:
        printf("Entered state B\n");
        yield(c->state, 1);
        if(input == 'a') goto C;
        if(input == 'b') goto A;
C:
        printf("Entered state C\n");
        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;
}