评估同质AST中的IF子树 [英] Evaluate IF subtree in homogeneus AST
问题描述
我正在为同质AST（所有节点都具有相同的类）构建一个树遍历器，评估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 ，然后在 if 之后进入我的AST树以评估该块。
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 规则中签入，如果标志为true，则返回该规则（这意味着已经有另一个块
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).
但是返回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.
这样，这是一种跳过评估随后的条件和 defcond 规则的方法。我坚持使用您拥有的结构，这意味着评估具有两个不同的阶段：匹配阶段（ exp ）和执行阶段（阻止）。这仅值得注意，因为阶段是在子图的不同部分处理的，并且没有自然的跳转方法，因此需要在整个 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;
}
当匹配为true和 done 为false，将执行下一个 block 。执行后， done 设置为true。如果匹配和 done 都为真，则不再有块 s将在 if 语句的其余部分执行。
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（树解析器）
AstTreeEvaluatorParser.g (tree parser)
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（测试代码）
TreeEvaluatorTest.java (test code)
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 为true，则将打印 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屋！
