评估同构 AST 中的 IF 子树 [英] Evaluate IF subtree in homogeneus AST
问题描述
我正在为同构 AST 构建一个 tree walker(所有节点都具有相同的类)，评估 if 语句的正确方法是什么?
I'm building a tree walker for an homogeneus AST (all nodes have same class), what's the correct way to evaluate an if statement?
我的 AST 是这样的:
My AST for if are like this:
我希望在解析 IF 块时，按顺序评估他的 CONDBLOCK 子项，如果其中一个为真，树遍历器不会评估其余的.
I would something that when parses an IF block, evaluates sequentially his CONDBLOCK children and if one of them is true, the tree walker doesn't evaluate the remaining.
更清楚地说，我的树行者是这样的:
More clearly, my tree walker is something like:
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 之后的块.
My question is, if in the example $op=+ so the first CONDBLOCK must be executed, I don't want evaluate anything else, I want execute the first CODEBLOCK and go up in my AST tree to evaluate the block after if.
现在我已经用一个标志和一个检查 condition 规则来实现它，如果标志为真则返回(这意味着另一个块已经被执行).
Now I've implemented that with a flag and a check in condition rule that returns if the flag was true (that means another block is already been executed).
但是 return retval; 完全停止执行，我只想不评估剩余条件就上去.我该怎么做?
But return retval; completely stops the execution, I want just go up without evaluate remaining conditions. How can I do that?
推荐答案
来自 AST 的任何类型的涉及分支或跳转的运行时评估都可能变得丑陋.您可能需要考虑将 AST 转换为一系列更常规的操作并按顺序执行它们.这是一个额外的步骤，但它会让你摆脱像这样的障碍，我认为它比 AST 评估器更容易验证和调试.
Any kind of runtime evaluation from an AST that involves branching or jumps is probably going to get ugly. You may want to consider converting the AST into a series of more conventional operations and execute them in sequence. It's an extra step, but it will get you out of jams like this one and I think it's easier to verify and to debug than an AST evaluator.
顺便说一下，这里有一种方法可以跳过评估后续的 condition 和 defcond 规则.我坚持你的结构，这意味着评估有两个不同的阶段:匹配阶段(exp)和执行阶段(block).这一点值得注意，因为阶段是在子图的不同部分处理的，并且没有自然的跳转方式，因此需要在整个 if 语句中跟踪它们.
With that out of the way, here is a way to skip evaluating subsequent condition and defcond rules. I'm sticking with the structure that you have, which means that evaluations have two distinct phases: a matching phase (exp) and an execution phase (block). This is only worth noting because the phases are handled in different parts of a subgraph and there is no natural means of jumping around, so they need to be tracked across the whole if statement.
这是一个管理跟踪单个 if 评估的简单类:
Here's a simple class to manage tracking a single if evaluation:
class Evaluation {
boolean matched = false;
boolean done = false;
}
当 matched 为真且 done 为假时，下一个 block 被执行.执行后，done 设置为 true.当 matched 和 done 都为真时，对于 if 语句的其余部分，不再执行 block .
When matched is true and done is false, the next block gets executed. After execution, done is set to true. When matched and done are both true, no more blocks get executed for the remainder of the if statement.
以下是处理此问题的树解析器规则:
Here are the tree parser rules to handle this:
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)
;
<小时>
这是我用来测试的语法和代码:
Here are the grammars and the code I used to test this:
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}.如果计算 {} 之间的 id，则会打印它.所以如果 a == b 为真，那么 "Executed b" 将被打印出来.
The test code evaluates if a == b {b} elif a == c {c} elif a == d {d} else {e}. The id between the {}s is printed if it is evaluated. So if a == b is true, then "Executed b" will be printed.
通过调用tparser.addVar(...) 来分配变量值.在这种情况下，a 不等于任何其他变量，因此块 {e} 被评估.
Variable values are assigned by calling tparser.addVar(...). In this case, a doesn't equal any other variable, so block {e} is evaluated.
这篇关于评估同构 AST 中的 IF 子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
