2

我正在为同质 AST(所有节点都具有相同的类)构建一个 tree walker,评估 if 语句的正确方法是什么?

我的 if AST 是这样的: 在此处输入图像描述

我会在解析一个IF块时按顺序评估他的CONDBLOCK孩子,如果其中一个为真,则树行者不会评估其余的。

更清楚地说,我的树行者是这样的:

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规则来实现它,如果标志为真则返回(这意味着另一个块已经被执行)。

return retval;完全停止执行,我只想上升而不评估剩余条件。我怎样才能做到这一点?

4

1 回答 1

2

来自 AST 的任何涉及分支或跳转的运行时评估都可能会变得丑陋。您可能需要考虑将 AST 转换为一系列更常规的操作并按顺序执行它们。这是一个额外的步骤,但它会让你摆脱这样的困境,我认为它比 AST 评估器更容易验证和调试。

有了这个,这是一种跳过评估后续规则conditiondefcond规则的方法。我坚持您的结构,这意味着评估有两个不同的阶段:匹配阶段 ( exp) 和执行阶段 ( block)。这只值得注意,因为阶段是在子图的不同部分处理的,并且没有自然的跳转方式,因此需要在整个if语句中跟踪它们。

这是一个简单的类来管理跟踪单个if评估:

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

matched为真和done假时,下一个block被执行。执行后,done设置为true。当matcheddone都为真时,语句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是真的,那么"Executed b"将被打印出来。

变量值是通过调用来分配的tparser.addVar(...)。在这种情况下,a不等于任何其他变量,因此块{e}被评估。

于 2013-01-11T21:34:10.257 回答