C专家编程 第8章 为什么程序员无法分清万圣节和圣诞节 8.7 用C语言实现有限状态机

用C语言实现有限状态机 
有限状态机（Finite State Machine, FSM）是一个数学概念。它是一种协议，用于有限数量的子程序（状态）的发展变化。每个子程序进行一些处理并选择下一种状态。（通常取决于下一段输入）

FSM可以用作程序的控制结构。FSM对于那些以输入为基础，在几个不同的可选动作中进行循环的程序尤其合适。投币售货机就是一个FSM的好例子。

它的基本思路是用一张表保存所有可能的状态，并列出进入每个状态时可能执行的所有动作，其中最后一个动作就是计算（通常在当前状态和下一次输入字符的基础上，另外再经过一次表查询）下一个应该进入的状态。你从一个“初始状态”开始。在这一过程中，翻译表可能会告诉你进入了一个错误的状态，表示一个预期之外的或错误的输入。你不停地在各种状态间进行切换，直到到达结束状态。 

在C语言中，有好几种方法可以用来表达FSM，但它们绝大多数都是基于函数指针数组。一个函数指针数组可以像下面这样声明：
void (*state[MAX_STATES])();
如果知道了函数名，就可以像下面这样对数组进行初始化：
extern int a(), b(), c(), d();
int (*state[])() = {a, b, c, d};
可以通过数组中的指针来调用函数：
(*state[i])();
所有的函数必须接受同样的参数，并返回同种类型的返回值（除非把数组元素做成一个联合）。函数指针是很有趣的。注意，我们甚至可以去掉指针形式，把上面的调用写成：
state[i]();
甚至是：
(******state[i]) ();
这是一个在ANSI C中流行的不良方法：调用函数和通过指针调用函数（或任意层次的指针间接引用）可以使用同一种语法。

/*用FSM实现cdecl*/
#include
#include
#include
#include
#define MAXTOKENS 100
#define MAXTOKENLEN 64
enum type_tag {
    IDENTIFIER, QUALIFIER, TYPE
}; 

struct token {
    char type;
    char string[MAXTOKENLEN];
};

int top = -1;
/*在第一个标识符（identifier)前保存所有的标记（token）*/
struct token stack[MAXTOKENS];
/*保存刚读入的标记*/
struct token this_2;
#define pop stack[top--]
#define push(s) stack[++top] =  s
enum type_tag classify_string(void) /*标识标识符的类型*/
{
    char *s = this_2.string;
    if (!strcmp(s, "const")) {
        strcpy(s, "read_only ");
        return QUALIFIER;
    }
    if (!strcmp(s, "volatile")) {
        return QUALIFIER;
    }
    if (!strcmp(s, "void")) {
        return TYPE;
    }
    if (!strcmp(s, "char")) {
        return TYPE;
    }
    if (!strcmp(s, "signed")) {
        return TYPE;
    }
    if (!strcmp(s, "unsigned")) {
        return TYPE;
    }
    if (!strcmp(s, "short")) {
        return TYPE;
    }
    if (!strcmp(s, "int")) {
        return TYPE;
    }
    if (!strcmp(s, "long")) {
        return TYPE;
    }
    if (!strcmp(s, "float")) {
        return TYPE;
    }
    if (!strcmp(s, "double")) {
        return TYPE;
    }
    if (!strcmp(s, "struct")) {
        return TYPE;
    }
    if (!strcmp(s, "union")) {
        return TYPE;
    }
    if (!strcmp(s, "enum")) {
        return TYPE;
    }
    return IDENTIFIER;    
} 

void gettoken(void) {
    /*读入下一个标记，保存在“this”中*/
    char *p = this_2.string;
    /*略过所有空白符*/
    while ((*p = getchar()) == ' ');
    if (isalnum(*p)) {
        /*在标识符中读取A-Z, 1-9字符*/
        while (isalnum(*++p = getchar()));
        ungetc(*p, stdin);
        *p = '\0';
        this_2.type = classify_string();
        return; 
    }
    this_2.string[1] = '\0';
    this_2.type =*p;
    return;
}

void initialize(), get_array(), get_params(), get_lparen(), get_ptr_part(), get_type();
void (*nextstate)(void) = initialize;

/*用有限机实现的cdecl */ 
int main() {
    /*在不同的状态间转换，直到指针为null*/
    while (nextstate != NULL) {
        (*nextstate)();
    } 
    return 0;
} 

void initialize() {      
    gettoken();
    while (this_2.type != IDENTIFIER) {
        push(this_2);
        gettoken(); 
    } 
    printf("%s is ", this_2.string);
    gettoken();
    nextstate = get_array;  
}

void get_array() {      
    nextstate = get_params;   
    while (this_2.type == '[') {
        printf("array ");
        gettoken(); /*一个数字或者']'*/
        if (isdigit(this_2.string[0])) {
            printf("0..%d ", atoi(this_2.string) - 1);
            gettoken(); /*读取']'*/ 
        }
        gettoken(); /*在']'继续读取*/
        printf("of ");
        nextstate = get_lparen;
    }
}

void get_params() {   
    nextstate = get_lparen;
    if (this_2.type == '(') {
        while (this_2.type != ')') {
            gettoken();
        }
        gettoken();
        printf("function returning ");
    }
}

void get_lparen() {   
    nextstate = get_ptr_part;
    if (top >= 0) {
        if (stack[top].type == '(') {
            pop;
            gettoken(); /*在')'之后读取*/
            nextstate = get_array; 
        }
    }
}

void get_ptr_part() {  
    nextstate = get_type;
    if (stack[top].type == '*') {
        printf("pointer to ");
        pop;
        nextstate = get_lparen;
    } else if (stack[top].type == QUALIFIER) {
        printf("%s", pop.string);
        nextstate = get_lparen;
    }
}

void get_type() {    
    nextstate = NULL;
    /*处理在读入标识符之前被放在堆栈里的所有标记*/
    while (top >= 0) {
        printf("%s ", pop.string);
    } 
    printf("\n");
}

/* 输出：

*/ 

如果想干得漂亮一些，可以让状态机函数返回一个指向通用后续函数的指针，并把它转换为适当的类型。这样，就不需要全局变量了。如果不想搞得太花哨，可以使用一个switch语句作为一个简朴的状态机，方法是赋值给控制变量并把switch语句放在循环内部。关于FSM还有一个最后一点需要说明：如果你的状态函数看上去需要多个不同的参数，可以考虑使用一个参数计数器和一个字符串指针数组，就像main函数的参数一样。我们熟悉的int argc、char *argv[]机制是非常普遍的，可以成功应用在你所定义的函数中。