3

好的，所以我正在编写一个函数作为词法分析器的一部分，用于“查找”或搜索与关键字的匹配项。我的词法分析器捕获了所有明显的标记，例如单字符和多字符运算符 ( + - * / > < = == etc) （注释和空格也已经被删除）所以我在收集了一个只有字母数字字符（包括下划线）的流之后调用了一个函数string，这个然后需要将字符串作为已知关键字或标识符进行匹配。

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

4

5 回答 5

4

如果您的关键字集是固定的，则可以为 O(1) 查找构建完美的散列。查看gperf或cmph。

于 2010-09-21T04:26:15.753 回答
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;
}
于 2010-09-21T20:58:06.340 回答
2

无论您使用何种std::map实现都可能就足够了。

于 2010-09-21T05:16:59.760 回答
1

“ trie”肯定是最有效的方法。

于 2010-09-21T04:21:39.300 回答
0

对于单字符关键字，查找表将是完美的。对于多字符（特别是如果长度不同）：哈希表。如果您需要性能，您甚至可以使用源代码生成来创建哈希表（使用能够或不忽略大小写的简单哈希函数，具体取决于您的语法）。

所以我会用 LUT 和哈希表来实现它：首先你用 LUT 检查第一个字符（如果它是一个简单的运算符，它将以非字母数字值开头），如果找不到，检查哈希表。

于 2010-09-21T06:22:08.857 回答