[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