Woohoo! Tree pattern matching, rewriting a reality

Can't resist showing off new filter mode for tree grammars (this is working in my dev branch). Imagine I built some trees with Cymbal.g and want to define symbols and push/pop scopes. Previously you had to give full tree grammar even though we'd only have actions in a few spots and don't care about structure (we trust tree builder). By doing tree pattern matching, we get to focus only on those subtrees we care about.

We are also separating the patterns from the strategy to apply them (many thanks to Eelco Visser and guidance I got from his Stratego/XT tool. I should also mention that Jurge Vinju of ASF+SDF fame explained a lot of his rewrite technology this summer when I visited him at CWI in Amsterdam...btw, ever wonder why Holland has so many good coders? Weird. A new Dutch USF grad student, Jasper Roel, has lots of potential). I have defined a default down-then-up strategy that applies matching rules once on way down and repeatedly on way up. It invokes rules topdown and bottomup if defined. You can create your own easily with a bit of code. Then just create a tree parser (Def here) and ask it to execute the downup strategy:


CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
Def def = new Def(nodes);
def.downup(t);

Here are the patterns:


tree grammar Def;

options {
  tokenVocab = Cymbal;
  ASTLabelType = CommonTree;
  filter = true;
}

topdown
    :   enterClassScope
    |   enterBlock
    |   fieldDeclaration
    |   methodDeclaration
    |   formalParameters
    |   localDeclaration
    ;

bottomup
    :   exitClassScope
    |   exitBlock
    ;

// S C O P E S

enterClassScope
    :   ^('class' ID (^('extends' sup=ID))? .)
        {System.out.println("enter class");}
    ;

exitClassScope : 'class' {System.out.println("exit class");} ;

enterBlock
    :   BLOCK {System.out.println("enter block");}
    ;
    
exitBlock
    :   BLOCK {System.out.println("exit block");}
    ;

// S Y M B O L S

fieldDeclaration
    :   ^(FIELD_DECL type=. ID .?) {System.out.println("field "+$ID);}
    ;
    
localDeclaration
    :   ^(LOCAL_DECL type=. ID .?) {System.out.println("local "+$ID);}
    ;

methodDeclaration
    :   ^(METHOD_DECL type=. ID .+) {System.out.println("def method "+$ID);}
    ;

formalParameters
    :   (^(PARAMETER type=. ID) {System.out.println("def arg "+$ID);})+ 
    ;

Ain't that cool?

Here is the downup strategy where we are only matching not rewriting:


    public void downup(Object t) {
        TreeVisitor v = new TreeVisitor(new CommonTreeAdaptor());
        TreeVisitorAction actions = new TreeVisitorAction() {
            public Object pre(Object t)  { applyOnce(t, topdown_fptr); return t; }
            public Object post(Object t) { applyOnce(t, bottomup_fptr); return t; }
        };
        v.visit(t, actions);
    }

Then for tree grammars with filter=true, output=AST:


    public Object downup(Object t) {
        TreeVisitor v = new TreeVisitor(new CommonTreeAdaptor());
        TreeVisitorAction actions = new TreeVisitorAction() {
            public Object pre(Object t)  { return applyOnce(t, topdown_fptr); }
            public Object post(Object t) { return applyRepeatedly(t, bottomup_ftpr); }
        };
        t = v.visit(t, actions);
        return t;
    }

We applyRepeatedly on way up and pass around result trees in case we need to walk them.

org.antlr.runtime.tree.TreeFilter and TreeRewriter are superclass of generated tree parser and derive from TreeParser.

I define two rules you can implement but you could define any strategy and any rule dependencies you wanted:


    // methods the downup strategy uses to do the up and down rules.
    // to override, just define tree grammar rule topdown and turn on
    // filter=true.
    public Object topdown() throws RecognitionException { return null; }
    public Object bottomup() throws RecognitionException { return null; }