Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
pdos.csail.mit.edu
Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
1–10 of 25 posts
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#2Packrat 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]
#3Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory But I still think it's a pretty good idea.
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]
#4Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory But I still think it's a pretty good idea.
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.)
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#5Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory But I still think it's a pretty good idea.
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]
#6For LL and LR languages. Not for general CFGs. The abstract also mentions other classes, but isn't specific, probably referring to other deterministic classes of CFG.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#7Tag title with 2002? It’s a great paper.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#8Packrat 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.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#9Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Unlimited Memory But I still think it's a pretty good idea.
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.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#10Guido van Rossum's series on PEG parsing
https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...
Proposal to use PEG parser in python https://www.python.org/dev/peps/pep-0617/
Python PEG grammar https://github.com/python/cpython/blob/3.9/Grammar/python.gr...