News for hackers. Stuff that matters.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by chrisseaton on Sunday November 15, 2020 @02:38PM (#25104061)
Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory

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

Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by stormbrew on Sunday November 15, 2020 @03:50PM (#25104691)
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.

Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by throwawaygh on Sunday November 15, 2020 @06:52PM (#25106183)
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
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by josephg on Sunday November 15, 2020 @03:10PM (#25104342)
Memory usage is linear too. It’s bounded by length of input * number of rules in the grammar.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by chrisseaton on Sunday November 15, 2020 @03:12PM (#25104367)
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.)

Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by centimeter on Sunday November 15, 2020 @04:49PM (#25105240)
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.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by barrkel on Sunday November 15, 2020 @06:33PM (#25106049)
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.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by chrisseaton on Sunday November 15, 2020 @04:52PM (#25105267)
I think in practice they're pretty chunky.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by ackien on Sunday November 15, 2020 @06:22PM (#25105959)
I've also had luck with only storing results for only a very small subset of the productions of a grammar.
Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by pmiller2 on Sunday November 15, 2020 @03:27PM (#25104499)
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.

Re:Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf] by unquietcode on Sunday November 15, 2020 @04:12PM (#25104885)
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.