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