copy nodes of trees using ANTLR tree grammars

Question

I need some guidance on trying to solve a problem I ran across using tree grammars. Basically, I want to be able to do is replace/copy statements around that may be found in the tree. It is probably best to explain through an example.

Here is a sample input:

int a = 10;
new function A;

function A {
    int x;
    int y;
    new function B;
}

function B {
    float b = 20;
}

Wanted output (later on):

int a = 10;
int x;
int y;
float b = 20;

It is a simple search and replace of the statements inside the function blocks. My problem is does ANTLR provide a way to do it through tree grammars?

Here is a grammar that should parse the above input:

Test.g

grammar Test;
options {
  language = Java;
  output = AST;
}
tokens {
    VARDECL;
    FUNDEF;
    FUNCALL;
    BLOCK;
    ASSIGN;

    Assign = '=';
    EqT    = '==';  
    NEq    = '!=';
    LT     = '<';
    LTEq   = '<=';
    GT     = '>';
    GTEq   = '>=';
    NOT    = '!';
    PLUS   = '+';
    MINUS  = '-';
    MULT   = '*';
    DIV    = '/';
}

parse: statements+
     ;

statements : varDeclare
           | funcDefinition
           | funcCall
           ;

funcDefinition : 'function' id '{' funcBlock* '}' -> ^(FUNDEF id ^(BLOCK funcBlock*))
               ;

funcBlock : varDeclare
          | funcCall
          ;

funcCall : 'new' 'function' id ';' -> ^(FUNCALL id)
         ;

varDeclare : type id equalExp? ';' -> ^(VARDECL type id equalExp?)
           ;

equalExp : (Assign^ (expression | '...' )) 
         ;

expression : binaryExpression
           ;

binaryExpression : addingExpression ((EqT|NEq|LTEq|GTEq|LT|GT)^ addingExpression)*
                 ;

addingExpression : multiplyingExpression ((PLUS|MINUS)^ multiplyingExpression)*
                 ;

multiplyingExpression : unaryExpression 
                        ((MULT|DIV)^ unaryExpression)*
                      ;

unaryExpression: ((NOT|MINUS))^ primitiveElement
               | primitiveElement
               ;   

primitiveElement : literalExpression
                 | id
                 | '(' expression ')' -> expression
                 ;  

literalExpression : INT
                  ;              

id : IDENTIFIER
   ;

type : 'int'    
     | 'float'
     ; 

// L E X I C A L   R U L E S      

INT : DIGITS ;   

IDENTIFIER : LETTER (LETTER | DIGIT)*;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

fragment LETTER : ('a'..'z' | 'A'..'Z' | '_') ;
fragment DIGITS: DIGIT+;
fragment DIGIT : '0'..'9';

Test.java

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

import org.antlr.runtime.ANTLRStringStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.RuleReturnScope;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.DOTTreeGenerator;
import org.antlr.stringtemplate.StringTemplate;

public class Test {
    public static void main(String[] args) throws Exception {
        String src = "int a = 10;\r\n" + 
                "new function A;\r\n" + 
                "\r\n" + 
                "function A {\r\n" + 
                "   int x;\r\n" + 
                "   int y;\r\n" + 
                "   new function B;\r\n" + 
                "}\r\n" + 
                "\r\n" + 
                "function B{\r\n" + 
                "   float b = 20;\r\n" + 
                "}";
        TestLexer lexer = new TestLexer(new ANTLRStringStream(src));
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        TestParser parser = new TestParser(tokenStream);
        RuleReturnScope r = parser.parse();
        System.out.println("Tree:" + ((CommonTree) r.getTree()).toStringTree() + "\n");


        CommonTree t = (CommonTree)r.getTree();
        generateGraph(t, "Tree.dot");   
    }

    private static void generateGraph(CommonTree t, String file) throws IOException {
        DOTTreeGenerator gen = new DOTTreeGenerator();
        StringTemplate st = gen.toDOT(t);
        String output = file;
        PrintWriter out = new PrintWriter(new FileWriter(output));
        out.println(st);
        out.close();
    }
}

Tree.dot

How can I do a search for each FUNCALL and be replaced with the contents of BLOCK inside using Tree Grammar?

Thanks in advance!

Answer 1

In your grammar, you'll make a table blockMap of your FUNDEF BLOCKs with the ID as the key.

Then in your tree grammar something like this, though it will probably need some tweaking. You'll make a rule for funcCall:

funcCall : ^(FUNCALL id) -> {input.getTreeAdaptor().dupTree(blockMap.get(id)}
     ;

This is what makes a copy of the BLOCK from the map: input.getTreeAdaptor().dupTree(...)

You need to make a copy because nodes keep track of their parents, so you can only use them in one place in the tree.