3 ms·
Memory usage is linear too. It’s bounded by length of input * number of rules in the grammar.
by josephg 6y ago
Memory 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.