昨天和同学讨论词法分析的状态机制的效率问题，我写的词法分析器查找状态是使用遍历查找，效率太低。想到在《编译原理与实践》一书中提到了使用折半查找和哈希表映射。
下面是我的转台转化机制的主要代码：
//状态机状态枚举
typedef enum {PLUS,MINUS,MULTI,DIVIDE,NUMBER,IDENTI,JINGHAO,COMMENT,IF,ELSE,END,REPEAT,UNTIL,ASSIGN,EQUAL,LESS,GREATER,LPAREN,RPAREN,SEMI,EXPRESSION,START,UNKNOWN} LexTokenType;
//状态转换结构
typedef struct {LexTokenType beg; char Domainbeg; char Domainend; LexTokenType end;} TransState;
//有限状态机状态转换描述
TransState trans[] ={
{NUMBER,'0','9',NUMBER},
{IDENTI,'A','Z',IDENTI},
{IDENTI,'a','z',IDENTI},
{IDENTI,'0','9',IDENTI},
{START,' ',' ',START},
{START,'\t','\t',START},
{START,'\n','\n',START},
{START,'\r','\r',START},
{START,'0','9',NUMBER},
{START,'A','Z',IDENTI},
{START,'a','z',IDENTI},
{START,'+','+',PLUS},
{START,'-','-',MINUS},
{START,'*','*',MULTI},
{START,'/','/',DIVIDE},
{START,'<','<',LESS},
{START,'>','>',GREATER},
{START,'(','(',LPAREN},
{START,')',')',RPAREN},
{START,';',';',SEMI},
{START,'=','=',ASSIGN},
{DIVIDE,'/','/',COMMENT},
{COMMENT,'\n','\n',START},
{COMMENT,'\n'+1,127,COMMENT},
{COMMENT,1,'\n'-1,COMMENT},
{COMMENT,-128,-1,COMMENT},//为支持汉字注释
{ASSIGN,'=','=',EQUAL},
};
上面的代码中共列举了27中状态转换。最坏情况下，程序将遍历全部27种转换。效率在这里大打折扣。
哈希函数的确定：
我们的查找过程主要是比较输入字符，因此可将输入字符作为查找项的主关键字。由于不同状态也会输入相同字符，所以将初始状态也作为关键字。我们用下面的代码生成一个函数映射。
int size = sizeof(trans)/sizeof(TransState);
for(int i=0; i<size; i++)
{cout<<((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)<<endl; }
注意到每两种转换的输入范围至少会相差2，因此使用下面的代码：
for(int i=0; i<size; i++)
{cout<<((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)/2+64<<endl; }
输出为：
118
144
176
119
106
83
84
87
127
152
184
117
119
116
121
134
136
114
115
133
135
112
77
136
72
3
131
((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)/2+64的范围在0到300多之间，用这样大的表就可存放哈希表。上面输出的最大值为184，所以关键字大与184的不用查表也知道不存在相应的转换。这样哈希表的大小缩小在184。为了支持汉字注释，状态机中允许出现扩展ACII字符。如果把这一要求去掉，我们的哈希表可缩小到127。