Latest developments: https://arxiv.org/abs/2005.06444
Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
11–20 of 25 posts
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#12Earlier quoted context omitted.
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.)
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]
#13Earlier quoted context omitted.
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.)
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.
I think in practice they're pretty chunky.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#14Tag title with 2002? It’s a great paper.
dammit. missed the edit window. will do so in future; thank you for the reminder.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#15Earlier quoted context omitted.
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.)
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.
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]
#16Latest developments: https://arxiv.org/abs/2005.06444
It is an interesting principle.
If I am reading the page 20 graphs, though, the parsing time gets crushed by the competition when parsing programming languages (Java, in the example). It is only competitive for simple grammars.
Beyond that, I feel like recursive descent parsers are the PostgreSQL of parsing: they are not exciting, but they get the job done well without fail. The rare cases where you need something else require subtle justification.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#17Earlier quoted context omitted.
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.)
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.
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]
#18Packrat 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 performanc…
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]
#19Conservation of genius.
Nice paper. Two columns. Why? In the 1980's computer science conferences like STOC and FOCS would hand out telephone-book sized proceedings, and it took two columns to squeeze it all in. Not relevant now, but the two columns make it that much harder to read on a tablet. I don't generally wish ill on anyone, but it's hard not to wish that the editors responsible for this idiotic convention would just die or retire in either order.
Re: Packrat Parsing: Simple, Powerful, Lazy, Linear Time [pdf]
#20Conservation of genius. Nice paper. Two columns. Why? In the 1980's computer science conferences like STOC and FOCS would hand out telephone-book sized proceedings, and it took two columns to squeeze it all in. Not relevant now, but the two columns make it that much harder to read on a tablet. I don't generally wish ill on anyone, but it's hard not to wish that the editors responsible for this idiotic convention woul…
If you had said "phone" I would have some sympathy, but "tablet"? Seriously? You act like two columns is somehow ridiculous, but magazines and newspapers also all use multiple columns. You only see single columns on narrow formats like handheld books (most paperbacks). A tablet is large enough to show an entirely page at once at a reasonable font size and you want two columns for that. If anything the technological restriction issue is that it was hard to make a two column typewriter so typed, instead of typeset, documents often have a humorously large single column. (Even on a phone it just isn't difficult enough to read that it deserves such hate.)