performance - 关键字和标识符之间的有效区分

Question

我正在构建一个编译器并处于词法分析器阶段:

最初在符号表中安装保留字。符号表条目的一个字段表明这些字符串绝不是普通标识符，并告诉它们代表哪个 token 。我们假设这个方法在图 3.14 中被使用。当我们找到一个标识符时，如果它不存在，则对 installID 的调用将它放在符号表中，并返回一个指向找到的词素的符号表条目的指针。当然，词法分析时任何不在符号表中的标识符都不能是保留字，所以它的记号就是id。函数 getToken 检查符号表条目以查找找到的词素，并返回符号表中表示该词素表示 id 或最初安装在表中的关键字标记之一的任何标记名称。

但是现在每次识别关键字时，我都必须遍历整个符号表，这就像比较每个关键字/Id 识别的“n”个元素。
会不会太低效了。我还可以做些什么？

请帮忙。

Answer 1

如果你建立一个有限状态自动机来识别词位，那么它的终端状态应该对应于语言词位。

您可以将关键字排除在 FSA 之外，对于看起来像标识符的字符串，您最终只会得到一个终端状态。这是手动编码 FSA 时的常见实现。你会遇到你现在的问题。作为符号表的实际问题，无论您使用关键字做什么，您都需要极快的标识符查找，这几乎表明您需要散列解决方案。如果你有这个，那么你可以快速查找并检查你的“它必须是一个关键字”位。有很多好的散列方案存在；像往常一样，Wikipedia on hash functions是一个很好的起点。这是一个实用的解决方案；我在我的 PARLANSE 编译器中使用它(参见我的 bio)，它在几十秒内处理百万行文件。

这并不是最快的解决方案。最好在 FSA 中包含关键字(这往往鼓励使用词法分析器生成器，因为将所有关键字添加到手动编码的 FSA 中很不方便，但并不难)。如果你这样做，并且你有看起来像标识符的关键字，例如，转到 ，将会有最终状态实际上表明您已经识别出一个恰好拼写为特定关键字的标识符。

您如何解释该最终状态取决于您。一个明显的选择是，这样的结束状态表明您已经找到了一个关键字。不需要哈希表查找。