[antlr-interest] Tree Transformation, can problem be solved easily with ANTLR??

[Daniel Shane]

Hi!

I have nearly finished my new Lucene query builder using ANTLR, and it works like a charm, in fact I'm about to release it to the Lucene community, but I have one case that I cant seem to resolve easily. Maybe its just because I dont have that much experience in tree transformations, but here is the problem.

I have an operator, call N_PROXIMITY, which takes the form "/n" like /1, /12, /200 etc... and this operator is binary (takes 2 operands).

If someone enters this :

A /1 B /2 C /3 D

I would like ANTLR to reorder the priority to this :

(((A /1 B) /2 C) /3 D)

Meaning that the lowest numbers have the highest priority.

If this was the query :

A /3 B /2 C

This would be the result :

(A /3 (B /2 C))

In my ANTLR parser, I build a AST tree that simply orders them first come first serve disregarding the values of the operators, and I'm trying to write an ANTLR tree transformation that could rebalance the tree to take into account the N_PROXIMITY level/value.

Would anyone have an easy idea on how that could be done without playing with the AST like this :

// UGLY Code that rebalances an /n based AST to take into account the chaining of /n operators
// Lower /n operators have higher priority than higher /n operators
public AST transformNProximityAST(AST t) {
		while(true) {
			if (t.getFirstChild() == null) {
				return t;
			}
			if (t.getFirstChild().getType() != N_PROXIMITY) {
				return t;
			}
			
			int type = t.getType();
			String text = t.getText();
			
			if (Integer.parseInt(t.getText().substring(1)) < Integer.parseInt(t.getFirstChild().getText().substring(1))) {
				CommonAST left = new CommonAST();
				left.setType(t.getFirstChild().getFirstChild().getType());
				left.setText(t.getFirstChild().getFirstChild().getText());
				
				CommonAST newAST = new CommonAST();
				
				CommonAST right = new CommonAST();
				right.setType(t.getType());
				right.setText(t.getText());
				right.addChild(t.getFirstChild().getFirstChild().getNextSibling());
				right.addChild(t.getFirstChild().getNextSibling());
				
				t.initialize(t.getFirstChild().getType(), t.getFirstChild().getText());
				t.setFirstChild(null);
				t.setNextSibling(null);
				t.addChild(left);
				t.addChild(transformNProximityAST(right));
			}
			
			return t;
		}
	}
_________________________________________________________________
Be one of the first to try Windows Live Mail.
http://ideas.live.com/programpage.aspx?versionId=5d21c51a-b161-4314-9b0e-4911fb2b2e6d