[antlr-interest] Multiple pass tree walking Q

Terence Parr parrt at cs.usfca.edu
Wed Oct 4 10:21:49 PDT 2006


On Oct 3, 2006, at 6:42 AM, Hill, Robert wrote:

> I want to make multiple passes over a tree but only utilise parts  
> of the tree for each pass so I've duplicated the tree grammar 3  
> times , adding actions only for the parts that matter at each pass.
  I have already added a wiki entry about this on the to do list:

http://www.antlr.org/wiki/display/ANTLR3/allow+skipping+of+entire 
+subtrees+during+tree+parsing

> So the question is , how do you ignore (remove) whole branches of a  
> tree? At the moment if I add a node into the parser output I have  
> to change all 3 tree walkers in response. If I know that the tokens  
> that pass 1 will no longer be affected, how can I remove all the  
> unwanted rules from that grammar so It only looks at the tokens it  
> needs?
I think what we really need is a filter mode for trees just like we  
have for lexer's.  This would be almost a declarative approach where  
you say what trees you want to match and what actions to execute when  
you see it.  For example,

tree grammar TP;

options {filter=true;}

IDENTITY
	:	^(MULT i:INT j:INT) {$i.text.equals("1")||$j.text.equals("1")}?
		-> i
	;

pretty sweet.   of course I need tree grammars to be able to generate  
trees before I can do this.

The idea will be that it tries all patterns looking for a match in  
the order specified.  An index can be used to speedthings up by only  
attempting rules on nodes in the tree that can possibly match.  For  
example if there is only one MULT node in the entire tree, don't walk  
the entire tree looking for that pattern.

added this is a wiki entry:

http://www.antlr.org/wiki/display/ANTLR3/filter+tree+grammar+mode

Ter


More information about the antlr-interest mailing list