Shulou(Shulou.com)06/02 Report--

Finite state machine (finite state machine) is referred to as FSM, which represents the mathematical model of finite states, transitions and actions between these states, and is widely used in the computer field. FSM is an efficient programming method within a logic unit. In server programming, the server can carry out corresponding processing logic according to different states or message types, making the program logic clear and easy to understand.

Where is the finite state machine usually used?

Processing language or natural language tokenizer, bottom-up parsing syntax parser

Various communication protocols such as sender and receiver transfer data to message processing, game AI and so on have application scenarios.

There are several ways to implement state machines, and I will elaborate on their advantages and disadvantages.

1. FSM realized by using if/else if statement

Using if/else if statements is the simplest and most understandable way to implement FSM. We only need to use a large number of if/else if statements to judge the state value to perform the corresponding logic processing.

Looking at the following example, we use a large number of if/else if statements to implement a simple state machine, perform the corresponding operations according to the different states, and achieve the state jump.

/ / for example, we defined the following enum {GET_UP, GO_TO_SCHOOL, HAVE_LUNCH, GO_HOME, DO_HOMEWORK, SLEEP,}; int main () {int state = GET_UP; / / Xiaoming's day while (1) {if (state = = GET_UP) {GetUp (); / / the function called state = GO_TO_SCHOOL / / transfer of status} else if (state = = GO_TO_SCHOOL) {Go2School (); state = HAVE_LUNCH;} else if (state = = HAVE_LUNCH) {HaveLunch ();}. Else if (state = = SLEEP) {Go2Bed (); state = GET_UP;}} return 0;}

After reading the above example, how do you feel? Do you feel that although the program is simple and easy to understand, it uses a large number of if judgment statements, which makes the code very low-end and the contemporary code expands sharply. There are only a few states in this state machine, and the code bloat is not obvious, but if we have dozens of states to deal with, the code of the state machine is difficult to read.

Second, use switch to realize FSM

The structure of FSM implemented with switch statement becomes clearer, and its disadvantages are obvious: although this design method is simple and handled by a lot of judgments, it is suitable for small-scale state switching processes, but it is difficult to expand and maintain if the scale is expanded.

Int main () {int state = GET_UP; / / one day of Xiao Ming while (1) {switch (state) {case GET_UP: GetUp (); / / specifically called function state = GO_TO_SCHOOL; / / State transfer break; case GO_TO_SCHOOL: Go2School (); state = HAVE_LUNCH; break; case HAVE_LUNCH: HaveLunch () State = GO_HOME; break;... Default: break;}} return 0;}

Third, use function pointers to implement FSM

The idea of using function pointer to realize FSM is to establish the corresponding state table and action query table, locate the corresponding action processing function according to the state table, event and action table, and then switch the state after execution.

Of course, the process of using function pointers to implement FSM is time-consuming and laborious, but it's all worth it, because when your program is large, it's easy to maintain a state machine based on this table structure.

Here is a framework for FSM implemented using function pointers:

We still take "Xiaoming's Day" as an example to design the FSM.

First, the state transition diagram of the FSM is given:

Let's explain the key parts of the code implementation.

First of all, we define the activity state of Xiaoming's day.

/ / for example, we defined the status of Xiaoming's day as follows: enum {GET_UP, GO_TO_SCHOOL, HAVE_LUNCH, DO_HOMEWORK, SLEEP,}

We also define the events that will happen.

Enum {EVENT1 = 1, EVENT2, EVENT3,}

Define the data structure of the state table

Typedef struct FsmTable_s {int event; / / event int CurState; / / current state void (* eventActFun) (); / / function pointer int NextState; / / next state} FsmTable_t

Next, we define the state table of the most important FSM, and our entire FSM operates according to this defined table.

FsmTable_t XiaoMingTable [] = {/ / {incoming event, current state, function to be executed Next state} {EVENT1, SLEEP, GetUp, GET_UP}, {EVENT2, GET_UP, Go2School, GO_TO_SCHOOL}, {EVENT3, GO_TO_SCHOOL, HaveLunch, HAVE_LUNCH}, {EVENT1, HAVE_LUNCH, DoHomework, DO_HOMEWORK}, {EVENT2, DO_HOMEWORK, Go2Bed, SLEEP}, / / add your codes here}

Action implementation of state machine registration, state transfer and event handling

/ * State machine registration * / void FSM_Regist (FSM_t* pFsm, FsmTable_t* pTable) {pFsm- > FsmTable = pTable;} / * State Migration * / void FSM_StateTransfer (FSM_t* pFsm, int state) {pFsm- > curState = state;} / * event handling * / void FSM_EventHandle (FSM_t* pFsm, int event) {FsmTable_t* pActTable = pFsm- > FsmTable; void (* eventActFun) () = NULL; / / function pointer initialized to empty int NextState Int CurState = pFsm- > curState; int flag = 0; / / identify whether the condition int I is satisfied; / * get the current action function * / for (I = 0; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.