News for hackers. Stuff that matters.
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.