我正在为编译器构建词法分析器,并且正在使用散列快速识别关键字。
我的哈希函数是:
int Eval_Hash(char *str)
{
int prime = 5381;
int i;
for(i = 0; i < strlen(str); i++)
prime = (prime*33) + str[i];
return (abs(prime%(KeyWordCount*KeyWordCount)));
}
我正在使用以下代码片段对关键字进行哈希处理。
i = 0;
while(i < KeyWordCount) {
while(1)
{
tmp = (Eval_Hash(keywordList[i])+j*j)%(KeyWordCount*KeyWordCount);
if(h.Elem[tmp].hashVal == INT_MIN)
{
strcpy(h.Elem[tmp].name,tokenList[i]);
h.Elem[tmp].hashVal = tmp;
strcpy(h.Elem[tmp].value,keywordList[i]);
break;
}
j++;
}
i++;
}
但是当我进行词法分析时,输入流中的词位被散列到不同的槽中。例如,假设“参数”是一个关键字,在初始化哈希表时已经对其进行了哈希处理。但是当我从输入流中读取“参数”时,它会被识别为其他一些标记。
从输入流中散列字符串的代码片段如下:
Hash_Value = Eval_Hash(str);
printf("\n \n Hash Value: %d Modified Hash Value: %d \n \n ",Hash_Value,Hash_Value%(KeyWordCount*KeyWordCount));
count = 1;
for(j=0;count<KeyWordCount;j++)
{
tmp = (Hash_Value+j*j)%(KeyWordCount*KeyWordCount);
if(h.Elem[tmp].flag == 1)
count++;
else if(strcmp(h.Elem[tmp].value, str) == 0)
{
alpha_flag = 1;
h.Elem[tmp].flag = 1;
strcpy(token->name,h.Elem[tmp].name);
break;
}
else
h.Elem[tmp].flag = 1;
}
此外,哈希表的 typedef 是
struct _hashElem {
int hashVal;
int flag;
char name[30];//keyw
char value[30];
};
typedef struct _hashElem hashElem;
struct _Hash {
hashElem Elem[KeyWordCount*KeyWordCount];
};
typedef struct _Hash Hash;
任何帮助将不胜感激。