4 ms·
Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory But I still think it's a pretty good idea.
by chrisseaton 6y ago
Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory
But I still think it's a pretty good idea.
- josephg 6y agoMemory usage is linear too. It’s bounded by length of input * number of rules in the grammar.
- chrisseaton 6y agoFor 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.)
- centimeter 6y agoBut 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.
- chrisseaton 6y agoI think in practice they're pretty chunky.
- ackien 6y agoI've also had luck with only storing results for only a very small subset of the productions of a grammar.
- barrkel 6y agoLanguages 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.
- pmiller2 6y agoAny 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.
- stormbrew 6y agoYes, 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 agoIn 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
- unquietcode 6y agoI 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.