寻找关键词的最有效方法

Question

好的，所以我正在编写一个函数，作为词法分析器的一部分，用于“查找”或搜索关键字的匹配项。我的词法分析器捕获所有明显的标记，如单个和多个字符运算符（+ - * / > < = == 等）（还有注释和空格已经被去除），因此在我收集了仅包含字母数字字符（包括下划线）的流后，我调用一个函数，并将其字符串作为已知关键字或标识符进行匹配。

所以我想知道如何识别它？我知道我基本上需要将其与所有内置关键字的列表或数组或某些东西进行比较，如果匹配，则返回该匹配项到其相应的枚举值；否则，如果没有匹配，则必须是函数或变量标识符。那么我该如何寻找匹配项呢？我在某个地方读到过，使用二叉搜索树或哈希表是一种有效的方法，但问题是我从未使用过任何一种，因此不确定是否正确。我能否可能使用MySQL数据库？

- Dooms101

---

这个链接 https://dev59.com/4EbRa4cB1Zd3GeqPzVjJ 可能会对你有所帮助。 - vrdhn

在C++中使用MySQL进行关键词查找，就像调用Web服务执行两个整数的加法一样。 - pascal

Answer 1

如果您的关键词集是固定的，可以建立一个完美哈希来进行O(1)的查找。请看gperf或cmph。

- ergosys

---

你仍然会遇到非关键字的哈希冲突，所以我认为这并不比其他方法更有效。它也不是O(1)，虽然复杂度不取决于关键字数量，但确实取决于每个关键字的长度。 - Ben Voigt

查找后的验证是一个字符串比较，但这不太可能对性能产生重要影响。由于哈希是完美的，不存在哈希冲突的惩罚，输入要么匹配哈希槽，要么不匹配，不需要进行额外的搜索。 - ergosys

完美哈希函数实际上对编译器词法分析器并不是那么有用；更好的方法是计算单个哈希值，并在各种作用域哈希表中同时用于关键字查找和符号查找。通过增加关键字哈希表的大小，甚至更好的方法是在添加任何其他内容之前将关键字添加到全局哈希表中，可以廉价地保证关键字查找不会发生冲突，因此您只需要进行一次查找即可解决关键字和符号。或者考虑将所有标识符（包括关键字）都存储在单个全局哈希表中，以便在编译器的其他地方进行超级廉价的指针比较。 - Barry Kelly

关键字需要在全局变量或任何其他标识符之前找到，但除此之外我同意，这可能是在尝试基于完美哈希的任何其他优化之前要做的。我怀疑这很少值得。 - ergosys

Answer 2

这是针对一种具有特定关键字集的语言，这些关键字从不改变，而且它们并不是很多吗？

如果是这样，那么你使用什么可能并不重要。你会有更重要的事情要处理。

然而，由于列表不会改变，像这样硬编码搜索将是最好的选择：

// search on first letter
switch(s[0]){
  case 'a':
    // search on 2nd letter, etc.
    break;
  case 'b':
    // search on 2nd letter, etc.
    break;
  ........
  case '_':
    // search on 2nd letter, etc.
    break;
}

- Mike Dunlavey

Answer 3

一棵"Trie"肯定是最有效的方法。

- Ben Voigt

Answer 4

无论你使用的std::map实现如何，都可能足够了。

- no one important

---

或者如果你的编译器支持，可以使用std::tr1::unordered_map，最新的VC++和GCC都支持。 :) - Jonathan Grynspan

Answer 5

对于单个字符的关键字，查找表是完美的选择。对于多字符的关键字（特别是长度不同的情况）：哈希表就比较适合了。如果你需要更高的性能，则可以使用源代码生成来创建哈希表（使用一个简单的哈希函数，能够忽略大小写或不忽略，这取决于语法）。

所以我会用一个查找表和一个哈希表来实现它：首先使用查找表检查第一个字符（如果它是一个简单的操作符，那么它将以非字母数字值开头），如果没有找到，则检查哈希表。

- ruslik