c语⾔⽤⾃动机识别字符串，使⽤有限状态⾃动机实现C语⾔的
宣⾔解析器
使⽤有限状态⾃动机实现C语⾔的声明解析器
摘要：在很多的游戏编程中，我们使⽤了有限状态⾃动机作为模型。有限状态⾃动机作为变成模型，具有通⽤性好，⽅便理解的特点。本⽂主要结合前⼀个系列的两篇⽂章(1)C语⾔声明解析器的实现和(2)⽤C语⾔实现有限状态⾃动机来说明如何⽤有限状态⾃动机模型实现⼀个C 语⾔的声明解析器。
⼀、状态机的设计
形式定义
· 定义：有限状态⾃动机(FA—finite automaton)是⼀个五元组：
– M=(Q, Σ, δ, q0, F)
· 其中，
– Q——状态的⾮空有穷集合。∀q∈Q，q称为M的⼀个状态，我们常常⽤枚举类型来实现，定义在machi
ne结构体之外。
– Σ——输⼊字母表。我们常常⽤枚举类型来实现，定义在machine结构体之外。
– δ——状态转移函数，有时⼜叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。可以⽤⼀个数组来实现，⼤概是⼀个statenum＊inputnum的数组，元素是trasition，包含动作函数action和下⼀个状态。放在machine结构之内。
– q0——M的开始状态，也可叫作初始状态或启动状态。q0∈Q。
– F——M的终⽌状态集合。F被Q包含。任给q∈F，q称为M的终⽌状态。
在我们进⾏程序实现的时候，⼀个statemachine的定义⼤概是这样的：
typedef struct
{
state current;
trasition trasitions[STATENUM][CONDITIONS];
} StateMachine, * pStateMachine;
其中，附属的其他定义还有其他的相关。
我们在解析⼀个C语⾔声明的时候，⼤致过程是这样的：
1)读取声明到第⼀个变量名称标识符name，此为状态S0
2)读取name后⾯的下⼀个标识符，确定类型并采取相应的动作：
“［”：这是⼀个数组，我们要处理这个数组，然后进⼊状态S1
“(”：这是⼀个函数，我们要处理这个函数，然后进⼊状态S2
“)”：它的前⾯是⼀个指针，我们要处理这个指针，然后进⼊状态S3
“／0”：声明读取完毕，可以结束了，进⼊状态S4
”other“：出错
这个状态机如下：
注意：S1,S2，S3，S4的状态图没有从图中体现出来，实际上，S1～S4的出边和S0是⼏乎⼀样的，所不同的就是S1没有经过function 到达S2的出边，因为数组的元素不能是函数(可以是函数指针)。这⼀部分可以参考前⾯的C语⾔声明规则。
S0：读完声明到第⼀个变量标识符
S1：读完⼀个数组
S2：读完后⾯的⼀个函数
S3：读完前⾯的⼀个指针
S4：解析完毕
⼆、数据结构的设计
我们仅仅谈与⾃动机相关的部分，其他的部分可以在 另外⼀篇⽂章 ⼀个C语⾔声明解析器的设计与实现⾥到。
typedef int (* actiontype)( );//函数指针，是⼀个动作
typedef struct{
state next;
actiontype action;
}trasition, *ptrasition;//转移动作：下⼀个状态+动作
typedef struct
{
state current;
int statenum;
int conditionnum;
trasition trasitions[STATENUM][CONDITIONS];
} StateMachine, * pStateMachine;//⾃动机：关键是 当前状态+转移函数集合
int initMachine(pStateMachine mymachine)//初始化状态机，设置初始状态和转移函数
state step(pStateMachine machine, condition mycondition)//状态机的运转函数
三、详细代码
#include
#include
#include
#include
#include
#define MAXTOKENLEN 64
#define MAXTOKENS 100
#define MAXDECLLEN 200
typedef int state;
typedef char condition;
#define STATENUM 5
#define STATE0 0
#define STATE1 1
#define STATE2 2
#define STATE3 3
#define STATE4 4
#define STATETRAP 6
#define CONDITIONS 5
struct token{
char type;
char string[MAXTOKENLEN];
};
struct decl{
char string[MAXDECLLEN];
int current_location;
};
struct decl mydecl;
int top=-1;
struct token this;//the current token
struct token stack[MAXTOKENS];//the tokens before the first identifer #define IDENTIFIER 'I'
#define QUALIFIER 'Q'
#define TYPE 'T'
#define pop stack[top--]
#define push(s) stack[++top]=s
//#define debug
char classify_string(const char *string);
/*
* init the value of mydecl*/
int init_parse_decl(){
if( fgets(mydecl.string,MAXDECLLEN,stdin) == NULL){
perror("can not read from the stdin");
}
if(strlen(mydecl.string)==MAXDECLLEN-1)
printf("you input is too long, you may get an error!");
mydecl.current_location=0;
#ifdef debug
printf("init:we get last char of mydecl:%c,%d\n",mydecl.string[strlen(mydecl.string)],mydecl.string[strlen(mydecl.string)]); #endif
}
/*
get a token from the current string,value the "this" and move the pointer
notice: we may get a '\0' at the end of the string
*/
int gettoken(){
char *ch_pointer=this.string;
//leave out the blank
while(mydecl.string[mydecl.current_location]==' '){
mydecl.current_location++;
}
*ch_pointer=mydecl.string[mydecl.current_location];
if(isalnum(*ch_pointer)){
while(isalnum(*ch_pointer)){
mydecl.current_location++;
ch_pointer++;
*ch_pointer=mydecl.string[mydecl.current_location];
}
*ch_pointer='\0';
#ifdef debug
printf("we get token:%s ",this.string );
#endif
return 1;
}
//else:(, ), [, ]
// printf("current location is:%d\n",mydecl.current_location);
/
/ printf("(%d)",mydecl.string[mydecl.current_location]);
switch(*ch_pointer){
case '*':
case '(':
case ')':
case '[':
case ']':
this.string[1]='\0';
mydecl.current_location++;
#ifdef debug
printf("we get token:%s ",this.string );
#endif
break;
case '\n':
case '\0':pe='\0';
// printf("we come to the end\n");
strcpy(this.string,"then end");
return 0;parse error怎么解决
default :
printf("we can not read this indentifier %d\n",*ch_pointer); parse_error();
}
return 1;
}
char classify_string(const char *string){
if(isspace(*string))
return '\0';
if(!strcmp(string,"const"))
return QUALIFIER;
if(!strcmp(string,"volatile"))
return QUALIFIER;
if(!strcmp(string,"void"))
return TYPE;
if(!strcmp(string,"char"))
return TYPE;