ANTLR узел переписывают дерево как переменной глубины дерева

Question

Я пытаюсь сделать следующее переписывание оператора умножения в виде повторных добавлений:

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

Есть ли способ сделать это в один проход в ANTLR с использованием правило перезаписи дерева?

Если нет, то каков наилучший способ сделать это?

Я должен сделать это переписывание несколько раз, для каждого вхождения '*', и соответствующие t анализируются. Поэтому на t нет фиксированной границы.

Answer 1

Мне удалось решить проблему в несколько проходов. Я вычисляю максимальное количество проходов при разборе выражения и применяю правила перезаписи дерева несколько раз. Мне даже не нужно возвращаться, чтобы быть правдой. См. Код ниже.

Expr.g -> лексический, синтаксический анализатор грамматики

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 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 
    ;