编译原理_使用哈希表给词法识别加速

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

昨天和同学讨论词法分析的状态机制的效率问题,我写的词法分析器查找状态是使用遍历查找,效率太低。想到在《编译原理与实践》一书中提到了使用折半查找和哈希表映射。

下面是我的转台转化机制的主要代码:

//状态机状态枚举

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。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航