哪个是键，哪个是关键字哈希表的项目
本文关键字：项目 哈希表 关键字 | 更新日期: 2023-09-27 18:30:26
我需要实现一个词法分析器，我需要一种数据结构来保存关键字。我被建议使用哈希表来保留关键字，一个建议是使用C#哈希表形式的System.Collections。但是我有一个问题：要使用这个哈希表，我需要一个键和一个项目。我只有关键字。我应该将关键字用作键还是项目，还是两者兼而有之？由于关键字不同，我可以使用另一种数据结构，例如二叉树吗？我真正感兴趣的是：编译器如何实现这个问题？
通常，关键字仅具有语法值，因此在大多数编译器中，它们仅用于选择适当的语法规则。因此，它们的"价值"立即被消耗掉。由于他们的身份是唯一有用的信息，因此使用HashSet可能比使用HashMap更合适。
但是，可能有一组语法相同的关键字，从而形成有效的枚举类型。在这种情况下，枚举值可以是与关键字关联的值。
对于手工构建的词法分析器，使用哈希集或其他此类数据结构可能很简单，但大多数编译器实际上会将关键字与其他词法标记模式一起编译为有限状态自动机。这允许在词法扫描期间识别关键字，而无需任何外部数据结构。
无论如何，在几乎所有语言中，关键字集都是固定的，因此使用编译到词法扫描器中的高效数据结构是最合适的。例如，使用可以二叉搜索的字符串的排序静态向量而不是二叉树是合理的。或者，可以使用预先构建的trie;这几乎等价于上面提到的有限状态自动机。