这个问题可能听起来陈词滥调,但我在这里遇到了情况。
我正在尝试实现一个有限状态自动机来解析 C 中的某个字符串。当我开始编写代码时,我意识到如果我使用标签来标记不同的状态并使用 goto 从一个状态跳转到另一个视情况而定。
在这种情况下,使用标准中断和标志变量非常麻烦,并且难以跟踪状态。
什么方法更好?最重要的是,我担心这会给我的老板留下不好的印象,因为我正在实习。
这个问题可能听起来陈词滥调,但我在这里遇到了情况。
我正在尝试实现一个有限状态自动机来解析 C 中的某个字符串。当我开始编写代码时,我意识到如果我使用标签来标记不同的状态并使用 goto 从一个状态跳转到另一个视情况而定。
在这种情况下,使用标准中断和标志变量非常麻烦,并且难以跟踪状态。
什么方法更好?最重要的是,我担心这会给我的老板留下不好的印象,因为我正在实习。
本质上没有错goto
。它们经常被认为是“禁忌”的原因是因为一些程序员(通常来自汇编世界)使用它们来创建几乎不可能理解的“意大利面条”代码。如果您可以在使用goto
语句的同时保持代码干净、可读且无错误,那么您将获得更大的权力。
为每个状态使用goto
语句和一段代码绝对是编写状态机的一种方式。另一种方法是创建一个将保存当前状态的变量,并使用 switch 语句(或类似语句)根据状态变量的值选择要执行的代码块。请参阅 Aidan Cully 的回答,了解使用第二种方法的良好模板。
实际上,这两种方法非常相似。如果您使用状态变量方法编写状态机并对其进行编译,则生成的程序集可能非常类似于使用该goto
方法编写的代码(取决于您的编译器的优化级别)。该goto
方法可以看作是从状态变量方法中优化掉额外的变量和循环。您使用哪种方法是个人选择的问题,只要您正在编写工作、可读的代码,我希望您的老板不会认为您使用一种方法与另一种方法有什么不同。
如果您将此代码添加到已经包含状态机的现有代码库中,我建议您遵循已经在使用的任何约定。
使用 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;
}
如果我想给老板留下好印象,我会使用像Ragel这样的 FSM 生成器。
这种方法的主要好处是您可以在更高的抽象层次上描述您的状态机,而无需担心是使用 goto 还是 switch。更不用说在 Ragel 的特定情况下,您可以自动获得 FSM 的漂亮图表,在任何点插入动作,自动最小化状态数量和各种其他好处。我有没有提到生成的 FSM 也非常快?
缺点是它们更难调试(自动可视化在这里有很大帮助)并且您需要学习一种新工具(如果您有一台简单的机器并且您不太可能经常编写机器,这可能不值得。 )
我会使用一个变量来跟踪您所处的状态,并使用一个开关来处理它们:
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;
}
}
Goto 不一定是邪恶的,我必须强烈反对 Denis,是的 goto 在大多数情况下可能是一个坏主意,但有一些用途。goto 最大的恐惧是所谓的“spagetti-code”,即无法追踪的代码路径。如果您可以避免这种情况,并且始终清楚代码的行为方式并且您不使用 goto 跳出函数,那么 goto 就没有什么可反对的了。请谨慎使用它,如果您想使用它,请真正评估情况并找到更好的解决方案。如果您无法做到这一点,可以使用 goto。
避免goto
,除非添加的复杂性(以避免)更加混乱。
在实际工程问题中,goto 的使用空间非常有限。学者和非工程师在使用goto
. 也就是说,如果您将自己描绘成一个实施角落,其中很多goto
是唯一的出路,请重新考虑解决方案。
正确工作的解决方案通常是主要目标。使其正确和可维护(通过最小化复杂性)具有许多生命周期的好处。先让它起作用,然后逐渐清理它,最好是通过简化和去除丑陋。
我不知道您的具体代码,但是否有这样的原因:
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 =
早期代码中的缺失。
我会向您推荐“龙书”: Aho、Sethi 和 Ullman的编译器、原理-技术-工具。(购买起来相当昂贵,但您肯定会在图书馆找到它)。在那里你会找到解析字符串和构建有限自动机所需的任何东西。没有我能找到的地方goto
。通常状态是一个数据表,转换是类似的函数accept_space()
我看不出 goto 和 switch 之间有什么区别。我可能更喜欢 switch/while,因为它为你提供了一个保证在 switch 之后执行的地方(你可以在其中输入日志并推理你的程序)。使用 GOTO,您只需不断地从一个标签跳到另一个标签,因此要加入日志记录,您必须将它放在每个标签上。
但除此之外,应该没有太大区别。无论哪种方式,如果您没有将其分解为函数并且不是每个状态都使用/初始化所有局部变量,那么您最终可能会得到一堆几乎意大利面条式的代码,不知道哪些状态改变了哪些变量,并且很难调试/推理关于。
顺便说一句,您可以使用正则表达式解析字符串吗?大多数编程语言都有允许使用它们的库。正则表达式通常会创建一个 FSM 作为其实现的一部分。通常,正则表达式适用于非任意嵌套的项目,对于其他所有项目,都有一个解析器生成器(ANTLR/YACC/LEX)。维护语法/正则表达式通常比底层状态机容易得多。您还说您正在实习,通常他们可能比高级开发人员更容易工作,因此正则表达式很有可能在字符串上工作。此外,大学通常不强调正则表达式,因此请尝试使用 Google 阅读它们。