c - 将短字符串与小字典进行比较的最有效方法(解析)

Question

我正在尝试优化我只是为了好玩而制作的简单 C 解释器，我正在像这样进行解析 - 首先我将文件解析为双向链表内的标记，然后进行语法和语义分析。
我想用这个原型(prototype)优化功能:

bool parsed_keyword(struct token *, char 字典[][]);

在函数内部，我基本上针对所有关键字调用 strcmp 并编辑 token 类型。 这当然会导致(几乎)每个正在解析的字符串需要 20 次 strcmp 调用。

我认为 Rabin-Karp 是最好的，但在我看来，它并不是最适合这项工作(将一个单词与小词典进行匹配)。 完成这项工作的最佳算法是什么？感谢您的任何建议。

Answer 1

对于这个特定问题，我可能会选择哈希表。它将提供 O(1) 查找您大小的表。不过，特里树也是一个不错的选择。

但是，最简单的实现方法是将单词按字母顺序放入数组中，然后使用 C 库中的 bsearch。它应该几乎与哈希或特里树一样快，因为您只处理 30 个单词。它实际上可能比哈希表更快，因为您不必计算哈希值。

Steve Jessop 的想法很好，将字符串首尾相连地布局在相同大小的字符数组中。

const char keywords[][MAX_KEYWORD_LEN+1] = {
 "auto", "break", "case", /* ... */, "while"
};

#define NUM_KEYWORDS sizeof(keywords)/sizeof(keywords[0])

int keyword_cmp (const void *a, const void *b) {
    return strcmp(a, b);
}

const char *kw = bsearch(word, keywords, NUM_KEYWORDS, sizeof(keywords[0]),
                         keyword_cmp);

int kw_index = (kw ? (const char (*)[MAX_KEYWORD_LEN+1])kw - keywords : -1);

如果您还没有，您应该考虑获取 Compilers: Principles, Techniques, and Tools 的副本。由于其封面，它通常被称为龙之书。