C语言中的有限状态机

Question

我正在尝试按照此图在 C 中创建 FSM：

并且输出如下所示：

我首先定义了一个包含所有可能状态的 enum：

typedef enum {
Start = 0,
Build_Id = 1,
Identifier = 2,
Build_Num = 3,
Number = 4,
Error = 5
} State_type;

这是我目前拥有的代码：

State_type analyzeData(State_type* currState, char c);

int main(int argc, char** argv) {
  State_type currState = 0;
  for (int i = 1; i < strlen(*argv); ++i) {
    analyzeData(&currState, *argv[i]);
  }
}



State_type analyzeData(State_type* currState, char c) {
  if (currState == 0) {
    if (isblank(c)) {
      *currState = (State_type) 0;
      return *currState;
    }
    else if (isdigit(c)) {
      *currState = (State_type) 3;
      return *currState;
    }
    else if (isalpha(c)) {
      *currState = (State_type) 1;
      return *currState;
    }
  }
}

我的计划基本上是对所有其他可能的状态使用一系列 if-else 语句。我想我对我是否正确地处理这个问题有点困惑。我一直在尝试阅读其他 FSM 问题的答案，但没有任何意义。有人能指出我正确的方向吗？

Answer 1

使用 switch 语句（甚至转换 table）可能会更好，但基本结构是相同的。

如果您正在使用枚举，请使用它。不要使用幻数。定义枚举的要点是能够使用有意义的名称而不是数字。

如果您要 return 新状态，使用 in-out 参数绝对没有意义。使用原型

State_type analyzeData(State_type currState, char c);
/* Better would be int c. See below. */

那么一个典型的状态案例可能是：

case Start:
  if (isblank(c)) return Start;
  else (isdigit(c)) return Build_Num;
  else (isalpha(c)) return Build_Id;
  else return Error;

另请注意，isalpha 和朋友使用 int，而不是 char。如果 char 是有符号的（这很常见）并且该值恰好是负数，则会导致未定义的行为。

Answer 2

您定义了一个枚举来列出您的状态 - 很好！

typedef enum {
    Start_state = 0,
    Build_Id_state = 1,
    Identifier_state = 2,
    Build_Num_state = 3,
    Number_state = 4,
    Error_state = 5
} State_type;

对您的状态转换代码稍作更改，

int
main(int argc, char** argv) {
  State_type currState = 0;
  Action_t action;
  char* p = *argv; char symbol;
  int len = strlen(p);
  //C-strings are zero-indexed
  for (int i=0; i < len; ++i) {
    action = analyzeData(&currState, classify(symbol=*p++));
    switch(action) {
        case None_act: break;
        case Gather_act: //appropriate symbol gathering
        case Emit_act: //handle ident/number print/save
        case Stop_act: //appropriate behavior, e.g. i=len
        ...
    }
  }
}

构建状态转换 table 保存这些条目：

typedef struct state_table_entry_s {
    State_type state;
    Transition_t trans; //could define as bit-field
    State_type nextstate;
    Action_t action; //semantic action
} state_table_entry_t;

定义您的状态转换 table，这表明您没有为某些转换定义行为。（把table变成二维的，可以更快的处理state&transition）

state_table_entry_t states[] = {
    {Start_state, Letter_class, None_act, Build_Id}
   ,{Start_state, Digit_class, None_act, Build_Num}
   ,{Start_state, Blank_class, None_act, Start_state}
   ,{Start_state, Semicolon_class, Stop_act, Start_state}
   ,{Build_Id_state, Letter_class, Gather_act, Build_Id_state}
   ,{Build_Id_state, Digit_class, Gather_act, Build_Id_state}
   ,{Build_Id_state, Underscore_class, Gather_act, Build_Id_state}
   ,{Build_Id_state, Blank_class, None_act, Identifier_state}
   ,{Identifier_state, Blank_class, Emit_act, Start_state}
   ,{Build_Num_state, Digit_class, Gather_act, Build_Num_state}
   ,{Build_Num_state, Blank_class, None_act, Number_state}
   ,{Number_state, Blank_class, Emit_act, Start_state}
   ,{Stop_state, <any>, Error_act, Stop_state}
   ,{Error_state, <any>, None_act, Stop_state}
};

请注意上面'state transition table'如何清楚地记录您的状态机？您可以（轻松地）从配置文件加载此 table？

停止。您是否为每个（状态 X 转换）对定义（适当的）操作？

//States:
Start_state
Build_Id_state
Identifier_state
Build_Num_state
Number_state
Error_state

//Transitions:
Letter_class
Digit_class
Underscore_class
Blank_class
Semicolon_class
Other_class

对于以上内容，您需要定义状态转换 classes:

typedef enum {
    Letter_class
   ,Digit_class
   ,Underscore_class
   ,Blank_class
   ,Semicolon_class
   ,Other_class
} Transition_t;

并且您需要定义您的操作：

typedef enum {
    None_act
   ,Gather_act
   ,Emit_act
   ,Stop_act
   ,Error_act
} Action_t;

将您的 characters/symbols 转换为它们的转换 class（您可以使用 ctype.h 和 isalpha()、isdigit() 宏），

Transition_t classify(char symbol) {
    Transition_t class = Other_class;
    if (isblank(c)) {
      return(class = Blank_class); break;
    }
    else if(isdigit(symbol)) {
      return(class = Digit_class);
    }
    else if (isalpha(symbol)) {
      return(class = Letter_class); break;
    }
    else {
      switch(tolower(symbol)) {
        case ' ':
            return(class = Blank_class); break;
        case '_':
            return(class = Underscore_class); break;
        case ';':
            return(class = Semicolon_class); break;
        default :
            return(class = Other_class); break;
      }
    }
    return(class = Other_class); break;
}

在状态table中找到你的匹配状态（你可以使这个更高效），在转换table中找到你的匹配转换，然后进行语义操作，

Action_t
analyzeData(State_type& currState, Transition_t class) {
  for( int ndx=0; ndx<sizeof(states)/sizeof(states[0]); ++ndx ) {
    if( (states[ndx].state == currState)
    &&. (states[ndx].trans == class) ) { //state match
        semantic_action(states[ndx].action);
        currState = states[ndx].nextState;
        return(states[ndx].action);
    }
  }
}

您将需要定义您的 'semantic_action' 函数，当然您还需要 'gather' 您的输入，以便您可以在适当的动作时间执行输出。您的 'emit_act' 需要清理。

C语言中的有限状态机

Finite State Machines in C

c

enums

fsm