c - 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

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

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
        ...
    }
  }
}

构建一个包含这些条目的状态转换表:

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;

定义您的状态转换表，这清楚地表明您尚未为某些转换定义行为。 (把表格做成二维的，可以更快速的处理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}
};

请注意上面的“状态转换表”如何清楚地记录您的状态机？您可以(轻松)从配置文件加载此表吗？

停止。 您是否为每个(状态 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

对于上述情况，您需要定义状态转换类:

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;

将您的字符/符号转换为它们的转换类(您可以使用 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;
}

在状态表中找到您的匹配状态(您可以使这更有效)，以及您在转换表中的匹配转换，然后进行语义操作，

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”函数，当然您还需要“收集”您的输入，以便您可以在适当的操作时间执行输出。你的“emit_act”需要清理。