3 ms·

Yes, this. It's really common for naive implementations of packrat parsing to work just fantastic on short input strings (aka benchmarks) and then take literal

Yes, this. It's really common for naive implementations of packrat parsing to work just fantastic on short input strings (aka benchmarks) and then take literal minutes of "linear time" to parse, say, a 1kbyte source code file. Particularly if you (as is relatively common) do it in a scripting language with a naive memory management policy where creating and connecting vast numbers of small objects can be a performance problem. It turns out that, in practice, it's better to be selective about where you apply the packrat mechanism.

throwawaygh 6y ago
In practice, IME, a good rule of thumb is that if you're programmatically generating any of the rules then the grammar is probably too big for a packrat parser to be fast enough on realistic inputs. If not, and if the entire parser is written by a single person in a time-frame that would make sense for a parser, then things are probably gonna be ok in all but the worst implementations. YMMV