2

同種 AST (すべてのノードが同じクラス) 用のツリー ウォーカーを構築しています。if ステートメントを評価する正しい方法は何ですか?

if の AST は次のようになります。 ここに画像の説明を入力

IFブロックを解析するときに、そのCONDBLOCK子を順番に評価し、そのうちの 1 つが true の場合、ツリー ウォーカーは残りを評価しません。

より明確に、私のツリー ウォーカーは次のようなものです。

ifStat       : ^(IF { jump=false; } condition* defcond?) 
condition    : { if (jump) return retval; } ^(CONDBLOCK exp block) { jump=$exp.value; }
defcond      : ^(DEFAULT block)

私の質問は、例$op=+で最初のCONDBLOCKものを実行する必要がある場合、他に何も評価したくない場合、最初のものを実行CODEBLOCKし、AST ツリーを上って の後にブロックを評価したいということですif。

conditionこれで、フラグと、フラグが true の場合 (つまり、別のブロックが既に実行されていることを意味します) を返すチェックイン ルールを実装しました。

しかしreturn retval;、実行を完全に停止し、残りの条件を評価せずに上に行きたいだけです。どうやってやるの？

4

1 に答える 1

2

分岐やジャンプを伴う AST からのあらゆる種類の実行時評価は、おそらく見苦しくなります。AST を一連の従来の操作に変換し、それらを順番に実行することを検討することをお勧めします。これは余分な手順ですが、このようなジャムから抜け出すことができます。また、AST エバリュエーターよりも検証とデバッグが簡単だと思います。

conditionそれはさておき、後続のルールとルールの評価をスキップする方法を次に示しdefcondます。私はあなたが持っている構造に固執しています。つまり、評価には2つの異なるフェーズがあります。マッチングフェーズ（exp）と実行フェーズ（block）です。ifフェーズはサブグラフのさまざまな部分で処理され、ジャンプする自然な手段がないため、これは注目に値するだけです。そのため、ステートメント全体で追跡する必要があります。

単一のif評価の追跡を管理する単純なクラスを次に示します。

class Evaluation {
    boolean matched = false;
    boolean done = false;
}

matchedが true でfalse の場合done、次blockが実行されます。実行後、donetrueに設定されます。matchedとdoneが両方とも true の場合、ステートメントblockの残りの s は実行されません。if

これを処理するためのツリー パーサー ルールは次のとおりです。

ifStat       
@init { Evaluation eval = new Evaluation(); }
             : ^(IF condition[eval]* defcond[eval]?) 
             ;

condition [Evaluation eval]
             : ^(CONDBLOCK exp {if ($exp.value) eval.matched = true;} evalblock[eval])
             ;

defcond [Evaluation eval] 
             : ^(DEFAULT {eval.matched = true;} evalblock[eval]) //force a match
             ;

evalblock [Evaluation eval]     
             : {eval.matched && !eval.done}? //Only do this when a condition is matched but not yet executed
                block                //call the execution code
                {eval.done = true;}  //evaluation is complete.
             | ^(CODEBLOCK .*)  //read the code subgraph (nothing gets executed)                
             ;

これをテストするために使用した文法とコードは次のとおりです。

TreeEvaluator.g (AST を生成するための結合された文法)

grammar TreeEvaluator;

options { 
    output = AST;
}

tokens { 
    CONDBLOCK;
    CODEBLOCK;
    DEFAULT;
}


compilationUnit : condition+ EOF;
condition   : cif elif* celse? -> ^(IF cif elif* celse?);
cif         : IF expr block -> ^(CONDBLOCK expr block);
elif        : ELIF expr block -> ^(CONDBLOCK expr block);
celse       : ELSE block -> ^(DEFAULT block); 
expr        : ID EQ^ ID;
block       : LCUR ID RCUR -> ^(CODEBLOCK ID);

IF  : 'if';
ELIF: 'elif';
ELSE: 'else';
LCUR: '{';
RCUR: '}';
EQ  : '==';
ID  : ('a'..'z'|'A'..'Z')+;
WS  : (' '|'\t'|'\f'|'\r'|'\n')+ {skip();};

AstTreeEvaluatorParser.g (ツリー パーサー)

tree grammar AstTreeEvaluatorParser;

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

@members { 
    private static final class Evaluation {
        boolean matched = false; 
        boolean done = false;
    }

    private java.util.HashMap<String, Integer> vars = new java.util.HashMap<String, Integer>();

    public void addVar(String name, int value){
        vars.put(name, value);
    }

}

compilationUnit : ifStat+;

ifStat       
@init { Evaluation eval = new Evaluation(); }
             : ^(IF condition[eval]* defcond[eval]?) 
             ;

condition [Evaluation eval]
             : ^(CONDBLOCK exp {if ($exp.value) eval.matched = true;} evalblock[eval])
             ;

defcond [Evaluation eval] 
             : ^(DEFAULT {eval.matched = true;} evalblock[eval]) //force a match
             ;

evalblock [Evaluation eval]     
             : {eval.matched && !eval.done}? //Only do this when a condition is matched but not finished 
                block                //call the execution code
                {eval.done = true;}  //evaluation is complete.
             | ^(CODEBLOCK .*)  //read the code node and continue without executing
             ;

block        : ^(CODEBLOCK ID) {System.out.println("Executed " + $ID.getText());};

exp returns [boolean value]
            : ^(EQ lhs=ID rhs=ID)
                {$value = vars.get($lhs.getText()) == vars.get($rhs.getText());}
            ;

TreeEvaluatorTest.java (テスト コード)

public class TreeEvaluatorTest {

    public static void main(String[] args) throws Exception {
        CharStream input = new ANTLRStringStream("if a == b {b} elif a == c {c} elif a == d {d} else {e}");
        TreeEvaluatorLexer lexer = new TreeEvaluatorLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);

        TreeEvaluatorParser parser = new TreeEvaluatorParser(tokens);

        TreeEvaluatorParser.compilationUnit_return result = parser.compilationUnit();

        if (lexer.getNumberOfSyntaxErrors() > 0 || parser.getNumberOfSyntaxErrors() > 0){
            throw new Exception("Syntax Errors encountered!");
        }

        AstTreeEvaluatorParser tparser = new AstTreeEvaluatorParser(new CommonTreeNodeStream(result.getTree()));
        tparser.addVar("a", 0);
        tparser.addVar("b", 2);
        tparser.addVar("c", 3);
        tparser.addVar("d", 4);
        AstTreeEvaluatorParser.compilationUnit_return tresult = tparser.compilationUnit();

    }
}

テスト コードは を評価しif a == b {b} elif a == c {c} elif a == d {d} else {e}ます。s の間の id{}が評価された場合に出力されます。a == bが true の場合、出力さ"Executed b"れます。

変数値は、 を呼び出すことによって割り当てられtparser.addVar(...)ます。この場合、a他の変数と等しくないため、ブロック{e}が評価されます。

于 2013-01-11T21:34:10.257 に答える