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
    ;