c - 更快地阅读关键字列表

Question

我正在为通用编程语言编写一个简单的词法分析器，其中一种标记类型是“关键字”，它具有一些预定义的控制流标记，例如“if”、“else”、“while”、“return”。

我想知道使用 x86 Standard C 检查某个关键字是否在我的列表中的最快方法。

我的想法是使用跳转表，但 C 字符串比较是有问题的，因为 C 字符串是 char 类型的数组。

Answer 1

最快的方法是手动构建一个 trie 或等效的状态机。Flex（或任何其他 lex 变体）会为您做到这一点。

Answer 2

理论上，哈希表提供 O(1) 的查找。但是，我会实现一个静态查找表。假设您要搜索的令牌数量很少。表格的线性搜索不应该证明成本太高。