2

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

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

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

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

4

5 回答 5

3

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

但是，最简单的实现方法是将单词按字母顺序放在一个数组中，然后bsearch从 C 库中使用。它应该几乎和哈希或特里一样快，因为您只处理 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);

如果您还没有它，您应该考虑获取一份编译器：原理、技术和工具。由于它的封面，它通常被称为龙书。

于 2012-07-09T17:18:22.887 回答
1

如果您正在寻找效率，我会说 Rabin Karp 不是您的最佳选择，而 Boyer-Moore 会发现您的最佳效率，尽管实施起来要困难一些。

如果您这样做是为了好玩，老实说，我认为没有必要进行优化，因为这些调用仍应在很短的时间内运行，并且您并不真的需要它以行业速度运行。

如果您正在尝试使用字符串匹配算法，这是一个很酷且有用的目标，我建议您研究 KMP 算法和 Boyer-Moore 算法，这两种算法都会在实施过程中教给您很多东西。

当然还有其他更直接的方法，比如字典查找和简单的二进制搜索等……，但这些方法并没有真正优化你正在处理字符串的事实，字符串比较是一个非常有趣的领域，你将不可避免地运行在某个时候进入。

于 2012-07-09T17:21:54.990 回答
1

假设您的关键字没有改变，这听起来像是完美哈希函数的正确案例。完美的散列函数将输入映射到整数（如常规散列函数），但没有冲突。

维基百科有几个完美的哈希生成器的链接，包括GNU gperf。

于 2012-07-09T21:01:03.963 回答
0

进行查找时首先想到的就是使用一个排序的键盘数组，然后对它们进行二分搜索。

于 2012-07-09T17:24:11.127 回答
0

如果关键字集是固定的，您可以使用完美散列，例如使用gperf。这只需要不断的工作和单个字符串比较，因此可能比其他方法更快。

于 2012-07-09T20:36:41.130 回答