CODEWITHSUNDEEP
antlr
wasserfeder
wasserfeder

Reputation: 486

ANTLR rewrite tree node as variable depth tree

I'm trying to do the following rewrite of the multiplication operator as repeated additions:

(* a t=INT) -> (+ a (+ a (+ a (+ ... + a) ... )) (t times)

Is there a way to do this in a single pass in ANTLR using a tree rewrite rule?

If not, what is the best way to go about it?

I have to do this rewriting multiple times, for each occurrence of '*', and the corresponding t's are parsed. Therefore, there is no fixed bound on the t's.

Upvotes: 1

Views: 178

Answers (1)

wasserfeder
wasserfeder

Reputation: 486

I managed to solve the problem in multiple passes. I compute the max number of passes while parsing the expression and apply the tree rewrite rules multiple times. I don't even need backtrack to be true. See code below.

Expr.g -> lexer, parser grammar

grammar Expr;
options {
    output=AST;
    ASTLabelType=CommonTree;
}

tokens {
    MULT='*';
    ADD='+';
}

@header{
import java.lang.Math;
}

@members {
public int limit=0;
}

prog :   expr {limit=$expr.value;} ;

expr returns [int value]
    :   a=multExpr {$value=$a.value;} (ADD^ b=multExpr {$value=Math.max($value, $b.value);})* ;

multExpr returns [int value]
    :   primary {$value=$primary.value;} (MULT^ c=INT {$value=Math.max($value, $c.int);})? ;

primary returns[int value]
    :   ID              {$value = 0;}
    |   '('! expr ')'!  {$value = $expr.value;}
    ;

ID  :   'a'..'z'+ ;
INT :   '0'..'9'+ ;
WS  :   (' '|'\r'|'\n')+ {skip();} ;

Eval.g -> tree rewrite grammar with main program

    tree grammar Eval;

options {
    tokenVocab=Expr;
    ASTLabelType=CommonTree;
    output=AST;
}

@members {

    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        ExprLexer lexer = new ExprLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ExprParser parser = new ExprParser(tokens);

        CommonTree t = null;
        try {
            t = (CommonTree) parser.prog().getTree();
        } catch(RecognitionException re){
            re.printStackTrace();
        }

        System.out.println("Tree: " + t.toStringTree());
        System.out.println();

        int loops = parser.limit;
        System.out.println("Number of loops:" + loops);
        System.out.println();

        for(int i=0; i<loops; i++) {
            System.out.println("Loop:" + (i+1));
            CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
            Eval s = new Eval(nodes);
            t = (CommonTree)s.prog().getTree();
            System.out.println("Simplified tree: "+t.toStringTree());
            System.out.println();
        }
    }
}

prog : expr ;

expr
    : ^(ADD a=expr b=expr)
    | ^(MULT a=expr t=INT) ( {$t.int>1}?=>  -> ^(ADD["+"] $a ^(MULT["*"] $a INT[String.valueOf($t.int - 1)]))
                           | {$t.int==1}?=> -> $a )
    | INT
    | ID
    ;

Upvotes: 1

Related Questions