c - 在构建词法分析器时使用哈希表

Question

我正在为编译器构建一个词法分析器，并使用散列来快速识别关键字。

我的哈希函数是:

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++;
        }

但是当我进行词法分析时，输入流中的词位被散列到不同的槽中。例如，假设“parameters”是一个关键字，在初始化哈希表时已经对其进行了哈希处理。但是当我从输入流中读取“参数”时，它被识别为其他 token 。

从输入流中哈希字符串的代码片段如下:

                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;

任何帮助将不胜感激。

Answer 1

这是浪费你的时间。在当今时代，或者实际上在 1988 年左右首次出现之后的任何时代，您应该使用 flex 来生成词法分析器，并且您应该让它识别关键字，只需将它们单独指定为规则即可。它可以像识别一般标识符一样快速地做到这一点。根本不需要哈希表。