Конечные автоматы в C

Я пытаюсь создать FSM в C, который следует этой диаграмме: ФШМ

И имеет вывод, который выглядит следующим образом: Введите описание изображения здесь

Я начал с определения 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, но ничего не имеет смысла. Может кто-нибудь указать мне правильное направление?
2 2
enums fsm

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

Постройте таблицу перехода состояний, содержащую следующие записи: 

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_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" нужно будет очистить.

2

Возможно, Вам было бы лучше использовать оператор switch (или даже таблицу переходов), но базовая структура остается прежней.

Если вы используете перечисление, используйте его. Не используйте магические числа. Смысл определения перечисления состоит в том, чтобы иметь возможность использовать значимые имена вместо чисел.

Если вы собираетесь вернуть новое состояние,нет абсолютно никакого смысла использовать параметр 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 имеет знак (что является общим) и значение оказывается отрицательным, результатом будет неопределенное поведение.
1