CODEWITHSUNDEEP
scalaparsing
Kevin Meredith
Kevin Meredith

Reputation: 41909

Understanding Packrat Parsers in Scala

DSLs in Action demonstrates a potential problem - slowness - when using alternation with a predictive parser:

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.

If, in the above example, my exp and term Parser's are lazily evaluated, i.e. lazy val ..., then does that mean that my parser is a packrat parser?

Upvotes: 1

Views: 421

Answers (1)

wingedsubmariner
wingedsubmariner

Reputation: 13667

No, marking them lazy val does not make them packrat parsers. What makes them packrat parsers is the underlying implementation. If you have mixed PackratParsers into your Parser then you are using packrat parsers. The fundamental difference is that the packrat parser caches already computed values (memoization) in order to prevent effort from being duplicated. Take a look at the code in https://github.com/scala/scala/blob/v2.10.4/src/library/scala/util/parsing/combinator/PackratParsers.scala.

Upvotes: 3

Related Questions