21

这个问题可能听起来陈词滥调，但我在这里遇到了情况。

我正在尝试实现一个有限状态自动机来解析 C 中的某个字符串。当我开始编写代码时，我意识到如果我使用标签来标记不同的状态并使用 goto 从一个状态跳转到另一个视情况而定。

在这种情况下，使用标准中断和标志变量非常麻烦，并且难以跟踪状态。

什么方法更好？最重要的是，我担心这会给我的老板留下不好的印象，因为我正在实习。

4

9 回答 9

37

本质上没有错goto。它们经常被认为是“禁忌”的原因是因为一些程序员（通常来自汇编世界）使用它们来创建几乎不可能理解的“意大利面条”代码。如果您可以在使用goto语句的同时保持代码干净、可读且无错误，那么您将获得更大的权力。

为每个状态使用goto语句和一段代码绝对是编写状态机的一种方式。另一种方法是创建一个将保存当前状态的变量，并使用 switch 语句（或类似语句）根据状态变量的值选择要执行的代码块。请参阅 Aidan Cully 的回答，了解使用第二种方法的良好模板。

实际上，这两种方法非常相似。如果您使用状态变量方法编写状态机并对其进行编译，则生成的程序集可能非常类似于使用该goto方法编写的代码（取决于您的编译器的优化级别）。该goto方法可以看作是从状态变量方法中优化掉额外的变量和循环。您使用哪种方法是个人选择的问题，只要您正在编写工作、可读的代码，我希望您的老板不会认为您使用一种方法与另一种方法有什么不同。

如果您将此代码添加到已经包含状态机的现有代码库中，我建议您遵循已经在使用的任何约定。

于 2010-06-23T22:03:47.190 回答
19

使用 agoto来实现状态机通常很有意义。如果你真的很担心使用 goto，一个合理的选择通常是有一个state你修改的变量，以及一个switch基于它的语句：

typedef enum {s0,s1,s2,s3,s4,...,sn,sexit} state;

state nextstate;
int done = 0;

nextstate = s0;  /* set up to start with the first state */
while(!done)
   switch(nextstate)
      {
         case s0:
            nextstate = do_state_0();
            break;
         case s1:
            nextstate = do_state_1();
            break;
         case s2:
            nextstate = do_state_2();
            break;
         case s3:
             .
             .
             .
             .
         case sn:
            nextstate = do_state_n();
            break;
         case sexit:
            done = TRUE;
            break;
         default:
            /*  some sort of unknown state */
            break;
      }
于 2010-06-23T21:42:31.627 回答
15

如果我想给老板留下好印象，我会使用像Ragel这样的 FSM 生成器。

这种方法的主要好处是您可以在更高的抽象层次上描述您的状态机，而无需担心是使用 goto 还是 switch。更不用说在 Ragel 的特定情况下，您可以自动获得 FSM 的漂亮图表，在任何点插入动作，自动最小化状态数量和各种其他好处。我有没有提到生成的 FSM 也非常快？

缺点是它们更难调试（自动可视化在这里有很大帮助）并且您需要学习一种新工具（如果您有一台简单的机器并且您不太可能经常编写机器，这可能不值得。 )

于 2010-06-23T21:39:52.237 回答
10

我会使用一个变量来跟踪您所处的状态，并使用一个开关来处理它们：

fsm_ctx_t ctx = ...;
state_t state = INITIAL_STATE;

while (state != DONE)
{
    switch (state)
    {
    case INITIAL_STATE:
    case SOME_STATE:
        state = handle_some_state(ctx)
        break;

    case OTHER_STATE:
        state = handle_other_state(ctx);
        break;
    }
}
于 2010-06-23T21:41:53.443 回答
8

Goto 不一定是邪恶的，我必须强烈反对 Denis，是的 goto 在大多数情况下可能是一个坏主意，但有一些用途。goto 最大的恐惧是所谓的“spagetti-code”，即无法追踪的代码路径。如果您可以避免这种情况，并且始终清楚代码的行为方式并且您不使用 goto 跳出函数，那么 goto 就没有什么可反对的了。请谨慎使用它，如果您想使用它，请真正评估情况并找到更好的解决方案。如果您无法做到这一点，可以使用 goto。

于 2010-06-23T21:43:58.053 回答
8

避免goto，除非添加的复杂性（以避免）更加混乱。

在实际工程问题中，goto 的使用空间非常有限。学者和非工程师在使用goto. 也就是说，如果您将自己描绘成一个实施角落，其中很多goto是唯一的出路，请重新考虑解决方案。

正确工作的解决方案通常是主要目标。使其正确和可维护（通过最小化复杂性）具有许多生命周期的好处。先让它起作用，然后逐渐清理它，最好是通过简化和去除丑陋。

于 2010-06-23T21:47:50.403 回答
4

我不知道您的具体代码，但是否有这样的原因：

typedef enum {
    STATE1, STATE2, STATE3
} myState_e;

void myFsm(void)
{
    myState_e State = STATE1;

    while(1)
    {
        switch(State)
        {
            case STATE1:
                State = STATE2;
                break;
            case STATE2:
                State = STATE3;
                break;
            case STATE3:
                State = STATE1;
                break;
        }
    }
}

不适合你吗？它不使用goto，并且相对容易理解。

编辑：所有这些State =片段都违反了 DRY，所以我可能会做类似的事情：

typedef int (*myStateFn_t)(int OldState);

int myStateFn_Reset(int OldState, void *ObjP);
int myStateFn_Start(int OldState, void *ObjP);
int myStateFn_Process(int OldState, void *ObjP);

myStateFn_t myStateFns[] = {
#define MY_STATE_RESET 0
   myStateFn_Reset,
#define MY_STATE_START 1
   myStateFn_Start,
#define MY_STATE_PROCESS 2
   myStateFn_Process
}

int myStateFn_Reset(int OldState, void *ObjP)
{
    return shouldStart(ObjP) ? MY_STATE_START : MY_STATE_RESET;
}

int myStateFn_Start(int OldState, void *ObjP)
{
    resetState(ObjP);
    return MY_STATE_PROCESS;
}

int myStateFn_Process(int OldState, void *ObjP)
{
    return (process(ObjP) == DONE) ? MY_STATE_RESET : MY_STATE_PROCESS;
}

int stateValid(int StateFnSize, int State)
{
    return (State >= 0 && State < StateFnSize);
}

int stateFnRunOne(myStateFn_t StateFns, int StateFnSize, int State, void *ObjP)
{
    return StateFns[OldState])(State, ObjP);
}

void stateFnRun(myStateFn_t StateFns, int StateFnSize, int CurState, void *ObjP)
{
    int NextState;

    while(stateValid(CurState))
    {
        NextState = stateFnRunOne(StateFns, StateFnSize, CurState, ObjP);
        if(! stateValid(NextState))
            LOG_THIS(CurState, NextState);
        CurState = NextState;
    }
}

当然，这比第一次尝试要长得多（DRY 的有趣之处）。但它也更健壮 - 未能从状态函数之一返回状态将导致编译器警告，而不是默默地忽略State =早期代码中的缺失。

于 2010-06-23T21:42:22.547 回答
1

我会向您推荐“龙书”： Aho、Sethi 和 Ullman的编译器、原理-技术-工具。（购买起来相当昂贵，但您肯定会在图书馆找到它）。在那里你会找到解析字符串和构建有限自动机所需的任何东西。没有我能找到的地方goto。通常状态是一个数据表，转换是类似的函数accept_space()

于 2010-06-23T21:43:12.593 回答
1

我看不出 goto 和 switch 之间有什么区别。我可能更喜欢 switch/while，因为它为你提供了一个保证在 switch 之后执行的地方（你可以在其中输入日志并推理你的程序）。使用 GOTO，您只需不断地从一个标签跳到另一个标签，因此要加入日志记录，您必须将它放在每个标签上。

但除此之外，应该没有太大区别。无论哪种方式，如果您没有将其分解为函数并且不是每个状态都使用/初始化所有局部变量，那么您最终可能会得到一堆几乎意大利面条式的代码，不知道哪些状态改变了哪些变量，并且很难调试/推理关于。

顺便说一句，您可以使用正则表达式解析字符串吗？大多数编程语言都有允许使用它们的库。正则表达式通常会创建一个 FSM 作为其实现的一部分。通常，正则表达式适用于非任意嵌套的项目，对于其他所有项目，都有一个解析器生成器（ANTLR/YACC/LEX）。维护语法/正则表达式通常比底层状态机容易得多。您还说您正在实习，通常他们可能比高级开发人员更容易工作，因此正则表达式很有可能在字符串上工作。此外，大学通常不强调正则表达式，因此请尝试使用 Google 阅读它们。

于 2010-06-23T22:40:27.743 回答