Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Re^2: Prevent "Out of Memory" error

by tford (Beadle)
on Nov 23, 2009 at 22:44 UTC ( #808946=note: print w/replies, xml ) Need Help??

in reply to Re: Prevent "Out of Memory" error
in thread Prevent "Out of Memory" error

You may be right that the un-adulterated algorithm is exponential in memory requirements, but it's classified as O(n^3) for time complexity.

It sounds like what many people are saying is basically "make it more efficient." Well I did, by using "shared subtrees" to consolidate memory usage (which helped a lot) and also a technique called "top-down filtering" which helps it to avoid the unnecessary work that JadeNB pointed out above.

Now it is about 3 times faster and uses about 1/10 as much memory, but the problem theoretically still exists.

It just doesn't seem right that Perl would allow you to keep throwing memory at a problem until it crashes, without allowing some way to trap for it.

I'll see if I can get a super-simplified model of the grammar and parser, and show an example that we can all look at. Basically, I'm pretty sure there's no good way to tell the complexity of parsing a given input without actually parsing it first.

Until then, thanks for all the help guys!

Oh by the way, I do realize that the parser used in the perl compiler is pretty exceptional, as far as the flexibility it allows, and the speed with which it parses. However, Perl is still a programming language, and the Perl parser makes decisions to ensure that in the end, the language that it accepts is unambiguous. Plus, it's written in C.

My particular application requires that we "never pick the wrong interpretation" for any given input. That's why I think it's necessary to have it come up with all valid parses.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://808946]
NodeReaper settles into the armchair by the fire. You weren't using it were you?

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2017-05-25 02:34 GMT
Find Nodes?
    Voting Booth?