Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Re: Prevent "Out of Memory" error

by JadeNB (Chaplain)
on Nov 23, 2009 at 16:16 UTC ( #808844=note: print w/replies, xml ) Need Help??

in reply to Prevent "Out of Memory" error

It works by building tree structures corresponding to every valid substring of the input, and storing them in memory. Then later on, it may combine some of the subtrees to make larger trees, which also need to be stored.
I think that all of us are instinctively terrified by the necessarily exponential behaviour of parsing every substring. Is this really necessary? As biohisham mentioned, limiting the ambiguity even in very small ways can help a lot—for example, think of how much natural-language freedom is allowed in Perl programs, which can still be parsed with relatively little memory overhead (I think!).

Replies are listed 'Best First'.
Re^2: Prevent "Out of Memory" error
by tford (Beadle) on Nov 23, 2009 at 22:44 UTC

    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://808844]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2021-05-13 05:29 GMT
Find Nodes?
    Voting Booth?
    Perl 7 will be out ...

    Results (134 votes). Check out past polls.