Hacker News Reader

Comment by chrisseaton | Hacker News Reader

Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory

But I still think it's a pretty good idea.

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.

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

Memory usage is linear too. It’s bounded by length of input * number of rules in the grammar.

For example 1 GB per character is linear... but it's still a hell of a lot.

The mathematical function doesn't matter as much as the practical overhead.

I mean... the clue's in the name, right?

(I worked on PEG and Packrat for my MEng.)

But packrat parsers don’t require nearly that much space in practice, right? Most languages I’ve worked with will have a relatively small number of production rules, requiring only a small number of results at each parsing position.

I think in practice they're pretty chunky.

I've also had luck with only storing results for only a very small subset of the productions of a grammar.

Languages with a small number of rules barely require parser tooling; ad-hoc hand-written recursive descent parsers don't add any dependencies, are trivial to write and are known to run well, if you have constant lookahead.

Any parsing algorithm uses "unlimited memory" if you make the input big enough.

But, seriously, it's called "packrat parsing," because it saves all the things. You have to expect it's going to use a bit of memory.

I still use it for everything. Memory at that scale just isn't an issue anymore. Your grammar would have to be huge and your data structures highly unoptimized for it to matter all that much.

Reply on news.ycombinator.com