PEG 解析器（例如 Pegasus）中的 'memoize' 是什么，什么时候应该使用它？

Question

这是来自 Pegasus 的示例：

additive <double> -memoize
= left:additive "+" right:multiplicative { left + right }
/ left:additive "-" right:multiplicative { left - right }
/ multiplicative

在这种情况下，memoize 是什么，我应该在什么时候使用它？

我理解一般概念（给定输入的缓存输出）——但是当我们谈论 PEG 解析器时，"input" 是什么？

Answer 1

我是 Pegasus 的作者。

Pegasus 将使用光标的当前位置以及内部状态的当前版本作为缓存特定规则结果的键，如果该规则设置为 memoize。

如果规则可能在同一状态下被调用不止一次，您应该这样做。

例如，如果您有这种风格的解析器：

a = b "foo"
  / b "bar"
  / b "baz"

b = /* something expensive */

记住 b 规则是值得的，因为它被用作几个表达式的前缀。

当然，这是可选的，因为在很多情况下，这可以通过更好的方式进行优化：

a = b ("foo" / "bar" / "baz")

如果你把每条规则都标记为-memoize，这基本上和Packrat解析是一样的。 Pegasus 允许您有选择地控制它，因为这会产生相当大的开销。

PEG 解析器（例如 Pegasus）中的 'memoize' 是什么，什么时候应该使用它？

What is 'memoize' in PEG parsers (e.g. Pegasus) and when should it be used?

peg