TL;DR Packrat trades guaranteed linear memory usage for worst-case polynomial time; the worst-case almost never comes up in non-contrived input, so it's a reaso

TL;DR Packrat trades guaranteed linear memory usage for worst-case polynomial time; the worst-case almost never comes up in non-contrived input, so it's a reasonable implementation decision to go with the less memory-hungry naive implementation. Depends on the algorithm; the naive recursive algorithm takes worst-case exponential time, while the packrat algorithm guarantees linear time. However, for most sensible[1] inputs, the recursive algorithm runs in linear time and constant space, while packrat takes about the same time, but with linear space usage. [1] Where "sensible" is defined to be "amount of backtracking is bounded by a fixed small constant, as is grammar nesting depth" - conditions that hold for most human-generated files matching useful grammars (I've been working on a new PEG parsing algorithm; it doesn't work so well, but the results I've been getting in testing about the existing algorithms are quite interesting.)