Методы реализации для состояний FSM - PullRequest
Новая
       51

Методы реализации для состояний FSM

1 голос
/ 21 июня 2010

Как вы реализуете состояния FSM (EDIT: конечный автомат)? Я обычно думаю о FSM как о наборе функций, диспетчер, и поток, чтобы указать текущее рабочее состояние. То есть я блокирую вызовы функций / функторов, представляющих государства.

Только сейчас я реализовал один в другом стиле, где я все еще представляю состояния с функцией (объектом) с, но поток просто вызывает state->step() метод, который пытается вернуть как можно быстрее. Если государство закончило и Переход должен состояться, это говорит о том, что соответственно. Я бы назвал это стилем «опроса», так как функции в основном выглядят как: 

void step()
{
  if(!HaveReachedGoal)
  {
    doWhateverNecessary();
    return; // get out as fast as possible
  }
  // ... test perhaps some more subgoals
  indicateTransition();
}

Мне известно, что это FSM в составе FSM.

Это выглядит довольно упрощенно, но у него есть определенные преимущества. Пока поток блокируется или удерживается в каком-то виде while (!CanGoForward)checkGoForward(); петля может быть громоздкой и громоздкой, опрос был намного легче отлаживать. Это потому, что объект FSM восстанавливает контроль после каждый шаг и выпуск некоторой отладочной информации - это бриз.

Ну, я отклоняюсь от своего вопроса: Как вы реализуете состояния автоматов?

Ответы [ 5 ]

1 голос
/ 21 июня 2010

Я помню свою первую программу FSM. Я написал это на C с очень простым switch оператором. Переход от одного состояния к другому или переход к следующему состоянию казался естественным.

Затем я перешел к использованию поиска по таблице . Я смог написать очень общий стиль кодирования, используя этот подход. Однако пару раз меня поймали, когда изменились требования, и я должен поддержать некоторые дополнительные мероприятия.

В последнее время я не написал ни одного автомата. Последнее, что я написал, было для модуля связи в C ++, где я использовал « шаблон проектирования состояний » в сочетании с « шаблон команды » (действие).

1 голос
/ 21 июня 2010

Я сделал это как таблицу, плоский массив в памяти, каждая ячейка - это состояние.Пожалуйста, посмотрите на источник cvs заброшенного проекта DFA .Для пример : 

class DFA {
    DFA();
    DFA(int mychar_groups,int mycharmap[256],int myi_state);
    ~DFA();
    void add_trans(unsigned int from,char sym,unsigned int to);
    void add_trans(unsigned int from,unsigned int symn,unsigned int to);
    /*adds a transition between state from to state to*/
    int add_state(bool accepting=false);
    int to(int state, int symn);
    int to(int state, char sym);
    void set_char(char used_chars[],int);
    void set_char(set<char> char_set);
    vector<int > table; /*contains the table of the dfa itself*/
    void normalize();

    vector<unsigned int> char_map;
    unsigned int char_groups; /*number of characters the DFA uses,
                    char_groups=0 means 1 character group is used*/
    unsigned int i_state; /*initial state of the DFA*/
    void switch_table_state(int first,int sec);
    unsigned int num_states;
    set<int > accepting_states;
};

Но это было для очень конкретной потребности (соответствие регулярным выражениям)

1 голос
/ 21 июня 2010

Шаблон проектирования состояния - это интересный способ реализации FSM:

http://en.wikipedia.org/wiki/State_pattern

Это очень чистый способ реализации FSM, но он может быть грязным в зависимости от сложностиваш FSM (но не количество штатов).Однако преимущества заключаются в том, что:

  • вы устраняете дублирование кода (особенно если / операторы else)
  • Проще расширять с новыми состояниями
  • Ваши классы имеютлучшая согласованность, поэтому вся связанная логика находится в одном месте - это также облегчит ваш код для написания тестов.

На этом сайте есть реализация Java и C ++:

http://www.vincehuston.org/dp/state.html

1 голос
/ 21 июня 2010

Всегда есть то, что я называю стилем реализации FSM в стиле Flying Spaghetti Monster (FSM-style FSM): используя лоты goto s. Например: 

state1:
  do_something();
  goto state2;

state2:
  if (condition) goto state1;
  else           goto state3;

state3:
  accept;

Очень хороший код спагетти: -)

0 голосов
/ 21 июня 2010

Если вы создаете сложный конечный автомат, вы можете проверить SMC - конечный автомат. Это берет текстовое представление конечного автомата и компилирует его на выбранный вами язык - он поддерживает Java, C, C ++, C #, Python, Ruby, Scala и многие другие.

...