Re: java question

[Mariusz Nowostawski <mariusz@marni.otago.ac.nz>]

Hi Steve,

As for the stack overflow, theoretically, you can always feed the parser
with long enough input stream to cause the stack overflow (or OutOfMemory
if there is slightly different implementation technique beeing used).
There are some solutions, and they depend on per case basis.
Lets have a look.

Currently, as you know the walker is recursivelly calling itself to visit
in the depht-first fashion all the nodes in the production, something
like below (this is just a made up code, consult the actual one in your
DepthfirstAdapter.java)


// list = {el} el | {list} list el ;

    public void caseAElList(AElList node)
    {
        inAElList(node);
        if(node.getEl() != null)
        {
            node.getEl().apply(this);
        }
        outAElList(node);
    }

    public void caseAListList(AListList node)
    {
        inAListList(node);
        if(node.getList() != null)
        {
            node.getList().apply(this);
        }
        if(node.getEl() != null)
        {
            node.getEl().apply(this);
        }
        outAListList(node);
    }

The problem is, that in the second method, each time the recursion is
called, the virtual machine has to put all the current method "state" on
the stack, because after the return, it will need to continue the current
method execution (note, the recursion is inside

  node.getList().apply(this);

and later, after that call returns, the rest of the method has to be
executed.
One simple solution is (simply) to avoid recursion. You need to take
matters into your own hands. Lets simply go as deep as we can and
fetch all the interesting nodes, put them all into the local list, and
process later once we have them all. If the list is something like
50000 items, it should work with not tha big memory usage.

What about something like this:


    public void caseAListList(AListList node)
    {
	// we are taking the full control now

        final List lists = new ArrayList(50000);

	PList n = node.getList();
	while(n instanceof AListList){
          lists.add(n);
          n = node.getList();
        }

        // ok, we have the final List in this sequence which
        // is just an El type, remember that!

        final Iterator iter = lists.iterator();
	while(iter.hasNext()){
	  AlistList nl = (AListList)iter.next();
          process_whatever(nl.getEl());
	}

        //and the last one
        process_whatever(((AElList)n).getEl());
    }

Note, it is just out of my head, so you may need to fiddle with that as I
have not even compiled that code ;o)

Also note, that in this case, you will preserve the order in which you are
processing El nodes, so it will be as you want it to be. For your case you
do not want depht-virst processing model, as you want to process each El
as soon as possible.

ReversedDepthFirstAdapter does not in fact reverse the bottom-up to
top-down, it simply reverses the way productions like:

   list = el* ;

are expanded - in normal DepthFirstAdapter for list a b c d the sequence
of visiting will be { a b c d }, for reversed it will be { d c b a }.
It has nothing to do with recursive productions like your list = list el.


ps1.
Give a try the new pre-release JDK 1.4, it has much better heap
management, and I have noticed most of my programs hanging with Stack or
Memory exceptions with limited recources (when forcing the stack and
memory to be very small) on sun jdk 1.2.2 and ibm 1.3 just work fine with
JDK 1.4.


ps2.
There is a new release of SableCC 2.1.7.2 with "withtools" support on the
SourceForge, together with the grammas boundle
http://sf.net/projects/sablecc



Best regards
Mariusz