理解Scala中的Packrat解析器

Question

DSL在行动中演示了在与预测解析器一起使用alternation时存在的一个潜在问题--慢度：

Predictive parsers are fast and use linear time parsing, but a naïve implementation
of backtracking parsers can quickly degenerate to exponential time parsing. 

lazy val exp = exp ~ ("+" ~> term) |
               exp ~ ("-" ~> term) |
               term

Packrat parsers can help solve this problem of redoing the
same computation using the technique of memoization. 

如果在上面的示例中，对我的exp和term解析器进行了懒惰的计算，即lazy val ...，那么这是否意味着我的解析器是一个packrat解析器？

Answer 1

不，标记它们lazy val并不能使它们成为打包解析器。使它们成为packrat解析器的是底层实现。如果您已经将PackratParsers混合到您的Parser中，那么您将使用packrat解析器。基本的区别在于，packrat解析器缓存已经计算过的值(回忆录)，以防止重复工作。看看https://github.com/scala/scala/blob/v2.10.4/src/library/scala/util/parsing/combinator/PackratParsers.scala中的代码。