语义词法分析器谓词性能

Question

我有一个词法分析器为传递给词法分析器的宏字符串的动态列表创建 MACRO 标记。我在最顶级的词法分析器规则中使用了一个语义谓词来实现这个特性：

MACRO: { macros != null && tryMacro() }? .;

其中 tryMacro() 只是检查是否有任何宏字符串与输入序列匹配。

这种方法的性能非常糟糕，经过一些研究后，我尝试将词法分析器规则更改为以下内容：

MACRO: . { macros != null && tryMacro() }?;

这大大提高了性能，但我不太明白为什么。 :) 因为 '.'匹配任何字符，语义谓词规则应该像以前一样多次调用，不是吗？有人可以解释这种行为吗？

Answer 1

原因很简单：如果你把谓词放在开头，词法分析器会评估它来决定是否应该应用 MACRO 规则。如果你把它放在最后，它只会在它有可能匹配 MACRO 规则时才执行检查。

因为 MACRO 是 非常 通用的，我想你把它放在规则的末尾，并且由于 它肯定会得到尝试了 最后 。它只能匹配单个字符标记，因此将优先使用更精确的规则。

如果 MACRO 规则被更优先的规则取代，则不会考虑它，也不会调用您的谓词。

Answer 2

我对此进行了进一步调试，结果发现规则的重新排序改变了词法分析器的行为，导致在解析期间不接受宏。感知到性能提高的原因是因为在词法分析器在进行预测时丢弃规则之前，语义谓词只被评估了几次。所以规则的改变实际上是无效的，而不是性能提升。

我最终通过将宏处理移至解析器解决了性能问题。