Language Implementation Patterns

Pattern 6

Memoizing Parser

Purpose

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].

Discussion

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 ...