Re: Problem finding cause of memory exhausted

[Laurence Finston]

On Thu, 8 May 2008, Frans Englich wrote:

> I'm running into "memory exhausted" and from reading section 2.3 this is 
> apparently caused by doing right recursion instead of left recursion. My 
> grammar is fairly large(grammar file is 3400 lines) and I simply have trouble 
> finding where I do right recursion.
> 

> How should I approach this problem? How can I find out where my right 
> recursion is? What patterns in the .output file should I look for?
> 

I don't know whether right recursion is involved, but it seems likely that 
you would run out of space on the stack, if all of the nested conditionals 
had to be parsed before the expression for the outer one can be completely 
parsed.  (Please excuse possible sloppy use of terminology --- I'm in a 
bit of a hurry.)

The way I handle conditionals in the grammar for GNU 3DLDF may or may not 
be relevant for you, but whether you choose to do it that way or some 
other way, it should still be possible to rapidly scan the tokens for the 
false conditions and discard them without making the parser cope with a 
lot of nested conditionals.

It's easier to do this if the end of a conditional is marked in some way, 
i.e., if curly braces are always required or if `end if' or something 
similar is required.  However, the conventions of C can also be used, 
without too much extra trouble (I believe).

For example, say I have something like this:

if (a)
   xyz();
elif (b)
   mno();
else 
   qrs;
endif

(This is pseudo-code, not 3DLDF code.)

If the condition `a' is false, I can just discard everything up until the 
next `elif', `else' or `endif'.  If I'm doing this, my scanner can be in a 
"state" (or "start condition") that indicates that I'm looking for one of 
these tokens.  If it finds an "elif", it is handled exactly like an "if".  
If it finds an "else", it executes it, because any preceding "if"s or 
"elifs" (in the same level of nesting) will have been false.  If it finds 
a true condition, the code in its block will be executed and if the 
scanner finds an "elif" or an "else", the start condition will be 
different, and any "elif" or "else" blocks can just be discarded.

Of course, one does need to keep track of the nesting level.

This method does require the tokens that indicate the structure of a 
conditional, i.e., `if', `elif', `else', `endif', semi-colons, curly 
braces, or whatever you're using, to keep their meanings while the 
scanner is scanning them rapidly.  Allowing them to be changed during this 
procedure would be more complicated, but not necessarily impossible.

My code for conditionals can be found here (`pcondit.w'):
http://cvs.savannah.gnu.org/viewvc/3dldf/3dldf/Group/CWEB/pcondit.w?view=log

I haven't looked at this code in a long time, so I don't remember the 
details.  On the other hand, that's an indication that it works properly.

I'll probably be off-line until Tuesday, so if you have any questions, 
don't be surprised if I don't answer right away.  I will do so as soon as 
I can, but I don't have a lot of time at present because of work.  

I hope this was of some help.

Laurence Finston



> If one wants to look at my code specifically, the details follows.
> 
> The input causing the error is:
> 
> if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else if (1) then 1
> else ()
> 
> My grammar for the if-expression is:
> 
> IfExpr: IF LPAREN Expr RPAREN THEN ExprSingle ELSE ExprSingle
> 
> I don't understand why this causes an error. The way the parser reduces is 
> the 
> way I would expect it too -- it has to read in all the tokens before it can 
> start reducing the first statement(or?).
> 
> The debugging output is:
> 
> http://www.codepaster.com/code.php?code=4865
> 
> The .output file is:
> 
> http://www.codepaster.com/code.php?code=4864
> 
> 
> Cheers,
> 
>               Frans
> 
> 
> _______________________________________________
> address@hidden http://lists.gnu.org/mailman/listinfo/help-bison
>