Конечные автоматы в Си

Question

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

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_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' необходимо очистить.

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