Assess subtree IF in AST homogenesis

Question

I am building a tree walker for the AST homogen (all nodes have the same class), what is the correct way to evaluate the if statement?

My AST, if so:

I would like something when analyzing an IF block sequentially evaluates its children CONDBLOCK elements, and if one of them is true, then the tree walker does not evaluate the remaining ones.

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) 

My question is, if in the example $op=+ first CONDBLOCK should be CONDBLOCK , I do not want to evaluate anything, I want to execute the first CODEBLOCK and go to my AST tree to evaluate the block after IF .

Now I implemented this with the flag and checked the condition rule, which returns if the flag was true (this means that another block has already been executed).

But return retval; completely stops execution, I just want to rise without evaluating the remaining conditions. How can i do this?

Answer 1

Any estimate of the runtime from the AST that includes branching or jumps is likely to become ugly. You may consider converting AST into a series of more common operations and their sequential execution. This is an additional step, but it will save you from traffic jams, like this one, and I think it is easier to check and debug than an AST evaluator.

From this point of view, this is a way to skip evaluating the following condition and defcond . I adhere to the structure that you have, which means that evaluations have two different phases: the matching phase ( exp ) and the execution phase ( block ). This is worth noting, because the phases are processed in different parts of the subgraph, and there are no natural ways to jump, so you need to track them throughout the if tag.

Here is a simple class to control the tracking of a single if score:

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

When matched true and done is false, the next block is executed. After done set to true. When matched and done are true, no more than block are executed for the remainder of the if .

Here are the parser tree rules for handling 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 grammar and code I used for testing:

TreeEvaluator.g (Combined Grammar for 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 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 (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(); } } 

The test code evaluates if a == b {b} elif a == c {c} elif a == d {d} else {e} . The identifier between {} is printed if it is evaluated. Therefore, if a == b true, then the symbol "Executed b" will be printed.

Variable values ​​are assigned by calling tparser.addVar(...) . In this case, a does not match any other variable, so the block {e} computed.