[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: java question





Mariusz--

Many thanks; In my clumsiness with Java, I somehow got tangled up in
your suggestion at the point of building the ArrayList. So, I
chickened out and used a Vector instead; this didn't work, either, as
it doesn't reverse the reversed order, so I used a Stack instead. I
kinda like the Stack; you don't have to pick any initial/absolute sizes.

    public void caseAListRecordList(AListRecordList node)
    {
       inAListRecordList(node);
       //  if(node.getRecordList() != null)
       //  {
       //      node.getRecordList().apply(this);
       //  }
       //  if(node.getRecord() != null)
       //  {
       //      node.getRecord().apply(this);
       //  }
	 	// we are taking the full control now

        final Stack lists = new Stack();

 		PRecordList n = node.getRecordList();
 		while(n instanceof AListRecordList)
		{
			lists.push(n);
			n = ((AListRecordList)n).getRecordList();
		}
        // ok, we have the final List in this sequence which
        // is just an El type, remember that!

        ((AElRecordList)n).getRecord().apply(this);

		while( ! lists.empty() )
		{
	  		AListRecordList nl = (AListRecordList)lists.pop();
        	nl.getRecord().apply(this);
		}

        //and the last one
        outAListRecordList(node);
    }

The above compiles and seems to do the job, reversing the reversed
order... can you see any mistakes I may be making?

Many thanks,

murf



>>>>> "Mariusz" == Mariusz Nowostawski <mariusz@marni.otago.ac.nz> writes:

    Mariusz> Hi Steve,

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

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


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

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

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

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

    Mariusz>   node.getList().apply(this);

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

    Mariusz> What about something like this:


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

    Mariusz>         final List lists = new ArrayList(50000);

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

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

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

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

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

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

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

    Mariusz>    list = el* ;

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


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


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



    Mariusz> Best regards
    Mariusz> Mariusz





-- 
murf:   Steve Murphy, 	             VP Technology
        57 Lane 17        Electronic Tools Company
        Cody, Wyoming          work: (307)754-8154
                               home: (307)754-5675
        email:                    murf@e-tools.com