Re: Problem finding cause of memory exhausted

[Frans Englich]

On Saturday 10 May 2008 21:00:50 Laurence Finston wrote:
> 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).
[...]

I agree, I don't think this is caused by wrong recursion. I can't change my 
grammar, and I can't discard tokens based on the test expression because it 
cannot be evaluated at parse time. My language(XQuery) is functional in 
syntax, which is the reason to why the if expressions has to be parsed in one 
go: they're expressions, not statements.

However, I don't see how "delimiters" like semi-colons would help anyway, the 
grammar has a non-terminal for expressions so each test/then/else expression 
can be reduced(see "Reducing stack by rule 77 (line 1678):" in the debug 
output link).

However, the parsing of other functional languages, such as Haskell, should(?) 
have the same problem. So what am I doing wrong?

sizeof(YYSTYPE) yields 84 -- it's very big(and hence inefficient). Could that 
be the cause?


Any help is greatly appreciated -- choking on a moderately large input is of 
course an absolute no go.


Cheers,

                Frans