December 2009
Intermediate to advanced
380 pages
9h 2m
English
| Pattern 6 | Memoizing Parser |
This pattern records partial parsing results during backtracking to guarantee linear parsing performance, at the cost of a small amount of memory.
Memoizing is a form of dynamic programming and lets us avoid reparsing the same input with the same rule. Another name for memoizing recursive-descent parser is packrat parser, a fabulous term coined by Bryan Ford in Packrat parsing:: simple, powerful, lazy, linear time, functional pearl [For02].
Without memoization to avoid redundant parsing, backtracking can lead to impractically slow (exponentially complex) parse times. This pattern guarantees linear parse time at the cost of a bit of memory. The extra memory is well worth the gain in parsing speed. I’ve ...